Fixed three minor issues
[libdai.git] / include / dai / dag.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2010 Joris Mooij [joris dot mooij at libdai dot org]
8 */
9
10
11 /// \file
12 /// \brief Defines the DAG class, which represents a directed acyclic graph
13
14
15 #ifndef __defined_libdai_dag_h
16 #define __defined_libdai_dag_h
17
18
19 #include <ostream>
20 #include <vector>
21 #include <algorithm>
22 #include <dai/util.h>
23 #include <dai/exceptions.h>
24 #include <dai/smallset.h>
25
26
27 namespace dai {
28
29
30 /// Represents the neighborhood structure of nodes in a directed cyclic graph.
31 /** A directed cyclic graph has nodes connected by directed edges, such that there is no
32 * directed cycle of edges n1->n2->n3->...->n1. Nodes are indexed by an unsigned integer.
33 * If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge
34 * from node \a n1 to node \a n2 is represented by a DAG::Edge(\a n1,\a n2).
35 *
36 * DAG is implemented as a sparse adjacency list, i.e., it stores for each node a list of
37 * its parents and a list of its children. Both lists are implemented as a vector of Neighbor
38 * structures (accessible by the pa() and ch() methods). Thus, each node has two associated
39 * variables of type DAG::Neighbors, which are vectors of Neighbor structures, describing their
40 * parent and children nodes.
41 */
42 class DAG {
43 public:
44 /// Describes the parent/child relationship of two nodes in a DAG.
45 /** Sometimes we want to do an action, such as sending a
46 * message, for all edges in a graph. However, most graphs
47 * will be sparse, so we need some way of storing a set of
48 * the neighbors of a node, which is both fast and
49 * memory-efficient. We also need to be able to go between
50 * viewing node \a a as a neighbor of node \a b, and node \a b
51 * as a neighbor of node \a a. The Neighbor struct solves
52 * both of these problems. Each node has two lists of neighbors
53 * (a list of parents and a list of children), stored as a
54 * std::vector<\link Neighbor \endlink>, and extra information
55 * is included in the Neighbor struct which allows us to access
56 * a node as a neighbor of its neighbor (the \c dual member),
57 * i.e., as a child of its parent or as a parent of its child.
58 *
59 * By convention, variable identifiers naming indices into a
60 * vector of neighbors are prefixed with an underscore ("_").
61 * The neighbor list which they point into is then understood
62 * from context. For example, <tt>pa(i,_j)</tt> gives the
63 * \a _j 'th parent of node \a i, and <tt>ch(k,_l)</tt>
64 * gives the \a _l 'th child of node \a k.
65 * Here, \a i and \a k are "absolute" indexes of nodes \a i and \a k,
66 * but \a _j and \a _k are understood as "relative" indexes
67 * within the list <tt>pa(i)</tt> of parents of \a i and the
68 * list of children <tt>ch(k)</tt> of \a k. The
69 * absolute index of \a _j, which would be called \a j, can be
70 * recovered from the \c node member: <tt>j = pa(i,_j).node</tt>.
71 * Similarly, the absolute index of \a _l, which would be called
72 * \a l, can be recovered from the \c node member:
73 * <tt>l = ch(k,_l).node</tt>.
74 * The \c iter member gives the relative index \a _j or \a _l,
75 * and the \c dual member gives the "dual" relative index, i.e.,
76 * the index of \a i in \a j 's children list or the index of
77 * \a k in \a l 's parent list.
78 *
79 * \code
80 * Neighbor p = pa(i,_j);
81 * p.node == j &&
82 * p.iter == _j &&
83 * ch(p.node,p.dual).node == i
84 *
85 * Neighbor c = ch(k,_l);
86 * c.node == l &&
87 * c.iter == _l &&
88 * pa(c.node,c.dual).node == k
89 * \endcode
90 *
91 * There is no cheap way to transform a pair of absolute node
92 * indices \a i and \a j into a Neighbor structure relative
93 * to one of the nodes. Such a feature has never yet been
94 * found to be necessary. Iteration over edges can always be
95 * accomplished using the Neighbor lists, and by writing
96 * functions that accept relative indices:
97 * \code
98 * for( size_t i = 0; i < nrNodes(); ++i )
99 * foreach( const Neighbor &j, ch(i) )
100 * assert( hasEdge( i, j ) );
101 * \endcode
102 */
103 struct Neighbor {
104 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
105 size_t iter;
106 /// Contains the number of the neighboring node
107 size_t node;
108 /// Contains the "dual" iter
109 size_t dual;
110
111 /// Default constructor
112 Neighbor() {}
113 /// Constructor that sets the Neighbor members according to the parameters
114 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
115
116 /// Cast to \c size_t returns \c node member
117 operator size_t () const { return node; }
118 };
119
120 /// Type for storing the parents/children of some node.
121 typedef std::vector<Neighbor> Neighbors;
122
123 /// Represents a directed edge: an Edge(\a n1,\a n2) corresponds to the edge from node \a n1 to node \a n2.
124 typedef std::pair<size_t,size_t> Edge;
125
126 private:
127 /// Contains for each node a vector of its parent nodes
128 std::vector<Neighbors> _pa;
129
130 /// Contains for each node a vector of its children nodes
131 std::vector<Neighbors> _ch;
132
133 public:
134 /// \name Constructors and destructors
135 //@{
136 /// Default constructor (creates an empty DAG).
137 DAG() : _pa(), _ch() {}
138
139 /// Constructs DAG with \a nr nodes and no edges.
140 DAG( size_t nr ) : _pa( nr ), _ch( nr ) {}
141
142 /// Constructs DAG from a range of edges.
143 /** \tparam EdgeInputIterator Iterator that iterates over instances of DAG::Edge.
144 * \param nr The number of nodes.
145 * \param begin Points to the first edge.
146 * \param end Points just beyond the last edge.
147 * \param check Whether to only add an edge if it does not exist already and
148 * if it does not introduce a cycle
149 */
150 template<typename EdgeInputIterator>
151 DAG( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _pa(), _ch() {
152 construct( nr, begin, end, check );
153 }
154 //@}
155
156 /// \name Accessors and mutators
157 //@{
158 /// Returns constant reference to the \a _p 'th parent of node \a n
159 const Neighbor& pa( size_t n, size_t _p ) const {
160 DAI_DEBASSERT( n < _pa.size() );
161 DAI_DEBASSERT( _p < _pa[n].size() );
162 return _pa[n][_p];
163 }
164 /// Returns reference to the \a _p 'th parent of node \a n
165 Neighbor& pa( size_t n, size_t _p ) {
166 DAI_DEBASSERT( n < _pa.size() );
167 DAI_DEBASSERT( _p < _pa[n].size() );
168 return _pa[n][_p];
169 }
170
171 /// Returns constant reference to all parents of node \a n
172 const Neighbors& pa( size_t n ) const {
173 DAI_DEBASSERT( n < _pa.size() );
174 return _pa[n];
175 }
176 /// Returns reference to all parents of node \a n
177 Neighbors& pa( size_t n ) {
178 DAI_DEBASSERT( n < _pa.size() );
179 return _pa[n];
180 }
181
182 /// Returns constant reference to the \a _c 'th child of node \a n
183 const Neighbor& ch( size_t n, size_t _c ) const {
184 DAI_DEBASSERT( n < _ch.size() );
185 DAI_DEBASSERT( _c < _ch[n].size() );
186 return _ch[n][_c];
187 }
188 /// Returns reference to the \a _c 'th child of node \a n
189 Neighbor& ch( size_t n, size_t _c ) {
190 DAI_DEBASSERT( n < _ch.size() );
191 DAI_DEBASSERT( _c < _ch[n].size() );
192 return _ch[n][_c];
193 }
194
195 /// Returns constant reference to all children of node \a n
196 const Neighbors& ch( size_t n ) const {
197 DAI_DEBASSERT( n < _ch.size() );
198 return _ch[n];
199 }
200 /// Returns reference to all children of node \a n
201 Neighbors& ch( size_t n ) {
202 DAI_DEBASSERT( n < _ch.size() );
203 return _ch[n];
204 }
205 //@}
206
207 /// \name Adding nodes and edges
208 //@{
209 /// (Re)constructs DAG from a range of edges.
210 /** \tparam EdgeInputIterator Iterator that iterates over instances of DAG::Edge.
211 * \param nr The number of nodes.
212 * \param begin Points to the first edge.
213 * \param end Points just beyond the last edge.
214 * \param check Whether to only add an edge if it does not exist already and does not introduce a cycle.
215 */
216 template<typename EdgeInputIterator>
217 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
218
219 /// Adds a node without parents and children and returns the index of the added node.
220 size_t addNode() {
221 _pa.push_back( Neighbors() );
222 _ch.push_back( Neighbors() );
223 return _pa.size() - 1;
224 }
225
226 /// Adds a node with parents specified by a range of nodes.
227 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
228 * \param begin Points to the first index of the nodes that should become parents of the added node.
229 * \param end Points just beyond the last index of the nodes that should become parents of the added node.
230 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
231 * \returns Index of the added node.
232 */
233 template <typename NodeInputIterator>
234 size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0 ) {
235 Neighbors newparents;
236 newparents.reserve( sizeHint );
237 size_t iter = 0;
238 for( NodeInputIterator it = begin; it != end; ++it ) {
239 DAI_ASSERT( *it < nrNodes() );
240 Neighbor newparent( iter, *it, ch(*it).size() );
241 Neighbor newchild( ch(*it).size(), nrNodes(), iter++ );
242 newparents.push_back( newparent );
243 ch( *it ).push_back( newchild );
244 }
245 _pa.push_back( newparents );
246 _ch.push_back( Neighbors() );
247 return _pa.size() - 1;
248 }
249
250 /// Adds an edge from node \a n1 and node \a n2.
251 /** If \a check == \c true, only adds the edge if it does not exist already and it would not introduce a cycle.
252 */
253 DAG& addEdge( size_t n1, size_t n2, bool check=true );
254 //@}
255
256 /// \name Erasing nodes and edges
257 //@{
258 /// Removes node \a n and all ingoing and outgoing edges; indices of other nodes are changed accordingly.
259 void eraseNode( size_t n );
260
261 /// Removes edge from node \a n1 to node \a n2.
262 void eraseEdge( size_t n1, size_t n2 );
263 //@}
264
265 /// \name Queries
266 //@{
267 /// Returns number of nodes
268 size_t nrNodes() const {
269 DAI_DEBASSERT( _pa.size() == _ch.size() );
270 return _pa.size();
271 }
272
273 /// Calculates the number of edges, time complexity: O(nrNodes())
274 size_t nrEdges() const {
275 size_t sum = 0;
276 for( size_t i = 0; i < _pa.size(); i++ )
277 sum += _pa[i].size();
278 return sum;
279 }
280
281 /// Returns true if the DAG contains an edge from node \a n1 and \a n2
282 /** \note The time complexity is linear in the number of children of \a n1 or the number of parents of \a n2, whichever is smaller
283 */
284 bool hasEdge( size_t n1, size_t n2 ) const {
285 if( ch(n1).size() < pa(n2).size() ) {
286 for( size_t _n2 = 0; _n2 < ch(n1).size(); _n2++ )
287 if( ch( n1, _n2 ) == n2 )
288 return true;
289 } else {
290 for( size_t _n1 = 0; _n1 < pa(n2).size(); _n1++ )
291 if( pa( n2, _n1 ) == n1 )
292 return true;
293 }
294 return false;
295 }
296
297 /// Returns the index of a given node \a p amongst the parents of \a n
298 /** \note The time complexity is linear in the number of parents of \a n
299 * \throw OBJECT_NOT_FOUND if \a p is not a parent of \a n
300 */
301 size_t findPa( size_t n, size_t p ) {
302 for( size_t _p = 0; _p < pa(n).size(); _p++ )
303 if( pa( n, _p ) == p )
304 return _p;
305 DAI_THROW(OBJECT_NOT_FOUND);
306 return pa(n).size();
307 }
308
309 /// Returns the index of a given node \a c amongst the children of \a n
310 /** \note The time complexity is linear in the number of children of \a n
311 * \throw OBJECT_NOT_FOUND if \a c is not a child \a n
312 */
313 size_t findCh( size_t n, size_t c ) {
314 for( size_t _c = 0; _c < ch(n).size(); _c++ )
315 if( ch( n, _c ) == c )
316 return _c;
317 DAI_THROW(OBJECT_NOT_FOUND);
318 return ch(n).size();
319 }
320
321 /// Returns parents of node \a n as a SmallSet<size_t>.
322 SmallSet<size_t> paSet( size_t n ) const;
323
324 /// Returns children of node \a n as a SmallSet<size_t>.
325 SmallSet<size_t> chSet( size_t n ) const;
326
327 /// Returns the set of ancestors of node \a n, i.e., all nodes \a a such that there exists a directed path from \a a to \a n (excluding \a n itself)
328 std::set<size_t> ancestors( size_t n ) const;
329
330 /// Returns the set of descendants of node \a n, i.e., all nodes \a d such that there exists a directed path from \a n to \a d (excluding \a n itself)
331 std::set<size_t> descendants( size_t n ) const;
332
333 /// Returns whether there exists a directed path from node \a n1 to node \a n2 (which may consist of zero edges)
334 bool existsDirectedPath( size_t n1, size_t n2 ) const;
335
336 /// Returns true if the DAG is connected
337 bool isConnected() const;
338
339 /// Asserts internal consistency
340 void checkConsistency() const;
341
342 /// Comparison operator which returns true if two DAGs are identical
343 /** \note Two DAGs are called identical if they have the same number
344 * of nodes and the same edges (i.e., \a x has an edge from \a n1 to \a n2
345 * if and only if \c *this has an edge from node \a n1 to \a n2).
346 */
347 bool operator==( const DAG& x ) const {
348 if( nrNodes() != x.nrNodes() )
349 return false;
350 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
351 if( pa(n1).size() != x.pa(n1).size() )
352 return false;
353 foreach( const Neighbor &n2, pa(n1) )
354 if( !x.hasEdge( n2, n1 ) )
355 return false;
356 foreach( const Neighbor &n2, x.pa(n1) )
357 if( !hasEdge( n2, n1 ) )
358 return false;
359 }
360 return true;
361 }
362 //@}
363
364 /// \name Input and output
365 //@{
366 /// Writes this DAG to an output stream in GraphViz .dot syntax
367 void printDot( std::ostream& os ) const;
368
369 /// Writes this DAG to an output stream
370 friend std::ostream& operator<<( std::ostream& os, const DAG& g ) {
371 g.printDot( os );
372 return os;
373 }
374 //@}
375 };
376
377
378 template<typename EdgeInputIterator>
379 void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
380 _pa.clear();
381 _pa.resize( nr );
382 _ch.clear();
383 _ch.resize( nr );
384
385 for( EdgeInputIterator e = begin; e != end; e++ )
386 addEdge( e->first, e->second, check );
387 }
388
389
390 } // end of namespace dai
391
392
393 #endif