00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00014
00015
00016 #ifndef __defined_libdai_bipgraph_h
00017 #define __defined_libdai_bipgraph_h
00018
00019
00020 #include <ostream>
00021 #include <vector>
00022 #include <algorithm>
00023 #include <dai/util.h>
00024 #include <dai/smallset.h>
00025 #include <dai/exceptions.h>
00026 #include <dai/graph.h>
00027
00028
00029 namespace dai {
00030
00031
00033
00048 class BipartiteGraph {
00049 private:
00051 std::vector<Neighbors> _nb1;
00052
00054 std::vector<Neighbors> _nb2;
00055
00057 struct levelType {
00059 std::vector<size_t> ind1;
00061 std::vector<size_t> ind2;
00062 };
00063
00064 public:
00066
00067
00068 BipartiteGraph() : _nb1(), _nb2() {}
00069
00071 BipartiteGraph( size_t nr1, size_t nr2 ) : _nb1(nr1), _nb2(nr2) {}
00072
00074
00081 template<typename EdgeInputIterator>
00082 BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb1(), _nb2() {
00083 construct( nrNodes1, nrNodes2, begin, end, check );
00084 }
00086
00088
00089
00090 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
00091 DAI_DEBASSERT( i1 < _nb1.size() );
00092 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
00093 return _nb1[i1][_i2];
00094 }
00096 Neighbor & nb1( size_t i1, size_t _i2 ) {
00097 DAI_DEBASSERT( i1 < _nb1.size() );
00098 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
00099 return _nb1[i1][_i2];
00100 }
00101
00103 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
00104 DAI_DEBASSERT( i2 < _nb2.size() );
00105 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
00106 return _nb2[i2][_i1];
00107 }
00109 Neighbor & nb2( size_t i2, size_t _i1 ) {
00110 DAI_DEBASSERT( i2 < _nb2.size() );
00111 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
00112 return _nb2[i2][_i1];
00113 }
00114
00116 const Neighbors & nb1( size_t i1 ) const {
00117 DAI_DEBASSERT( i1 < _nb1.size() );
00118 return _nb1[i1];
00119 }
00121 Neighbors & nb1( size_t i1 ) {
00122 DAI_DEBASSERT( i1 < _nb1.size() );
00123 return _nb1[i1];
00124 }
00125
00127 const Neighbors & nb2( size_t i2 ) const {
00128 DAI_DEBASSERT( i2 < _nb2.size() );
00129 return _nb2[i2];
00130 }
00132 Neighbors & nb2( size_t i2 ) {
00133 DAI_DEBASSERT( i2 < _nb2.size() );
00134 return _nb2[i2];
00135 }
00137
00139
00140
00141
00148 template<typename EdgeInputIterator>
00149 void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
00150
00152 size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
00153
00155 size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
00156
00157
00159
00165 template <typename NodeInputIterator>
00166 size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
00167 Neighbors nbs1new;
00168 nbs1new.reserve( sizeHint );
00169 size_t iter = 0;
00170 for( NodeInputIterator it = begin; it != end; ++it ) {
00171 DAI_ASSERT( *it < nrNodes2() );
00172 Neighbor nb1new( iter, *it, nb2(*it).size() );
00173 Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
00174 nbs1new.push_back( nb1new );
00175 nb2( *it ).push_back( nb2new );
00176 }
00177 _nb1.push_back( nbs1new );
00178 return _nb1.size() - 1;
00179 }
00180
00182
00188 template <typename NodeInputIterator>
00189 size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
00190 Neighbors nbs2new;
00191 nbs2new.reserve( sizeHint );
00192 size_t iter = 0;
00193 for( NodeInputIterator it = begin; it != end; ++it ) {
00194 DAI_ASSERT( *it < nrNodes1() );
00195 Neighbor nb2new( iter, *it, nb1(*it).size() );
00196 Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
00197 nbs2new.push_back( nb2new );
00198 nb1( *it ).push_back( nb1new );
00199 }
00200 _nb2.push_back( nbs2new );
00201 return _nb2.size() - 1;
00202 }
00203
00205
00207 BipartiteGraph& addEdge( size_t n1, size_t n2, bool check = true );
00209
00211
00212
00213 void eraseNode1( size_t n1 );
00214
00216 void eraseNode2( size_t n2 );
00217
00219 void eraseEdge( size_t n1, size_t n2 );
00221
00223
00224
00225 size_t nrNodes1() const { return _nb1.size(); }
00227 size_t nrNodes2() const { return _nb2.size(); }
00228
00230 size_t nrEdges() const {
00231 size_t sum = 0;
00232 for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
00233 sum += nb1(i1).size();
00234 return sum;
00235 }
00236
00238
00240 bool hasEdge( size_t n1, size_t n2 ) const {
00241 if( nb1(n1).size() < nb2(n2).size() ) {
00242 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
00243 if( nb1( n1, _n2 ) == n2 )
00244 return true;
00245 } else {
00246 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
00247 if( nb2( n2, _n1 ) == n1 )
00248 return true;
00249 }
00250 return false;
00251 }
00252
00254
00257 size_t findNb1( size_t n1, size_t n2 ) {
00258 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
00259 if( nb1( n1, _n2 ) == n2 )
00260 return _n2;
00261 DAI_THROW(OBJECT_NOT_FOUND);
00262 return nb1(n1).size();
00263 }
00264
00266
00269 size_t findNb2( size_t n1, size_t n2 ) {
00270 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
00271 if( nb2( n2, _n1 ) == n1 )
00272 return _n1;
00273 DAI_THROW(OBJECT_NOT_FOUND);
00274 return nb2(n2).size();
00275 }
00276
00278 SmallSet<size_t> nb1Set( size_t n1 ) const;
00279
00281 SmallSet<size_t> nb2Set( size_t n2 ) const;
00282
00284
00287 SmallSet<size_t> delta1( size_t n1, bool include = false ) const;
00288
00290
00293 SmallSet<size_t> delta2( size_t n2, bool include = false ) const;
00294
00296 bool isConnected() const;
00297
00299 bool isTree() const;
00300
00302
00306 bool operator==( const BipartiteGraph& x ) const {
00307 if( nrNodes1() != x.nrNodes1() )
00308 return false;
00309 if( nrNodes2() != x.nrNodes2() )
00310 return false;
00311 for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
00312 if( nb1(n1).size() != x.nb1(n1).size() )
00313 return false;
00314 foreach( const Neighbor &n2, nb1(n1) )
00315 if( !x.hasEdge( n1, n2 ) )
00316 return false;
00317 foreach( const Neighbor &n2, x.nb1(n1) )
00318 if( !hasEdge( n1, n2 ) )
00319 return false;
00320 }
00321 return true;
00322 }
00323
00325 void checkConsistency() const;
00327
00329
00330
00331 void printDot( std::ostream& os ) const;
00332
00334 friend std::ostream& operator<<( std::ostream& os, const BipartiteGraph& g ) {
00335 g.printDot( os );
00336 return os;
00337 }
00339 };
00340
00341
00342 template<typename EdgeInputIterator>
00343 void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
00344 _nb1.clear();
00345 _nb1.resize( nrNodes1 );
00346 _nb2.clear();
00347 _nb2.resize( nrNodes2 );
00348
00349 for( EdgeInputIterator e = begin; e != end; e++ )
00350 addEdge( e->first, e->second, check );
00351 }
00352
00353
00354 }
00355
00356
00392 #endif