libDAI
include/dai/dag.h
Go to the documentation of this file.
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