bipgraph.h

Go to the documentation of this file.

/*  This file is part of libDAI - http://www.libdai.org/
 *
 *  Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
 *
 *  Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
 */




#ifndef __defined_libdai_bipgraph_h
#define __defined_libdai_bipgraph_h


#include <ostream>
#include <vector>
#include <algorithm>
#include <dai/util.h>
#include <dai/smallset.h>
#include <dai/exceptions.h>
#include <dai/graph.h>


namespace dai {



class BipartiteGraph {
    private:
        std::vector<Neighbors> _nb1;

        std::vector<Neighbors> _nb2;

        struct levelType {
            std::vector<size_t> ind1;       
            std::vector<size_t> ind2;
        };

    public:

        BipartiteGraph() : _nb1(), _nb2() {}

        BipartiteGraph( size_t nr1, size_t nr2 ) : _nb1(nr1), _nb2(nr2) {}


        template<typename EdgeInputIterator>
        BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb1(), _nb2() {
            construct( nrNodes1, nrNodes2, begin, end, check );
        }


        const Neighbor & nb1( size_t i1, size_t _i2 ) const {
            DAI_DEBASSERT( i1 < _nb1.size() );
            DAI_DEBASSERT( _i2 < _nb1[i1].size() );
            return _nb1[i1][_i2];
        }
        Neighbor & nb1( size_t i1, size_t _i2 ) {
            DAI_DEBASSERT( i1 < _nb1.size() );
            DAI_DEBASSERT( _i2 < _nb1[i1].size() );
            return _nb1[i1][_i2];
        }

        const Neighbor & nb2( size_t i2, size_t _i1 ) const {
            DAI_DEBASSERT( i2 < _nb2.size() );
            DAI_DEBASSERT( _i1 < _nb2[i2].size() );
            return _nb2[i2][_i1];
        }
        Neighbor & nb2( size_t i2, size_t _i1 ) {
            DAI_DEBASSERT( i2 < _nb2.size() );
            DAI_DEBASSERT( _i1 < _nb2[i2].size() );
            return _nb2[i2][_i1];
        }

        const Neighbors & nb1( size_t i1 ) const {
            DAI_DEBASSERT( i1 < _nb1.size() );
            return _nb1[i1];
        }
        Neighbors & nb1( size_t i1 ) {
            DAI_DEBASSERT( i1 < _nb1.size() );
            return _nb1[i1];
        }

        const Neighbors & nb2( size_t i2 ) const {
            DAI_DEBASSERT( i2 < _nb2.size() );
            return _nb2[i2];
        }
        Neighbors & nb2( size_t i2 ) {
            DAI_DEBASSERT( i2 < _nb2.size() );
            return _nb2[i2];
        }



        template<typename EdgeInputIterator>
        void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );

        size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }

        size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }



        template <typename NodeInputIterator>
        size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
            Neighbors nbs1new;
            nbs1new.reserve( sizeHint );
            size_t iter = 0;
            for( NodeInputIterator it = begin; it != end; ++it ) {
                DAI_ASSERT( *it < nrNodes2() );
                Neighbor nb1new( iter, *it, nb2(*it).size() );
                Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
                nbs1new.push_back( nb1new );
                nb2( *it ).push_back( nb2new );
            }
            _nb1.push_back( nbs1new );
            return _nb1.size() - 1;
        }


        template <typename NodeInputIterator>
        size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
            Neighbors nbs2new;
            nbs2new.reserve( sizeHint );
            size_t iter = 0;
            for( NodeInputIterator it = begin; it != end; ++it ) {
                DAI_ASSERT( *it < nrNodes1() );
                Neighbor nb2new( iter, *it, nb1(*it).size() );
                Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
                nbs2new.push_back( nb2new );
                nb1( *it ).push_back( nb1new );
            }
            _nb2.push_back( nbs2new );
            return _nb2.size() - 1;
        }


        BipartiteGraph& addEdge( size_t n1, size_t n2, bool check = true );


        void eraseNode1( size_t n1 );

        void eraseNode2( size_t n2 );

        void eraseEdge( size_t n1, size_t n2 );


        size_t nrNodes1() const { return _nb1.size(); }
        size_t nrNodes2() const { return _nb2.size(); }

        size_t nrEdges() const {
            size_t sum = 0;
            for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
                sum += nb1(i1).size();
            return sum;
        }


        bool hasEdge( size_t n1, size_t n2 ) const {
            if( nb1(n1).size() < nb2(n2).size() ) {
                for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
                    if( nb1( n1, _n2 ) == n2 )
                        return true;
            } else {
                for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
                    if( nb2( n2, _n1 ) == n1 )
                        return true;
            }
            return false;
        }


        size_t findNb1( size_t n1, size_t n2 ) {
            for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
                if( nb1( n1, _n2 ) == n2 )
                    return _n2;
            DAI_THROW(OBJECT_NOT_FOUND);
            return nb1(n1).size();
        }


        size_t findNb2( size_t n1, size_t n2 ) {
            for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
                if( nb2( n2, _n1 ) == n1 )
                    return _n1;
            DAI_THROW(OBJECT_NOT_FOUND);
            return nb2(n2).size();
        }

        SmallSet<size_t> nb1Set( size_t n1 ) const;

        SmallSet<size_t> nb2Set( size_t n2 ) const;


        SmallSet<size_t> delta1( size_t n1, bool include = false ) const;


        SmallSet<size_t> delta2( size_t n2, bool include = false ) const;

        bool isConnected() const;

        bool isTree() const;


        bool operator==( const BipartiteGraph& x ) const {
            if( nrNodes1() != x.nrNodes1() )
                return false;
            if( nrNodes2() != x.nrNodes2() )
                return false;
            for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
                if( nb1(n1).size() != x.nb1(n1).size() )
                    return false;
                bforeach( const Neighbor &n2, nb1(n1) )
                    if( !x.hasEdge( n1, n2 ) )
                        return false;
                bforeach( const Neighbor &n2, x.nb1(n1) )
                    if( !hasEdge( n1, n2 ) )
                        return false;
            }
            return true;
        }

        void checkConsistency() const;


        void printDot( std::ostream& os ) const;

        friend std::ostream& operator<<( std::ostream& os, const BipartiteGraph& g ) {
            g.printDot( os );
            return os;
        }

        std::string toString() const {
            std::stringstream ss;
            ss << *this;
            return ss.str();
        }
};


template<typename EdgeInputIterator>
void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
    _nb1.clear();
    _nb1.resize( nrNodes1 );
    _nb2.clear();
    _nb2.resize( nrNodes2 );

    for( EdgeInputIterator e = begin; e != end; e++ )
        addEdge( e->first, e->second, check );
}


} // end of namespace dai


#endif