00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00013
00014
00015 #ifndef __defined_libdai_dag_h
00016 #define __defined_libdai_dag_h
00017
00018
00019 #include <ostream>
00020 #include <vector>
00021 #include <algorithm>
00022 #include <dai/util.h>
00023 #include <dai/exceptions.h>
00024 #include <dai/smallset.h>
00025
00026
00027 namespace dai {
00028
00029
00031
00042 class DAG {
00043 public:
00045
00103 struct Neighbor {
00105 size_t iter;
00107 size_t node;
00109 size_t dual;
00110
00112 Neighbor() {}
00114 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
00115
00117 operator size_t () const { return node; }
00118 };
00119
00121 typedef std::vector<Neighbor> Neighbors;
00122
00124 typedef std::pair<size_t,size_t> Edge;
00125
00126 private:
00128 std::vector<Neighbors> _pa;
00129
00131 std::vector<Neighbors> _ch;
00132
00133 public:
00135
00136
00137 DAG() : _pa(), _ch() {}
00138
00140 DAG( size_t nr ) : _pa( nr ), _ch( nr ) {}
00141
00143
00150 template<typename EdgeInputIterator>
00151 DAG( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _pa(), _ch() {
00152 construct( nr, begin, end, check );
00153 }
00155
00157
00158
00159 const Neighbor& pa( size_t n, size_t _p ) const {
00160 DAI_DEBASSERT( n < _pa.size() );
00161 DAI_DEBASSERT( _p < _pa[n].size() );
00162 return _pa[n][_p];
00163 }
00165 Neighbor& pa( size_t n, size_t _p ) {
00166 DAI_DEBASSERT( n < _pa.size() );
00167 DAI_DEBASSERT( _p < _pa[n].size() );
00168 return _pa[n][_p];
00169 }
00170
00172 const Neighbors& pa( size_t n ) const {
00173 DAI_DEBASSERT( n < _pa.size() );
00174 return _pa[n];
00175 }
00177 Neighbors& pa( size_t n ) {
00178 DAI_DEBASSERT( n < _pa.size() );
00179 return _pa[n];
00180 }
00181
00183 const Neighbor& ch( size_t n, size_t _c ) const {
00184 DAI_DEBASSERT( n < _ch.size() );
00185 DAI_DEBASSERT( _c < _ch[n].size() );
00186 return _ch[n][_c];
00187 }
00189 Neighbor& ch( size_t n, size_t _c ) {
00190 DAI_DEBASSERT( n < _ch.size() );
00191 DAI_DEBASSERT( _c < _ch[n].size() );
00192 return _ch[n][_c];
00193 }
00194
00196 const Neighbors& ch( size_t n ) const {
00197 DAI_DEBASSERT( n < _ch.size() );
00198 return _ch[n];
00199 }
00201 Neighbors& ch( size_t n ) {
00202 DAI_DEBASSERT( n < _ch.size() );
00203 return _ch[n];
00204 }
00206
00208
00209
00210
00216 template<typename EdgeInputIterator>
00217 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
00218
00220 size_t addNode() {
00221 _pa.push_back( Neighbors() );
00222 _ch.push_back( Neighbors() );
00223 return _pa.size() - 1;
00224 }
00225
00227
00233 template <typename NodeInputIterator>
00234 size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0 ) {
00235 Neighbors newparents;
00236 newparents.reserve( sizeHint );
00237 size_t iter = 0;
00238 for( NodeInputIterator it = begin; it != end; ++it ) {
00239 DAI_ASSERT( *it < nrNodes() );
00240 Neighbor newparent( iter, *it, ch(*it).size() );
00241 Neighbor newchild( ch(*it).size(), nrNodes(), iter++ );
00242 newparents.push_back( newparent );
00243 ch( *it ).push_back( newchild );
00244 }
00245 _pa.push_back( newparents );
00246 _ch.push_back( Neighbors() );
00247 return _pa.size() - 1;
00248 }
00249
00251
00253 DAG& addEdge( size_t n1, size_t n2, bool check=true );
00255
00257
00258
00259 void eraseNode( size_t n );
00260
00262 void eraseEdge( size_t n1, size_t n2 );
00264
00266
00267
00268 size_t nrNodes() const {
00269 DAI_DEBASSERT( _pa.size() == _ch.size() );
00270 return _pa.size();
00271 }
00272
00274 size_t nrEdges() const {
00275 size_t sum = 0;
00276 for( size_t i = 0; i < _pa.size(); i++ )
00277 sum += _pa[i].size();
00278 return sum;
00279 }
00280
00282
00284 bool hasEdge( size_t n1, size_t n2 ) const {
00285 if( ch(n1).size() < pa(n2).size() ) {
00286 for( size_t _n2 = 0; _n2 < ch(n1).size(); _n2++ )
00287 if( ch( n1, _n2 ) == n2 )
00288 return true;
00289 } else {
00290 for( size_t _n1 = 0; _n1 < pa(n2).size(); _n1++ )
00291 if( pa( n2, _n1 ) == n1 )
00292 return true;
00293 }
00294 return false;
00295 }
00296
00298
00301 size_t findPa( size_t n, size_t p ) {
00302 for( size_t _p = 0; _p < pa(n).size(); _p++ )
00303 if( pa( n, _p ) == p )
00304 return _p;
00305 DAI_THROW(OBJECT_NOT_FOUND);
00306 return pa(n).size();
00307 }
00308
00310
00313 size_t findCh( size_t n, size_t c ) {
00314 for( size_t _c = 0; _c < ch(n).size(); _c++ )
00315 if( ch( n, _c ) == c )
00316 return _c;
00317 DAI_THROW(OBJECT_NOT_FOUND);
00318 return ch(n).size();
00319 }
00320
00322 SmallSet<size_t> paSet( size_t n ) const;
00323
00325 SmallSet<size_t> chSet( size_t n ) const;
00326
00328 std::set<size_t> ancestors( size_t n ) const;
00329
00331 std::set<size_t> descendants( size_t n ) const;
00332
00334 bool existsDirectedPath( size_t n1, size_t n2 ) const;
00335
00337 bool isConnected() const;
00338
00340 void checkConsistency() const;
00341
00343
00347 bool operator==( const DAG& x ) const {
00348 if( nrNodes() != x.nrNodes() )
00349 return false;
00350 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
00351 if( pa(n1).size() != x.pa(n1).size() )
00352 return false;
00353 foreach( const Neighbor &n2, pa(n1) )
00354 if( !x.hasEdge( n2, n1 ) )
00355 return false;
00356 foreach( const Neighbor &n2, x.pa(n1) )
00357 if( !hasEdge( n2, n1 ) )
00358 return false;
00359 }
00360 return true;
00361 }
00363
00365
00366
00367 void printDot( std::ostream& os ) const;
00368
00370 friend std::ostream& operator<<( std::ostream& os, const DAG& g ) {
00371 g.printDot( os );
00372 return os;
00373 }
00375 };
00376
00377
00378 template<typename EdgeInputIterator>
00379 void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
00380 _pa.clear();
00381 _pa.resize( nr );
00382 _ch.clear();
00383 _ch.resize( nr );
00384
00385 for( EdgeInputIterator e = begin; e != end; e++ )
00386 addEdge( e->first, e->second, check );
00387 }
00388
00389
00390 }
00391
00392
00393 #endif