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 private:
45 /// Contains for each node a vector of its parent nodes
46 std::vector<Neighbors> _pa;
48 /// Contains for each node a vector of its children nodes
49 std::vector<Neighbors> _ch;
51 public:
52 /// \name Constructors and destructors
53 //@{
54 /// Default constructor (creates an empty DAG).
55 DAG() : _pa(), _ch() {}
57 /// Constructs DAG with \a nr nodes and no edges.
58 DAG( size_t nr ) : _pa( nr ), _ch( nr ) {}
60 /// Constructs DAG from a range of edges.
61 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
62 * \param nr The number of nodes.
63 * \param begin Points to the first edge.
64 * \param end Points just beyond the last edge.
65 * \param check Whether to only add an edge if it does not exist already and
66 * if it does not introduce a cycle
67 */
68 template<typename EdgeInputIterator>
69 DAG( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _pa(), _ch() {
70 construct( nr, begin, end, check );
71 }
72 //@}
74 /// \name Accessors and mutators
75 //@{
76 /// Returns constant reference to the \a _p 'th parent of node \a n
77 const Neighbor& pa( size_t n, size_t _p ) const {
78 DAI_DEBASSERT( n < _pa.size() );
79 DAI_DEBASSERT( _p < _pa[n].size() );
80 return _pa[n][_p];
81 }
82 /// Returns reference to the \a _p 'th parent of node \a n
83 Neighbor& pa( size_t n, size_t _p ) {
84 DAI_DEBASSERT( n < _pa.size() );
85 DAI_DEBASSERT( _p < _pa[n].size() );
86 return _pa[n][_p];
87 }
89 /// Returns constant reference to all parents of node \a n
90 const Neighbors& pa( size_t n ) const {
91 DAI_DEBASSERT( n < _pa.size() );
92 return _pa[n];
93 }
94 /// Returns reference to all parents of node \a n
95 Neighbors& pa( size_t n ) {
96 DAI_DEBASSERT( n < _pa.size() );
97 return _pa[n];
98 }
100 /// Returns constant reference to the \a _c 'th child of node \a n
101 const Neighbor& ch( size_t n, size_t _c ) const {
102 DAI_DEBASSERT( n < _ch.size() );
103 DAI_DEBASSERT( _c < _ch[n].size() );
104 return _ch[n][_c];
105 }
106 /// Returns reference to the \a _c 'th child of node \a n
107 Neighbor& ch( size_t n, size_t _c ) {
108 DAI_DEBASSERT( n < _ch.size() );
109 DAI_DEBASSERT( _c < _ch[n].size() );
110 return _ch[n][_c];
111 }
113 /// Returns constant reference to all children of node \a n
114 const Neighbors& ch( size_t n ) const {
115 DAI_DEBASSERT( n < _ch.size() );
116 return _ch[n];
117 }
118 /// Returns reference to all children of node \a n
119 Neighbors& ch( size_t n ) {
120 DAI_DEBASSERT( n < _ch.size() );
121 return _ch[n];
122 }
123 //@}
125 /// \name Adding nodes and edges
126 //@{
127 /// (Re)constructs DAG from a range of edges.
128 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
129 * \param nr The number of nodes.
130 * \param begin Points to the first edge.
131 * \param end Points just beyond the last edge.
132 * \param check Whether to only add an edge if it does not exist already and does not introduce a cycle.
133 */
134 template<typename EdgeInputIterator>
135 void construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
137 /// Adds a node without parents and children and returns the index of the added node.
139 _pa.push_back( Neighbors() );
140 _ch.push_back( Neighbors() );
141 return _pa.size() - 1;
142 }
144 /// Adds a node with parents specified by a range of nodes.
145 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
146 * \param begin Points to the first index of the nodes that should become parents of the added node.
147 * \param end Points just beyond the last index of the nodes that should become parents of the added node.
148 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
149 * \returns Index of the added node.
150 */
151 template <typename NodeInputIterator>
152 size_t addNode( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0 ) {
153 Neighbors newparents;
154 newparents.reserve( sizeHint );
155 size_t iter = 0;
156 for( NodeInputIterator it = begin; it != end; ++it ) {
157 DAI_ASSERT( *it < nrNodes() );
158 Neighbor newparent( iter, *it, ch(*it).size() );
159 Neighbor newchild( ch(*it).size(), nrNodes(), iter++ );
160 newparents.push_back( newparent );
161 ch( *it ).push_back( newchild );
162 }
163 _pa.push_back( newparents );
164 _ch.push_back( Neighbors() );
165 return _pa.size() - 1;
166 }
168 /// Adds an edge from node \a n1 and node \a n2.
169 /** If \a check == \c true, only adds the edge if it does not exist already and it would not introduce a cycle.
170 */
171 DAG& addEdge( size_t n1, size_t n2, bool check=true );
172 //@}
174 /// \name Erasing nodes and edges
175 //@{
176 /// Removes node \a n and all ingoing and outgoing edges; indices of other nodes are changed accordingly.
177 void eraseNode( size_t n );
179 /// Removes edge from node \a n1 to node \a n2.
180 void eraseEdge( size_t n1, size_t n2 );
181 //@}
183 /// \name Queries
184 //@{
185 /// Returns number of nodes
186 size_t nrNodes() const {
187 DAI_DEBASSERT( _pa.size() == _ch.size() );
188 return _pa.size();
189 }
191 /// Calculates the number of edges, time complexity: O(nrNodes())
192 size_t nrEdges() const {
193 size_t sum = 0;
194 for( size_t i = 0; i < _pa.size(); i++ )
195 sum += _pa[i].size();
196 return sum;
197 }
199 /// Returns true if the DAG contains an edge from node \a n1 and \a n2
200 /** \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
201 */
202 bool hasEdge( size_t n1, size_t n2 ) const {
203 if( ch(n1).size() < pa(n2).size() ) {
204 for( size_t _n2 = 0; _n2 < ch(n1).size(); _n2++ )
205 if( ch( n1, _n2 ) == n2 )
206 return true;
207 } else {
208 for( size_t _n1 = 0; _n1 < pa(n2).size(); _n1++ )
209 if( pa( n2, _n1 ) == n1 )
210 return true;
211 }
212 return false;
213 }
215 /// Returns the index of a given node \a p amongst the parents of \a n
216 /** \note The time complexity is linear in the number of parents of \a n
217 * \throw OBJECT_NOT_FOUND if \a p is not a parent of \a n
218 */
219 size_t findPa( size_t n, size_t p ) {
220 for( size_t _p = 0; _p < pa(n).size(); _p++ )
221 if( pa( n, _p ) == p )
222 return _p;
223 DAI_THROW(OBJECT_NOT_FOUND);
224 return pa(n).size();
225 }
227 /// Returns the index of a given node \a c amongst the children of \a n
228 /** \note The time complexity is linear in the number of children of \a n
229 * \throw OBJECT_NOT_FOUND if \a c is not a child \a n
230 */
231 size_t findCh( size_t n, size_t c ) {
232 for( size_t _c = 0; _c < ch(n).size(); _c++ )
233 if( ch( n, _c ) == c )
234 return _c;
235 DAI_THROW(OBJECT_NOT_FOUND);
236 return ch(n).size();
237 }
239 /// Returns parents of node \a n as a SmallSet<size_t>.
240 SmallSet<size_t> paSet( size_t n ) const;
242 /// Returns children of node \a n as a SmallSet<size_t>.
243 SmallSet<size_t> chSet( size_t n ) const;
245 /// 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)
246 std::set<size_t> ancestors( size_t n ) const;
248 /// 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)
249 std::set<size_t> descendants( size_t n ) const;
251 /// Returns whether there exists a directed path from node \a n1 to node \a n2 (which may consist of zero edges)
252 bool existsDirectedPath( size_t n1, size_t n2 ) const;
254 /// Returns true if the DAG is connected
255 bool isConnected() const;
257 /// Asserts internal consistency
258 void checkConsistency() const;
260 /// Comparison operator which returns true if two DAGs are identical
261 /** \note Two DAGs are called identical if they have the same number
262 * of nodes and the same edges (i.e., \a x has an edge from \a n1 to \a n2
263 * if and only if \c *this has an edge from node \a n1 to \a n2).
264 */
265 bool operator==( const DAG& x ) const {
266 if( nrNodes() != x.nrNodes() )
267 return false;
268 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
269 if( pa(n1).size() != x.pa(n1).size() )
270 return false;
271 foreach( const Neighbor &n2, pa(n1) )
272 if( !x.hasEdge( n2, n1 ) )
273 return false;
274 foreach( const Neighbor &n2, x.pa(n1) )
275 if( !hasEdge( n2, n1 ) )
276 return false;
277 }
278 return true;
279 }
280 //@}
282 /// \name Input and output
283 //@{
284 /// Writes this DAG to an output stream in GraphViz .dot syntax
285 void printDot( std::ostream& os ) const;
287 /// Writes this DAG to an output stream
288 friend std::ostream& operator<<( std::ostream& os, const DAG& g ) {
289 g.printDot( os );
290 return os;
291 }
292 //@}
293 };
296 template<typename EdgeInputIterator>
297 void DAG::construct( size_t nr, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
298 _pa.clear();
299 _pa.resize( nr );
300 _ch.clear();
301 _ch.resize( nr );
303 for( EdgeInputIterator e = begin; e != end; e++ )
304 addEdge( e->first, e->second, check );
305 }
308 } // end of namespace dai
311 #endif