umcb.h

Go to the documentation of this file.

//
// This program can be freely used in an academic environment
// ONLY for research purposes, subject to the following restrictions:
//
// 1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    an acknowledgment in the product documentation is required.
// 2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
// 3. This notice may not be removed or altered from any source distribution.
//
// Any other use is strictly prohibited by the author, without an explicit 
// permission.
//
// Note that this program uses the LEDA library, which is NOT free. For more 
// details visit Algorithmic Solutions at http://www.algorithmic-solutions.com/
// There is also a free version of LEDA 6.0 or newer.
//
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// ! Any commercial use of this software is strictly !
// ! prohibited without explicit permission by the   !
// ! author.                                         !
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//
// This software is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
//
// Copyright (C) 2004-2008 - Dimitrios Michail <dimitrios.michail@gmail.com>
//

#ifndef UMCB_H
#define UMCB_H

#include <LEP/mcb/config.h>

#ifdef LEDA_GE_V5
#include <LEDA/graph/graph.h>
#include <LEDA/graph/edge_array.h>
#include <LEDA/graph/node_array.h>
#include <LEDA/core/d_int_set.h>
#include <LEDA/core/array.h>
#include <LEDA/core/list.h>
#else
#include <LEDA/graph.h>
#include <LEDA/d_int_set.h>
#include <LEDA/edge_array.h>
#include <LEDA/node_array.h>
#include <LEDA/array.h>
#include <LEDA/list.h>
#endif

#include <LEP/mcb/spvecgf2.h>
#include <LEP/mcb/signed.h>
#include <LEP/mcb/superset.h>
#include <LEP/mcb/sptrees.h>
#include <LEP/mcb/transform.h>
#include <LEP/mcb/verify.h>

// start our namespace
namespace mcb 
{ 

#if defined(LEDA_NAMESPACE)
    using leda::graph;
    using leda::array;
    using leda::edge;
    using leda::edge_array;
    using leda::d_int_set;
    using leda::list;
#endif

    template<typename W, class Container>
    class SupportMCB
    {
        public:
            typedef W result_type;

            SupportMCB( const graph& g_, 
                        array< Container >& mcb_, 
                        array< Container >& proof_,
                        const mcb::edge_num& enumb_ 
                        ) 
                : g(g_), C(mcb_), S(proof_), enumb(enumb_), N(enumb_.dim_cycle_space())
            {
#if ! defined(LEDA_CHECKING_OFF)
                if ( Is_Undirected_Simple( g ) == false )
                    error_handler(999,"MIN_CYCLE_BASIS: illegal graph (parallel,anti-parallel edges or loops?)");
#endif
                C.resize(N);
                S.resize(N);
            }

            virtual ~SupportMCB() {}

            W run() { 
                checkPreconditions();

#ifdef LEP_STATS
                float Tcycle = 0.0, Torthog = 0.0, Ttemp;
#endif

                initializeSupportVectors();
                
                W min = W();
                for( int k = 0; k < N; ++k ) {
#ifdef LEP_STATS
                    leda::used_time( Ttemp );
#endif
                    chooseSparsestSupportHeuristic( k );

#ifdef LEP_STATS
                    Torthog += leda::used_time( Ttemp );
#endif

                    min += computeShortestOddCycle( k );

#ifdef LEP_STATS
                    Tcycle += leda::used_time( Ttemp );
#endif
                    updateSupportVectors( k );

#ifdef LEP_STATS
                    Torthog += leda::used_time( Ttemp );
#endif

                }

#ifdef LEP_STATS
                std::cout << "LEP_STATS: cycle computation time: " << Tcycle << std::endl;
                std::cout << "LEP_STATS: orthogonal base maintain time: " << Torthog << std::endl;
#endif

                return min;
            }

        private:

            virtual void checkPreconditions() = 0;

            void initializeSupportVectors() {
                for( int i = 0; i < N; ++i ) { 
                    S[i].clear(); 
                    S[i].insert(i); 
                } 
            }

            void chooseSparsestSupportHeuristic( int k ) { 
#ifndef MCB_LEP_UNDIR_NO_EXCHANGE_HEURISTIC
                int minS = k;
                for( int r = k+1; r < N; ++r ) {
                    if ( S[r].size() < S[minS].size() )
                        minS = r;
                }
                if ( minS != k ) {  // swap
                    std::swap( S[k], S[minS] );
                }
#endif
            }

            virtual W computeShortestOddCycle( int k ) = 0;

            void updateSupportVectors( int k ) { 
                for( int l = k+1; l < N; ++l )   {
                    if ( (C[k].intersect(S[l])).size() % 2 == 1 )   {
                        S[ l ] %= S[k];
                    }
                }
            }

        protected:
            const graph& g;
            array<Container>& C;
            array<Container>& S;
            const mcb::edge_num& enumb; 
            int N; 
    };

    template<typename W, class Container>
    class WeightedSupportMCB: public SupportMCB< W, Container>
    {
        public:
            typedef SupportMCB< W, Container> base_type;

            WeightedSupportMCB( const graph& g_, 
                                const edge_array<W>& len_,
                        array< Container >& mcb_, 
                        array< Container >& proof_,
                        const mcb::edge_num& enumb_ ) 
                : base_type( g_, mcb_, proof_, enumb_ ), len(len_)
            {
            }

        private:

            void checkPreconditions() { 
#if ! defined(LEDA_CHECKING_OFF)
                edge e;
                forall_edges( e , g ) {
                    if ( len[e] < 0 )
                        error_handler(999,"MIN_CYCLE_BASIS: illegal edge (negative weight)");
                }
#endif
            }

        protected:
            const edge_array<W>& len;
            using base_type::g;
    };

    template<typename W, class Container>
    class WeightedSignedSupportMCB: public WeightedSupportMCB< W, Container>
    {
        public:
            typedef WeightedSupportMCB< W, Container> base_type;

            WeightedSignedSupportMCB( const graph& g_, 
                                const edge_array<W>& len_,
                        array< Container >& mcb_, 
                        array< Container >& proof_,
                        const mcb::edge_num& enumb_ ) 
                : base_type( g_, len_, mcb_, proof_, enumb_ ), sg(g_, len_, enumb_)
            {
            }

        private:

            W computeShortestOddCycle( int k ) { 
                return sg.get_shortest_odd_cycle( S[k], C[k] );
            }

        private:
            detail::WeightedSignedGraph<W,leda::bin_heap> sg;
            using base_type::C;
            using base_type::S;
    };

    template<class Container>
    class UnweightedSignedSupportMCB: public SupportMCB< int, Container >
    {
        public:
            typedef SupportMCB< int, Container> base_type;

            UnweightedSignedSupportMCB( const graph& g_, 
                        array< Container >& mcb_, 
                        array< Container >& proof_,
                        const mcb::edge_num& enumb_ 
                        ) 
                : base_type( g_, mcb_, proof_, enumb_ ), sg( g_, enumb_ )
            {
            }

            ~UnweightedSignedSupportMCB() {}

        private:
            int computeShortestOddCycle( int k ) { 
                return sg.get_shortest_odd_cycle( S[k], C[k] );
            }

            void checkPreconditions() {}

        private:
            detail::UnweightedSignedGraph sg;
            using base_type::C;
            using base_type::S;
    };

    template<typename W, class Container>
    class WeightedHortonSupportMCB: public WeightedSupportMCB<W, Container>
    {
        public:
            typedef WeightedSupportMCB<W, Container> base_type;

            WeightedHortonSupportMCB( const graph& g_, 
                                const edge_array<W>& len_,
                        array< Container >& mcb_, 
                        array< Container >& proof_,
                        const mcb::edge_num& enumb_ ) 
                : base_type( g_, len_, mcb_, proof_, enumb_ ), HS( g_, len_, enumb_ )
            {
            }

        private:

            W computeShortestOddCycle( int k ) { 
                return HS.get_shortest_odd_cycle( S[k], C[k] );
            }

            HortonSuperset<W> HS;
            using base_type::C;
            using base_type::S;
    };

    template<typename W, class Container>
    class WeightedSPTreesSupportMCB: public WeightedSupportMCB<W, Container>
    {
        public:
            typedef WeightedSupportMCB<W, Container> base_type;

            WeightedSPTreesSupportMCB( const graph& g_, 
                                const edge_array<W>& len_,
                        array< Container >& mcb_, 
                        array< Container >& proof_,
                        const mcb::edge_num& enumb_ ) 
                : base_type( g_, len_, mcb_, proof_, enumb_ ), uhst( g_, len_, enumb_ )
            {
            }

        private:

            W computeShortestOddCycle( int k ) { 
                uhst.updateTreeLabels( S[k] );
                return uhst.getShortestOddCycle( S[k], C[k] );
            }

            UndirectedHortonSupersetTrees<W> uhst;
            using base_type::C;
            using base_type::S;
    };




    template<class Container>
        int UMCB_SVA( const graph& g,
                array< Container >& mcb,
                array< Container >& proof,
                const mcb::edge_num& enumb
                ) 
        {
        UnweightedSignedSupportMCB<Container> tmp( g, mcb, proof, enumb );
        return tmp.run();
        }

    template<class Container>
    int UMCB_SVA( const graph& g, 
        array< Container >& mcb, 
        const mcb::edge_num& enumb
        )
    {
        array< Container > proof;
        return UMCB_SVA( g, mcb, proof, enumb );
    }

    template<class W, class Container>
        W UMCB_SVA( const graph& g,
                const edge_array<W>& len,
                array< Container >& mcb,
                array< Container >& proof,
                const mcb::edge_num& enumb
                ) 
        { 
        WeightedSignedSupportMCB<W,Container> tmp( g, len, mcb, proof, enumb );
        return tmp.run();
    }

    template<class W, class Container>
        W UMCB_SVA( const graph& g,
                const edge_array<W>& len,
                array< Container >& mcb,
                const mcb::edge_num& enumb
                ) 
        { 
                array< Container > proof;
        WeightedSignedSupportMCB<W,Container> tmp( g, len, mcb, proof, enumb );
        return tmp.run();
    }

    extern int UMCB_HYBRID( const leda::graph& g,
            leda::array< leda::d_int_set >& mcb,
            leda::array< leda::d_int_set >& proof,
            const mcb::edge_num& enumb
            );

    extern int UMCB_HYBRID( const leda::graph& g,
            leda::array< leda::d_int_set >& mcb,
            const mcb::edge_num& enumb
            );


    template<class W>
        W UMCB_HYBRID( const graph& g,
                const edge_array<W>& len,
                array< d_int_set >& mcb,
                array< d_int_set >& proof,
                const mcb::edge_num& enumb
                ) 
        { 
            WeightedHortonSupportMCB<W, d_int_set> tmp( g, len, mcb, proof, enumb );  
            return tmp.run();
        }


    template<class W>
        W UMCB_HYBRID( const graph& g,
                const edge_array<W>& len,
                array< d_int_set >& mcb,
                const mcb::edge_num& enumb
                )
        {
            array< d_int_set > proof_temp;
            return UMCB_HYBRID( g, len, mcb, proof_temp, enumb );
        }

    template<class W>
    W UMCB_FH( const graph& g, 
                const edge_array<W>& len,
                array< mcb::spvecgf2 >& mcb, 
                array< mcb::spvecgf2 >& proof, 
                const mcb::edge_num& enumb ) 
    { 
        WeightedSPTreesSupportMCB<W,mcb::spvecgf2> tmp( g, len, mcb, proof, enumb );
        return tmp.run();
    }

    template<class W>
    W UMCB_FH( const graph& g, 
                const edge_array<W>& len,
                array< mcb::spvecgf2 >& mcb, 
                const mcb::edge_num& enumb ) 
    { 
        array< mcb::spvecgf2 > proof;
        WeightedSPTreesSupportMCB<W,mcb::spvecgf2> tmp( g, len, mcb, proof, enumb );
        return tmp.run();
    }


} // namespace mcb end

#endif  // UMCB_H

/* ex: set ts=4 sw=4 sts=4 et: */