4822e72e0cd3dfd3561353d570c75e4a51b34312
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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 */
11 /// \file
12 /// \brief Defines the DAG class, which represents a directed acyclic graph
15 #ifndef __defined_libdai_dag_h
16 #define __defined_libdai_dag_h
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 #include <dai/graph.h>
28 namespace dai {
31 /// Represents the neighborhood structure of nodes in a directed cyclic graph.
32 /** A directed cyclic graph has nodes connected by directed edges, such that there is no
33 * directed cycle of edges n1->n2->n3->...->n1. Nodes are indexed by an unsigned integer.
34 * If there are nrNodes() nodes, they are numbered 0,1,2,...,nrNodes()-1. An edge
35 * from node \a n1 to node \a n2 is represented by a Edge(\a n1,\a n2).
36 *
37 * DAG is implemented as a sparse adjacency list, i.e., it stores for each node a list of
38 * its parents and a list of its children. Both lists are implemented as a vector of Neighbor
39 * structures (accessible by the pa() and ch() methods). Thus, each node has two associated
40 * variables of type DAG::Neighbors, which are vectors of Neighbor structures, describing their
41 * parent and children nodes.
42 */
43 class DAG {
44 /// Describes the parent/child relationship of two nodes in a DAG.
46 */
47 typedef dai::Neighbor Neighbor;
49 /// Type for storing the parents/children of some node.
51 */
52 typedef dai::Neighbors Neighbors;
54 /// Represents a directed edge: an Edge(\a n1,\a n2) corresponds to the edge from node \a n1 to node \a n2.
56 */
57 typedef dai::Edge Edge;
59 private:
60 /// Contains for each node a vector of its parent nodes
61 std::vector<Neighbors> _pa;
63 /// Contains for each node a vector of its children nodes
64 std::vector<Neighbors> _ch;
66 public:
67 /// \name Constructors and destructors
68 //@{
69 /// Default constructor (creates an empty DAG).
70 DAG() : _pa(), _ch() {}
72 /// Constructs DAG with \a nr nodes and no edges.
73 DAG( size_t nr ) : _pa( nr ), _ch( nr ) {}
75 /// Constructs DAG from a range of edges.
76 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
77 * \param nr The number of nodes.
78 * \param begin Points to the first edge.
79 * \param end Points just beyond the last edge.
80 * \param check Whether to only add an edge if it does not exist already and
81 * if it does not introduce a cycle
82 */
83 template<typename EdgeInputIterator>
84 DAG( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _pa(), _ch() {
85 construct( nr, begin, end, check );
86 }
87 //@}
89 /// \name Accessors and mutators
90 //@{
91 /// Returns constant reference to the \a _p 'th parent of node \a n
92 const Neighbor& pa( size_t n, size_t _p ) const {
93 DAI_DEBASSERT( n < _pa.size() );
94 DAI_DEBASSERT( _p < _pa[n].size() );
95 return _pa[n][_p];
96 }
97 /// Returns reference to the \a _p 'th parent of node \a n
98 Neighbor& pa( size_t n, size_t _p ) {
99 DAI_DEBASSERT( n < _pa.size() );
100 DAI_DEBASSERT( _p < _pa[n].size() );
101 return _pa[n][_p];
102 }
104 /// Returns constant reference to all parents of node \a n
105 const Neighbors& pa( size_t n ) const {
106 DAI_DEBASSERT( n < _pa.size() );
107 return _pa[n];
108 }
109 /// Returns reference to all parents of node \a n
110 Neighbors& pa( size_t n ) {
111 DAI_DEBASSERT( n < _pa.size() );
112 return _pa[n];
113 }
115 /// Returns constant reference to the \a _c 'th child of node \a n
116 const Neighbor& ch( size_t n, size_t _c ) const {
117 DAI_DEBASSERT( n < _ch.size() );
118 DAI_DEBASSERT( _c < _ch[n].size() );
119 return _ch[n][_c];
120 }
121 /// Returns reference to the \a _c 'th child of node \a n
122 Neighbor& ch( size_t n, size_t _c ) {
123 DAI_DEBASSERT( n < _ch.size() );
124 DAI_DEBASSERT( _c < _ch[n].size() );
125 return _ch[n][_c];
126 }
128 /// Returns constant reference to all children of node \a n
129 const Neighbors& ch( size_t n ) const {
130 DAI_DEBASSERT( n < _ch.size() );
131 return _ch[n];
132 }
133 /// Returns reference to all children of node \a n
134 Neighbors& ch( size_t n ) {
135 DAI_DEBASSERT( n < _ch.size() );
136 return _ch[n];
137 }
138 //@}
140 /// \name Adding nodes and edges
141 //@{
142 /// (Re)constructs DAG from a range of edges.
143 /** \tparam EdgeInputIterator Iterator that iterates over instances of 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 does not introduce a cycle.
148 */
149 template<typename EdgeInputIterator>
150 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
152 /// Adds a node without parents and children and returns the index of the added node.
154 _pa.push_back( Neighbors() );
155 _ch.push_back( Neighbors() );
156 return _pa.size() - 1;
157 }
159 /// Adds a node with parents specified by a range of nodes.
160 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
161 * \param begin Points to the first index of the nodes that should become parents of the added node.
162 * \param end Points just beyond the last index of the nodes that should become parents of the added node.
163 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
164 * \returns Index of the added node.
165 */
166 template <typename NodeInputIterator>
167 size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0 ) {
168 Neighbors newparents;
169 newparents.reserve( sizeHint );
170 size_t iter = 0;
171 for( NodeInputIterator it = begin; it != end; ++it ) {
172 DAI_ASSERT( *it < nrNodes() );
173 Neighbor newparent( iter, *it, ch(*it).size() );
174 Neighbor newchild( ch(*it).size(), nrNodes(), iter++ );
175 newparents.push_back( newparent );
176 ch( *it ).push_back( newchild );
177 }
178 _pa.push_back( newparents );
179 _ch.push_back( Neighbors() );
180 return _pa.size() - 1;
181 }
183 /// Adds an edge from node \a n1 and node \a n2.
184 /** If \a check == \c true, only adds the edge if it does not exist already and it would not introduce a cycle.
185 */
186 DAG& addEdge( size_t n1, size_t n2, bool check=true );
187 //@}
189 /// \name Erasing nodes and edges
190 //@{
191 /// Removes node \a n and all ingoing and outgoing edges; indices of other nodes are changed accordingly.
192 void eraseNode( size_t n );
194 /// Removes edge from node \a n1 to node \a n2.
195 void eraseEdge( size_t n1, size_t n2 );
196 //@}
198 /// \name Queries
199 //@{
200 /// Returns number of nodes
201 size_t nrNodes() const {
202 DAI_DEBASSERT( _pa.size() == _ch.size() );
203 return _pa.size();
204 }
206 /// Calculates the number of edges, time complexity: O(nrNodes())
207 size_t nrEdges() const {
208 size_t sum = 0;
209 for( size_t i = 0; i < _pa.size(); i++ )
210 sum += _pa[i].size();
211 return sum;
212 }
214 /// Returns true if the DAG contains an edge from node \a n1 and \a n2
215 /** \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
216 */
217 bool hasEdge( size_t n1, size_t n2 ) const {
218 if( ch(n1).size() < pa(n2).size() ) {
219 for( size_t _n2 = 0; _n2 < ch(n1).size(); _n2++ )
220 if( ch( n1, _n2 ) == n2 )
221 return true;
222 } else {
223 for( size_t _n1 = 0; _n1 < pa(n2).size(); _n1++ )
224 if( pa( n2, _n1 ) == n1 )
225 return true;
226 }
227 return false;
228 }
230 /// Returns the index of a given node \a p amongst the parents of \a n
231 /** \note The time complexity is linear in the number of parents of \a n
232 * \throw OBJECT_NOT_FOUND if \a p is not a parent of \a n
233 */
234 size_t findPa( size_t n, size_t p ) {
235 for( size_t _p = 0; _p < pa(n).size(); _p++ )
236 if( pa( n, _p ) == p )
237 return _p;
238 DAI_THROW(OBJECT_NOT_FOUND);
239 return pa(n).size();
240 }
242 /// Returns the index of a given node \a c amongst the children of \a n
243 /** \note The time complexity is linear in the number of children of \a n
244 * \throw OBJECT_NOT_FOUND if \a c is not a child \a n
245 */
246 size_t findCh( size_t n, size_t c ) {
247 for( size_t _c = 0; _c < ch(n).size(); _c++ )
248 if( ch( n, _c ) == c )
249 return _c;
250 DAI_THROW(OBJECT_NOT_FOUND);
251 return ch(n).size();
252 }
254 /// Returns parents of node \a n as a SmallSet<size_t>.
255 SmallSet<size_t> paSet( size_t n ) const;
257 /// Returns children of node \a n as a SmallSet<size_t>.
258 SmallSet<size_t> chSet( size_t n ) const;
260 /// 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)
261 std::set<size_t> ancestors( size_t n ) const;
263 /// 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)
264 std::set<size_t> descendants( size_t n ) const;
266 /// Returns whether there exists a directed path from node \a n1 to node \a n2 (which may consist of zero edges)
267 bool existsDirectedPath( size_t n1, size_t n2 ) const;
269 /// Returns true if the DAG is connected
270 bool isConnected() const;
272 /// Asserts internal consistency
273 void checkConsistency() const;
275 /// Comparison operator which returns true if two DAGs are identical
276 /** \note Two DAGs are called identical if they have the same number
277 * of nodes and the same edges (i.e., \a x has an edge from \a n1 to \a n2
278 * if and only if \c *this has an edge from node \a n1 to \a n2).
279 */
280 bool operator==( const DAG& x ) const {
281 if( nrNodes() != x.nrNodes() )
282 return false;
283 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
284 if( pa(n1).size() != x.pa(n1).size() )
285 return false;
286 foreach( const Neighbor &n2, pa(n1) )
287 if( !x.hasEdge( n2, n1 ) )
288 return false;
289 foreach( const Neighbor &n2, x.pa(n1) )
290 if( !hasEdge( n2, n1 ) )
291 return false;
292 }
293 return true;
294 }
295 //@}
297 /// \name Input and output
298 //@{
299 /// Writes this DAG to an output stream in GraphViz .dot syntax
300 void printDot( std::ostream& os ) const;
302 /// Writes this DAG to an output stream
303 friend std::ostream& operator<<( std::ostream& os, const DAG& g ) {
304 g.printDot( os );
305 return os;
306 }
307 //@}
308 };
311 template<typename EdgeInputIterator>
312 void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
313 _pa.clear();
314 _pa.resize( nr );
315 _ch.clear();
316 _ch.resize( nr );
318 for( EdgeInputIterator e = begin; e != end; e++ )
319 addEdge( e->first, e->second, check );
320 }
323 } // end of namespace dai
326 #endif