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/exceptions.h>
00025
00026
00027 namespace dai {
00028
00029
00031
00046 class BipartiteGraph {
00047 public:
00049
00104 struct Neighbor {
00106 size_t iter;
00108 size_t node;
00110 size_t dual;
00111
00113 Neighbor() {}
00115 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
00116
00118 operator size_t () const { return node; }
00119 };
00120
00122 typedef std::vector<Neighbor> Neighbors;
00123
00125 typedef std::pair<size_t,size_t> Edge;
00126
00127 private:
00129 std::vector<Neighbors> _nb1;
00130
00132 std::vector<Neighbors> _nb2;
00133
00135 struct levelType {
00137 std::vector<size_t> ind1;
00139 std::vector<size_t> ind2;
00140 };
00141
00142 public:
00144
00145
00146 BipartiteGraph() : _nb1(), _nb2() {}
00147
00149
00155 template<typename EdgeInputIterator>
00156 BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1(), _nb2() {
00157 construct( nrNodes1, nrNodes2, begin, end );
00158 }
00160
00162
00163
00164 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
00165 DAI_DEBASSERT( i1 < _nb1.size() );
00166 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
00167 return _nb1[i1][_i2];
00168 }
00170 Neighbor & nb1( size_t i1, size_t _i2 ) {
00171 DAI_DEBASSERT( i1 < _nb1.size() );
00172 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
00173 return _nb1[i1][_i2];
00174 }
00175
00177 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
00178 DAI_DEBASSERT( i2 < _nb2.size() );
00179 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
00180 return _nb2[i2][_i1];
00181 }
00183 Neighbor & nb2( size_t i2, size_t _i1 ) {
00184 DAI_DEBASSERT( i2 < _nb2.size() );
00185 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
00186 return _nb2[i2][_i1];
00187 }
00188
00190 const Neighbors & nb1( size_t i1 ) const {
00191 DAI_DEBASSERT( i1 < _nb1.size() );
00192 return _nb1[i1];
00193 }
00195 Neighbors & nb1( size_t i1 ) {
00196 DAI_DEBASSERT( i1 < _nb1.size() );
00197 return _nb1[i1];
00198 }
00199
00201 const Neighbors & nb2( size_t i2 ) const {
00202 DAI_DEBASSERT( i2 < _nb2.size() );
00203 return _nb2[i2];
00204 }
00206 Neighbors & nb2( size_t i2 ) {
00207 DAI_DEBASSERT( i2 < _nb2.size() );
00208 return _nb2[i2];
00209 }
00211
00213
00214
00215
00221 template<typename EdgeInputIterator>
00222 void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end );
00223
00225 size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
00226
00228 size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
00229
00230
00232
00234 size_t add1() { return addNode1(); }
00235
00237
00239 size_t add2() { return addNode2(); }
00240
00242
00248 template <typename NodeInputIterator>
00249 size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
00250 Neighbors nbs1new;
00251 nbs1new.reserve( sizeHint );
00252 size_t iter = 0;
00253 for( NodeInputIterator it = begin; it != end; ++it ) {
00254 DAI_ASSERT( *it < nrNodes2() );
00255 Neighbor nb1new( iter, *it, nb2(*it).size() );
00256 Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
00257 nbs1new.push_back( nb1new );
00258 nb2( *it ).push_back( nb2new );
00259 }
00260 _nb1.push_back( nbs1new );
00261 return _nb1.size() - 1;
00262 }
00263
00265
00271 template <typename NodeInputIterator>
00272 size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
00273 Neighbors nbs2new;
00274 nbs2new.reserve( sizeHint );
00275 size_t iter = 0;
00276 for( NodeInputIterator it = begin; it != end; ++it ) {
00277 DAI_ASSERT( *it < nrNodes1() );
00278 Neighbor nb2new( iter, *it, nb1(*it).size() );
00279 Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
00280 nbs2new.push_back( nb2new );
00281 nb1( *it ).push_back( nb1new );
00282 }
00283 _nb2.push_back( nbs2new );
00284 return _nb2.size() - 1;
00285 }
00286
00288
00290 template <typename NodeInputIterator>
00291 size_t add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
00292 return addNode1( begin, end, sizeHint );
00293 }
00294
00296
00298 template <typename NodeInputIterator>
00299 size_t add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
00300 return addNode2( begin, end, sizeHint );
00301 }
00302
00304
00306 void addEdge( size_t n1, size_t n2, bool check = true );
00308
00310
00311
00312 void eraseNode1( size_t n1 );
00313
00315 void eraseNode2( size_t n2 );
00316
00318
00320 void erase1( size_t n1 ) { eraseNode1( n1 ); }
00321
00323
00325 void erase2( size_t n2 ) { eraseNode2( n2 ); }
00326
00328 void eraseEdge( size_t n1, size_t n2 );
00330
00332
00333
00334 size_t nrNodes1() const { return _nb1.size(); }
00336 size_t nrNodes2() const { return _nb2.size(); }
00337
00339
00341 size_t nr1() const { return nrNodes1(); }
00342
00344
00346 size_t nr2() const { return nrNodes2(); }
00347
00349 size_t nrEdges() const {
00350 size_t sum = 0;
00351 for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
00352 sum += nb1(i1).size();
00353 return sum;
00354 }
00355
00357
00359 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
00360
00362
00364 std::vector<size_t> delta2( size_t n2, bool include = false ) const;
00365
00367 bool isConnected() const;
00368
00370 bool isTree() const;
00371
00373 void checkConsistency() const;
00375
00377
00378
00379 void printDot( std::ostream& os ) const;
00381 };
00382
00383
00384 template<typename EdgeInputIterator>
00385 void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end ) {
00386 _nb1.clear();
00387 _nb1.resize( nrNodes1 );
00388 _nb2.clear();
00389 _nb2.resize( nrNodes2 );
00390
00391 for( EdgeInputIterator e = begin; e != end; e++ ) {
00392 #ifdef DAI_DEBUG
00393 addEdge( e->first, e->second, true );
00394 #else
00395 addEdge( e->first, e->second, false );
00396 #endif
00397 }
00398 }
00399
00400
00401 }
00402
00403
00439 #endif