libDAI
|
00001 /* This file is part of libDAI - http://www.libdai.org/ 00002 * 00003 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved. 00004 * 00005 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file. 00006 */ 00007 00008 00011 00012 00013 #ifndef __defined_libdai_bipgraph_h 00014 #define __defined_libdai_bipgraph_h 00015 00016 00017 #include <ostream> 00018 #include <vector> 00019 #include <algorithm> 00020 #include <dai/util.h> 00021 #include <dai/smallset.h> 00022 #include <dai/exceptions.h> 00023 #include <dai/graph.h> 00024 00025 00026 namespace dai { 00027 00028 00030 00045 class BipartiteGraph { 00046 private: 00048 std::vector<Neighbors> _nb1; 00049 00051 std::vector<Neighbors> _nb2; 00052 00054 struct levelType { 00056 std::vector<size_t> ind1; 00058 std::vector<size_t> ind2; 00059 }; 00060 00061 public: 00063 00064 00065 BipartiteGraph() : _nb1(), _nb2() {} 00066 00068 BipartiteGraph( size_t nr1, size_t nr2 ) : _nb1(nr1), _nb2(nr2) {} 00069 00071 00078 template<typename EdgeInputIterator> 00079 BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb1(), _nb2() { 00080 construct( nrNodes1, nrNodes2, begin, end, check ); 00081 } 00083 00085 00086 00087 const Neighbor & nb1( size_t i1, size_t _i2 ) const { 00088 DAI_DEBASSERT( i1 < _nb1.size() ); 00089 DAI_DEBASSERT( _i2 < _nb1[i1].size() ); 00090 return _nb1[i1][_i2]; 00091 } 00093 Neighbor & nb1( size_t i1, size_t _i2 ) { 00094 DAI_DEBASSERT( i1 < _nb1.size() ); 00095 DAI_DEBASSERT( _i2 < _nb1[i1].size() ); 00096 return _nb1[i1][_i2]; 00097 } 00098 00100 const Neighbor & nb2( size_t i2, size_t _i1 ) const { 00101 DAI_DEBASSERT( i2 < _nb2.size() ); 00102 DAI_DEBASSERT( _i1 < _nb2[i2].size() ); 00103 return _nb2[i2][_i1]; 00104 } 00106 Neighbor & nb2( size_t i2, size_t _i1 ) { 00107 DAI_DEBASSERT( i2 < _nb2.size() ); 00108 DAI_DEBASSERT( _i1 < _nb2[i2].size() ); 00109 return _nb2[i2][_i1]; 00110 } 00111 00113 const Neighbors & nb1( size_t i1 ) const { 00114 DAI_DEBASSERT( i1 < _nb1.size() ); 00115 return _nb1[i1]; 00116 } 00118 Neighbors & nb1( size_t i1 ) { 00119 DAI_DEBASSERT( i1 < _nb1.size() ); 00120 return _nb1[i1]; 00121 } 00122 00124 const Neighbors & nb2( size_t i2 ) const { 00125 DAI_DEBASSERT( i2 < _nb2.size() ); 00126 return _nb2[i2]; 00127 } 00129 Neighbors & nb2( size_t i2 ) { 00130 DAI_DEBASSERT( i2 < _nb2.size() ); 00131 return _nb2[i2]; 00132 } 00134 00136 00137 00138 00145 template<typename EdgeInputIterator> 00146 void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ); 00147 00149 size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; } 00150 00152 size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; } 00153 00154 00156 00162 template <typename NodeInputIterator> 00163 size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) { 00164 Neighbors nbs1new; 00165 nbs1new.reserve( sizeHint ); 00166 size_t iter = 0; 00167 for( NodeInputIterator it = begin; it != end; ++it ) { 00168 DAI_ASSERT( *it < nrNodes2() ); 00169 Neighbor nb1new( iter, *it, nb2(*it).size() ); 00170 Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ ); 00171 nbs1new.push_back( nb1new ); 00172 nb2( *it ).push_back( nb2new ); 00173 } 00174 _nb1.push_back( nbs1new ); 00175 return _nb1.size() - 1; 00176 } 00177 00179 00185 template <typename NodeInputIterator> 00186 size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) { 00187 Neighbors nbs2new; 00188 nbs2new.reserve( sizeHint ); 00189 size_t iter = 0; 00190 for( NodeInputIterator it = begin; it != end; ++it ) { 00191 DAI_ASSERT( *it < nrNodes1() ); 00192 Neighbor nb2new( iter, *it, nb1(*it).size() ); 00193 Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ ); 00194 nbs2new.push_back( nb2new ); 00195 nb1( *it ).push_back( nb1new ); 00196 } 00197 _nb2.push_back( nbs2new ); 00198 return _nb2.size() - 1; 00199 } 00200 00202 00204 BipartiteGraph& addEdge( size_t n1, size_t n2, bool check = true ); 00206 00208 00209 00210 void eraseNode1( size_t n1 ); 00211 00213 void eraseNode2( size_t n2 ); 00214 00216 void eraseEdge( size_t n1, size_t n2 ); 00218 00220 00221 00222 size_t nrNodes1() const { return _nb1.size(); } 00224 size_t nrNodes2() const { return _nb2.size(); } 00225 00227 size_t nrEdges() const { 00228 size_t sum = 0; 00229 for( size_t i1 = 0; i1 < nrNodes1(); i1++ ) 00230 sum += nb1(i1).size(); 00231 return sum; 00232 } 00233 00235 00237 bool hasEdge( size_t n1, size_t n2 ) const { 00238 if( nb1(n1).size() < nb2(n2).size() ) { 00239 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ ) 00240 if( nb1( n1, _n2 ) == n2 ) 00241 return true; 00242 } else { 00243 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ ) 00244 if( nb2( n2, _n1 ) == n1 ) 00245 return true; 00246 } 00247 return false; 00248 } 00249 00251 00254 size_t findNb1( size_t n1, size_t n2 ) { 00255 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ ) 00256 if( nb1( n1, _n2 ) == n2 ) 00257 return _n2; 00258 DAI_THROW(OBJECT_NOT_FOUND); 00259 return nb1(n1).size(); 00260 } 00261 00263 00266 size_t findNb2( size_t n1, size_t n2 ) { 00267 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ ) 00268 if( nb2( n2, _n1 ) == n1 ) 00269 return _n1; 00270 DAI_THROW(OBJECT_NOT_FOUND); 00271 return nb2(n2).size(); 00272 } 00273 00275 SmallSet<size_t> nb1Set( size_t n1 ) const; 00276 00278 SmallSet<size_t> nb2Set( size_t n2 ) const; 00279 00281 00284 SmallSet<size_t> delta1( size_t n1, bool include = false ) const; 00285 00287 00290 SmallSet<size_t> delta2( size_t n2, bool include = false ) const; 00291 00293 bool isConnected() const; 00294 00296 bool isTree() const; 00297 00299 00303 bool operator==( const BipartiteGraph& x ) const { 00304 if( nrNodes1() != x.nrNodes1() ) 00305 return false; 00306 if( nrNodes2() != x.nrNodes2() ) 00307 return false; 00308 for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) { 00309 if( nb1(n1).size() != x.nb1(n1).size() ) 00310 return false; 00311 foreach( const Neighbor &n2, nb1(n1) ) 00312 if( !x.hasEdge( n1, n2 ) ) 00313 return false; 00314 foreach( const Neighbor &n2, x.nb1(n1) ) 00315 if( !hasEdge( n1, n2 ) ) 00316 return false; 00317 } 00318 return true; 00319 } 00320 00322 void checkConsistency() const; 00324 00326 00327 00328 void printDot( std::ostream& os ) const; 00329 00331 friend std::ostream& operator<<( std::ostream& os, const BipartiteGraph& g ) { 00332 g.printDot( os ); 00333 return os; 00334 } 00336 }; 00337 00338 00339 template<typename EdgeInputIterator> 00340 void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check ) { 00341 _nb1.clear(); 00342 _nb1.resize( nrNodes1 ); 00343 _nb2.clear(); 00344 _nb2.resize( nrNodes2 ); 00345 00346 for( EdgeInputIterator e = begin; e != end; e++ ) 00347 addEdge( e->first, e->second, check ); 00348 } 00349 00350 00351 } // end of namespace dai 00352 00353 00389 #endif