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_dag_h 00014 #define __defined_libdai_dag_h 00015 00016 00017 #include <ostream> 00018 #include <vector> 00019 #include <algorithm> 00020 #include <dai/util.h> 00021 #include <dai/exceptions.h> 00022 #include <dai/smallset.h> 00023 #include <dai/graph.h> 00024 00025 00026 namespace dai { 00027 00028 00030 00041 class DAG { 00042 private: 00044 std::vector<Neighbors> _pa; 00045 00047 std::vector<Neighbors> _ch; 00048 00049 public: 00051 00052 00053 DAG() : _pa(), _ch() {} 00054 00056 DAG( size_t nr ) : _pa( nr ), _ch( nr ) {} 00057 00059 00066 template<typename EdgeInputIterator> 00067 DAG( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _pa(), _ch() { 00068 construct( nr, begin, end, check ); 00069 } 00071 00073 00074 00075 const Neighbor& pa( size_t n, size_t _p ) const { 00076 DAI_DEBASSERT( n < _pa.size() ); 00077 DAI_DEBASSERT( _p < _pa[n].size() ); 00078 return _pa[n][_p]; 00079 } 00081 Neighbor& pa( size_t n, size_t _p ) { 00082 DAI_DEBASSERT( n < _pa.size() ); 00083 DAI_DEBASSERT( _p < _pa[n].size() ); 00084 return _pa[n][_p]; 00085 } 00086 00088 const Neighbors& pa( size_t n ) const { 00089 DAI_DEBASSERT( n < _pa.size() ); 00090 return _pa[n]; 00091 } 00093 Neighbors& pa( size_t n ) { 00094 DAI_DEBASSERT( n < _pa.size() ); 00095 return _pa[n]; 00096 } 00097 00099 const Neighbor& ch( size_t n, size_t _c ) const { 00100 DAI_DEBASSERT( n < _ch.size() ); 00101 DAI_DEBASSERT( _c < _ch[n].size() ); 00102 return _ch[n][_c]; 00103 } 00105 Neighbor& ch( size_t n, size_t _c ) { 00106 DAI_DEBASSERT( n < _ch.size() ); 00107 DAI_DEBASSERT( _c < _ch[n].size() ); 00108 return _ch[n][_c]; 00109 } 00110 00112 const Neighbors& ch( size_t n ) const { 00113 DAI_DEBASSERT( n < _ch.size() ); 00114 return _ch[n]; 00115 } 00117 Neighbors& ch( size_t n ) { 00118 DAI_DEBASSERT( n < _ch.size() ); 00119 return _ch[n]; 00120 } 00122 00124 00125 00126 00132 template<typename EdgeInputIterator> 00133 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ); 00134 00136 size_t addNode() { 00137 _pa.push_back( Neighbors() ); 00138 _ch.push_back( Neighbors() ); 00139 return _pa.size() - 1; 00140 } 00141 00143 00149 template <typename NodeInputIterator> 00150 size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0 ) { 00151 Neighbors newparents; 00152 newparents.reserve( sizeHint ); 00153 size_t iter = 0; 00154 for( NodeInputIterator it = begin; it != end; ++it ) { 00155 DAI_ASSERT( *it < nrNodes() ); 00156 Neighbor newparent( iter, *it, ch(*it).size() ); 00157 Neighbor newchild( ch(*it).size(), nrNodes(), iter++ ); 00158 newparents.push_back( newparent ); 00159 ch( *it ).push_back( newchild ); 00160 } 00161 _pa.push_back( newparents ); 00162 _ch.push_back( Neighbors() ); 00163 return _pa.size() - 1; 00164 } 00165 00167 00169 DAG& addEdge( size_t n1, size_t n2, bool check=true ); 00171 00173 00174 00175 void eraseNode( size_t n ); 00176 00178 void eraseEdge( size_t n1, size_t n2 ); 00180 00182 00183 00184 size_t nrNodes() const { 00185 DAI_DEBASSERT( _pa.size() == _ch.size() ); 00186 return _pa.size(); 00187 } 00188 00190 size_t nrEdges() const { 00191 size_t sum = 0; 00192 for( size_t i = 0; i < _pa.size(); i++ ) 00193 sum += _pa[i].size(); 00194 return sum; 00195 } 00196 00198 00200 bool hasEdge( size_t n1, size_t n2 ) const { 00201 if( ch(n1).size() < pa(n2).size() ) { 00202 for( size_t _n2 = 0; _n2 < ch(n1).size(); _n2++ ) 00203 if( ch( n1, _n2 ) == n2 ) 00204 return true; 00205 } else { 00206 for( size_t _n1 = 0; _n1 < pa(n2).size(); _n1++ ) 00207 if( pa( n2, _n1 ) == n1 ) 00208 return true; 00209 } 00210 return false; 00211 } 00212 00214 00217 size_t findPa( size_t n, size_t p ) { 00218 for( size_t _p = 0; _p < pa(n).size(); _p++ ) 00219 if( pa( n, _p ) == p ) 00220 return _p; 00221 DAI_THROW(OBJECT_NOT_FOUND); 00222 return pa(n).size(); 00223 } 00224 00226 00229 size_t findCh( size_t n, size_t c ) { 00230 for( size_t _c = 0; _c < ch(n).size(); _c++ ) 00231 if( ch( n, _c ) == c ) 00232 return _c; 00233 DAI_THROW(OBJECT_NOT_FOUND); 00234 return ch(n).size(); 00235 } 00236 00238 SmallSet<size_t> paSet( size_t n ) const; 00239 00241 SmallSet<size_t> chSet( size_t n ) const; 00242 00244 std::set<size_t> ancestors( size_t n ) const; 00245 00247 std::set<size_t> descendants( size_t n ) const; 00248 00250 bool existsDirectedPath( size_t n1, size_t n2 ) const; 00251 00253 bool isConnected() const; 00254 00256 void checkConsistency() const; 00257 00259 00263 bool operator==( const DAG& x ) const { 00264 if( nrNodes() != x.nrNodes() ) 00265 return false; 00266 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) { 00267 if( pa(n1).size() != x.pa(n1).size() ) 00268 return false; 00269 foreach( const Neighbor &n2, pa(n1) ) 00270 if( !x.hasEdge( n2, n1 ) ) 00271 return false; 00272 foreach( const Neighbor &n2, x.pa(n1) ) 00273 if( !hasEdge( n2, n1 ) ) 00274 return false; 00275 } 00276 return true; 00277 } 00279 00281 00282 00283 void printDot( std::ostream& os ) const; 00284 00286 friend std::ostream& operator<<( std::ostream& os, const DAG& g ) { 00287 g.printDot( os ); 00288 return os; 00289 } 00291 }; 00292 00293 00294 template<typename EdgeInputIterator> 00295 void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) { 00296 _pa.clear(); 00297 _pa.resize( nr ); 00298 _ch.clear(); 00299 _ch.resize( nr ); 00300 00301 for( EdgeInputIterator e = begin; e != end; e++ ) 00302 addEdge( e->first, e->second, check ); 00303 } 00304 00305 00306 } // end of namespace dai 00307 00308 00309 #endif