New git HEAD version
[libdai.git] / include / dai / dag.h
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
9 /// \file
10 /// \brief Defines the DAG class, which represents a directed acyclic graph
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
29 /// Represents the neighborhood structure of nodes in a directed cyclic graph.
30 /** A directed cyclic graph has nodes connected by directed edges, such that there is no
31 * directed cycle of edges n1->n2->n3->...->n1. Nodes are indexed by an unsigned integer.
32 * If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge
33 * from node \a n1 to node \a n2 is represented by a Edge(\a n1,\a n2).
34 *
35 * DAG is implemented as a sparse adjacency list, i.e., it stores for each node a list of
36 * its parents and a list of its children. Both lists are implemented as a vector of Neighbor
37 * structures (accessible by the pa() and ch() methods). Thus, each node has two associated
38 * variables of type DAG::Neighbors, which are vectors of Neighbor structures, describing their
39 * parent and children nodes.
40 */
41 class DAG {
42 private:
43 /// Contains for each node a vector of its parent nodes
44 std::vector<Neighbors> _pa;
45
46 /// Contains for each node a vector of its children nodes
47 std::vector<Neighbors> _ch;
48
49 public:
50 /// \name Constructors and destructors
51 //@{
52 /// Default constructor (creates an empty DAG).
53 DAG() : _pa(), _ch() {}
54
55 /// Constructs DAG with \a nr nodes and no edges.
56 DAG( size_t nr ) : _pa( nr ), _ch( nr ) {}
57
58 /// Constructs DAG from a range of edges.
59 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
60 * \param nr The number of nodes.
61 * \param begin Points to the first edge.
62 * \param end Points just beyond the last edge.
63 * \param check Whether to only add an edge if it does not exist already and
64 * if it does not introduce a cycle
65 */
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 }
70 //@}
71
72 /// \name Accessors and mutators
73 //@{
74 /// Returns constant reference to the \a _p 'th parent of node \a n
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 }
80 /// Returns reference to the \a _p 'th parent of node \a n
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
87 /// Returns constant reference to all parents of node \a n
88 const Neighbors& pa( size_t n ) const {
89 DAI_DEBASSERT( n < _pa.size() );
90 return _pa[n];
91 }
92 /// Returns reference to all parents of node \a n
93 Neighbors& pa( size_t n ) {
94 DAI_DEBASSERT( n < _pa.size() );
95 return _pa[n];
96 }
97
98 /// Returns constant reference to the \a _c 'th child of node \a n
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 }
104 /// Returns reference to the \a _c 'th child of node \a n
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
111 /// Returns constant reference to all children of node \a n
112 const Neighbors& ch( size_t n ) const {
113 DAI_DEBASSERT( n < _ch.size() );
114 return _ch[n];
115 }
116 /// Returns reference to all children of node \a n
117 Neighbors& ch( size_t n ) {
118 DAI_DEBASSERT( n < _ch.size() );
119 return _ch[n];
120 }
121 //@}
122
123 /// \name Adding nodes and edges
124 //@{
125 /// (Re)constructs DAG from a range of edges.
126 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
127 * \param nr The number of nodes.
128 * \param begin Points to the first edge.
129 * \param end Points just beyond the last edge.
130 * \param check Whether to only add an edge if it does not exist already and does not introduce a cycle.
131 */
132 template<typename EdgeInputIterator>
133 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
134
135 /// Adds a node without parents and children and returns the index of the added node.
136 size_t addNode() {
137 _pa.push_back( Neighbors() );
138 _ch.push_back( Neighbors() );
139 return _pa.size() - 1;
140 }
141
142 /// Adds a node with parents specified by a range of nodes.
143 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
144 * \param begin Points to the first index of the nodes that should become parents of the added node.
145 * \param end Points just beyond the last index of the nodes that should become parents of the added node.
146 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
147 * \returns Index of the added node.
148 */
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
166 /// Adds an edge from node \a n1 and node \a n2.
167 /** If \a check == \c true, only adds the edge if it does not exist already and it would not introduce a cycle.
168 */
169 DAG& addEdge( size_t n1, size_t n2, bool check=true );
170 //@}
171
172 /// \name Erasing nodes and edges
173 //@{
174 /// Removes node \a n and all ingoing and outgoing edges; indices of other nodes are changed accordingly.
175 void eraseNode( size_t n );
176
177 /// Removes edge from node \a n1 to node \a n2.
178 void eraseEdge( size_t n1, size_t n2 );
179 //@}
180
181 /// \name Queries
182 //@{
183 /// Returns number of nodes
184 size_t nrNodes() const {
185 DAI_DEBASSERT( _pa.size() == _ch.size() );
186 return _pa.size();
187 }
188
189 /// Calculates the number of edges, time complexity: O(nrNodes())
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
197 /// Returns true if the DAG contains an edge from node \a n1 and \a n2
198 /** \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
199 */
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
213 /// Returns the index of a given node \a p amongst the parents of \a n
214 /** \note The time complexity is linear in the number of parents of \a n
215 * \throw OBJECT_NOT_FOUND if \a p is not a parent of \a n
216 */
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
225 /// Returns the index of a given node \a c amongst the children of \a n
226 /** \note The time complexity is linear in the number of children of \a n
227 * \throw OBJECT_NOT_FOUND if \a c is not a child \a n
228 */
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
237 /// Returns parents of node \a n as a SmallSet<size_t>.
238 SmallSet<size_t> paSet( size_t n ) const;
239
240 /// Returns children of node \a n as a SmallSet<size_t>.
241 SmallSet<size_t> chSet( size_t n ) const;
242
243 /// 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 (including \a n itself if \a inclusive == \c true)
244 std::set<size_t> ancestors( size_t n, bool inclusive ) const;
245
246 /// 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 if \a inclusive == \c true)
247 std::set<size_t> descendants( size_t n, bool inclusive ) const;
248
249 /// Returns whether there exists a directed path from node \a n1 to node \a n2 (which may consist of zero edges)
250 bool existsDirectedPath( size_t n1, size_t n2 ) const;
251
252 /// Returns true if the DAG is connected
253 bool isConnected() const;
254
255 /// Asserts internal consistency
256 void checkConsistency() const;
257
258 /// Comparison operator which returns true if two DAGs are identical
259 /** \note Two DAGs are called identical if they have the same number
260 * of nodes and the same edges (i.e., \a x has an edge from \a n1 to \a n2
261 * if and only if \c *this has an edge from node \a n1 to \a n2).
262 */
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 }
278 //@}
279
280 /// \name Input and output
281 //@{
282 /// Writes a DAG to an output stream in GraphViz .dot syntax
283 void printDot( std::ostream& os ) const;
284
285 /// Writes a DAG to an output stream
286 friend std::ostream& operator<<( std::ostream& os, const DAG& g ) {
287 g.printDot( os );
288 return os;
289 }
290
291 /// Formats a DAG as a string
292 std::string toString() const {
293 std::stringstream ss;
294 ss << *this;
295 return ss.str();
296 }
297 //@}
298 };
299
300
301 template<typename EdgeInputIterator>
302 void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
303 _pa.clear();
304 _pa.resize( nr );
305 _ch.clear();
306 _ch.resize( nr );
307
308 for( EdgeInputIterator e = begin; e != end; e++ )
309 addEdge( e->first, e->second, check );
310 }
311
312
313 } // end of namespace dai
314
315
316 #endif