libDAI
dag.h
Go to the documentation of this file.
1 /* This file is part of libDAI - http://www.libdai.org/
2  *
3  * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4  *
5  * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6  */
7 
8 
11 
12 
13 #ifndef __defined_libdai_dag_h
14 #define __defined_libdai_dag_h
15 
16 
17 #include <ostream>
18 #include <vector>
19 #include <algorithm>
20 #include <dai/util.h>
21 #include <dai/exceptions.h>
22 #include <dai/smallset.h>
23 #include <dai/graph.h>
24 
25 
26 namespace dai {
27 
28 
30 
41 class DAG {
42  private:
44  std::vector<Neighbors> _pa;
45 
47  std::vector<Neighbors> _ch;
48 
49  public:
51 
52 
53  DAG() : _pa(), _ch() {}
54 
56  DAG( size_t nr ) : _pa( nr ), _ch( nr ) {}
57 
59 
66  template<typename EdgeInputIterator>
67  DAG( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _pa(), _ch() {
68  construct( nr, begin, end, check );
69  }
71 
73 
74 
75  const Neighbor& pa( size_t n, size_t _p ) const {
76  DAI_DEBASSERT( n < _pa.size() );
77  DAI_DEBASSERT( _p < _pa[n].size() );
78  return _pa[n][_p];
79  }
81  Neighbor& pa( size_t n, size_t _p ) {
82  DAI_DEBASSERT( n < _pa.size() );
83  DAI_DEBASSERT( _p < _pa[n].size() );
84  return _pa[n][_p];
85  }
86 
88  const Neighbors& pa( size_t n ) const {
89  DAI_DEBASSERT( n < _pa.size() );
90  return _pa[n];
91  }
93  Neighbors& pa( size_t n ) {
94  DAI_DEBASSERT( n < _pa.size() );
95  return _pa[n];
96  }
97 
99  const Neighbor& ch( size_t n, size_t _c ) const {
100  DAI_DEBASSERT( n < _ch.size() );
101  DAI_DEBASSERT( _c < _ch[n].size() );
102  return _ch[n][_c];
103  }
105  Neighbor& ch( size_t n, size_t _c ) {
106  DAI_DEBASSERT( n < _ch.size() );
107  DAI_DEBASSERT( _c < _ch[n].size() );
108  return _ch[n][_c];
109  }
110 
112  const Neighbors& ch( size_t n ) const {
113  DAI_DEBASSERT( n < _ch.size() );
114  return _ch[n];
115  }
117  Neighbors& ch( size_t n ) {
118  DAI_DEBASSERT( n < _ch.size() );
119  return _ch[n];
120  }
122 
124 
125 
126 
132  template<typename EdgeInputIterator>
133  void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
134 
136  size_t addNode() {
137  _pa.push_back( Neighbors() );
138  _ch.push_back( Neighbors() );
139  return _pa.size() - 1;
140  }
141 
143 
149  template <typename NodeInputIterator>
150  size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0 ) {
151  Neighbors newparents;
152  newparents.reserve( sizeHint );
153  size_t iter = 0;
154  for( NodeInputIterator it = begin; it != end; ++it ) {
155  DAI_ASSERT( *it < nrNodes() );
156  Neighbor newparent( iter, *it, ch(*it).size() );
157  Neighbor newchild( ch(*it).size(), nrNodes(), iter++ );
158  newparents.push_back( newparent );
159  ch( *it ).push_back( newchild );
160  }
161  _pa.push_back( newparents );
162  _ch.push_back( Neighbors() );
163  return _pa.size() - 1;
164  }
165 
167 
169  DAG& addEdge( size_t n1, size_t n2, bool check=true );
171 
173 
174 
175  void eraseNode( size_t n );
176 
178  void eraseEdge( size_t n1, size_t n2 );
180 
182 
183 
184  size_t nrNodes() const {
185  DAI_DEBASSERT( _pa.size() == _ch.size() );
186  return _pa.size();
187  }
188 
190  size_t nrEdges() const {
191  size_t sum = 0;
192  for( size_t i = 0; i < _pa.size(); i++ )
193  sum += _pa[i].size();
194  return sum;
195  }
196 
198 
200  bool hasEdge( size_t n1, size_t n2 ) const {
201  if( ch(n1).size() < pa(n2).size() ) {
202  for( size_t _n2 = 0; _n2 < ch(n1).size(); _n2++ )
203  if( ch( n1, _n2 ) == n2 )
204  return true;
205  } else {
206  for( size_t _n1 = 0; _n1 < pa(n2).size(); _n1++ )
207  if( pa( n2, _n1 ) == n1 )
208  return true;
209  }
210  return false;
211  }
212 
214 
217  size_t findPa( size_t n, size_t p ) {
218  for( size_t _p = 0; _p < pa(n).size(); _p++ )
219  if( pa( n, _p ) == p )
220  return _p;
221  DAI_THROW(OBJECT_NOT_FOUND);
222  return pa(n).size();
223  }
224 
226 
229  size_t findCh( size_t n, size_t c ) {
230  for( size_t _c = 0; _c < ch(n).size(); _c++ )
231  if( ch( n, _c ) == c )
232  return _c;
233  DAI_THROW(OBJECT_NOT_FOUND);
234  return ch(n).size();
235  }
236 
238  SmallSet<size_t> paSet( size_t n ) const;
239 
241  SmallSet<size_t> chSet( size_t n ) const;
242 
244  std::set<size_t> ancestors( size_t n ) const;
245 
247  std::set<size_t> descendants( size_t n ) const;
248 
250  bool existsDirectedPath( size_t n1, size_t n2 ) const;
251 
253  bool isConnected() const;
254 
256  void checkConsistency() const;
257 
259 
263  bool operator==( const DAG& x ) const {
264  if( nrNodes() != x.nrNodes() )
265  return false;
266  for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
267  if( pa(n1).size() != x.pa(n1).size() )
268  return false;
269  bforeach( const Neighbor &n2, pa(n1) )
270  if( !x.hasEdge( n2, n1 ) )
271  return false;
272  bforeach( const Neighbor &n2, x.pa(n1) )
273  if( !hasEdge( n2, n1 ) )
274  return false;
275  }
276  return true;
277  }
279 
281 
282 
283  void printDot( std::ostream& os ) const;
284 
286  friend std::ostream& operator<<( std::ostream& os, const DAG& g ) {
287  g.printDot( os );
288  return os;
289  }
291 };
292 
293 
294 template<typename EdgeInputIterator>
295 void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
296  _pa.clear();
297  _pa.resize( nr );
298  _ch.clear();
299  _ch.resize( nr );
300 
301  for( EdgeInputIterator e = begin; e != end; e++ )
302  addEdge( e->first, e->second, check );
303 }
304 
305 
306 } // end of namespace dai
307 
308 
309 #endif