New git HEAD version
[libdai.git] / src / dag.cpp
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 #include <dai/dag.h>
10
11
12 namespace dai {
13
14
15 using namespace std;
16
17
18 DAG& DAG::addEdge( size_t n1, size_t n2, bool check ) {
19 DAI_ASSERT( n1 < nrNodes() );
20 DAI_ASSERT( n2 < nrNodes() );
21 bool allowed = true;
22 if( check ) {
23 // Check whether the edge already exists
24 bforeach( const Neighbor& n, ch(n1) )
25 if( n == n2 ) {
26 allowed = false;
27 break;
28 }
29 // Check whether there exists a directed path from n2 to n1 already
30 if( allowed && existsDirectedPath( n2, n1 ) )
31 allowed = false;
32 }
33 if( allowed && n1 != n2 ) { // Add edge
34 Neighbor ch_1( ch(n1).size(), n2, pa(n2).size() );
35 Neighbor pa_2( ch_1.dual, n1, ch_1.iter );
36 ch(n1).push_back( ch_1 );
37 pa(n2).push_back( pa_2 );
38 }
39 return *this;
40 }
41
42
43 void DAG::eraseNode( size_t n ) {
44 DAI_ASSERT( n < nrNodes() );
45 // Erase parents entry of node n
46 _pa.erase( _pa.begin() + n );
47 // Erase children entry of node n
48 _ch.erase( _ch.begin() + n );
49 // Adjust parents and children entries of remaining nodes
50 for( size_t m = 0; m < nrNodes(); m++ ) {
51 // Adjust parents entries of node m
52 for( size_t iter = 0; iter < pa(m).size(); ) {
53 Neighbor &p = pa(m, iter);
54 if( p.node == n ) {
55 // delete this entry, because it points to the deleted node
56 pa(m).erase( pa(m).begin() + iter );
57 } else {
58 // update this entry and the corresponding dual of the child node
59 if( p.node > n )
60 p.node--;
61 ch( p.node, p.dual ).dual = iter;
62 p.iter = iter++;
63 }
64 }
65 // Adjust children entries of node m
66 for( size_t iter = 0; iter < ch(m).size(); ) {
67 Neighbor &c = ch(m, iter);
68 if( c.node == n ) {
69 // delete this entry, because it points to the deleted node
70 ch(m).erase( ch(m).begin() + iter );
71 } else {
72 if( c.node > n )
73 c.node--;
74 // update this entry and the corresponding dual of the child node
75 pa( c.node, c.dual ).dual = iter;
76 c.iter = iter++;
77 }
78 }
79 }
80 }
81
82
83 void DAG::eraseEdge( size_t n1, size_t n2 ) {
84 DAI_ASSERT( n1 < nrNodes() );
85 DAI_ASSERT( n2 < nrNodes() );
86 size_t iter;
87 // Search for edge among children of n1
88 for( iter = 0; iter < ch(n1).size(); iter++ )
89 if( ch(n1, iter).node == n2 ) {
90 // Remove it
91 ch(n1).erase( ch(n1).begin() + iter );
92 break;
93 }
94 // Change the iter and dual values of the subsequent children
95 for( ; iter < ch(n1).size(); iter++ ) {
96 Neighbor &m = ch( n1, iter );
97 m.iter = iter;
98 pa( m.node, m.dual ).dual = iter;
99 }
100 // Search for edge among parents of n2
101 for( iter = 0; iter < pa(n2).size(); iter++ )
102 if( pa(n2, iter).node == n1 ) {
103 // Remove it
104 pa(n2).erase( pa(n2).begin() + iter );
105 break;
106 }
107 // Change the iter and node values of the subsequent parents
108 for( ; iter < pa(n2).size(); iter++ ) {
109 Neighbor &m = pa( n2, iter );
110 m.iter = iter;
111 ch( m.node, m.dual ).dual = iter;
112 }
113 }
114
115
116 SmallSet<size_t> DAG::paSet( size_t n ) const {
117 SmallSet<size_t> result;
118 bforeach( const Neighbor &p, pa(n) )
119 result |= p;
120 return result;
121 }
122
123
124 SmallSet<size_t> DAG::chSet( size_t n ) const {
125 SmallSet<size_t> result;
126 bforeach( const Neighbor &c, ch(n) )
127 result |= c;
128 return result;
129 }
130
131
132 /// 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)
133 std::set<size_t> DAG::ancestors( size_t n, bool inclusive ) const {
134 set<size_t> anc;
135 if( inclusive )
136 anc.insert( n );
137
138 set<size_t> curParents;
139 curParents.insert( n );
140 while( curParents.size() ) {
141 size_t node = *(curParents.begin());
142 // Add node to ancestors
143 if( node != n )
144 anc.insert( node );
145 // Add all parents of node to curParents
146 bforeach( const Neighbor& p, pa(node) )
147 curParents.insert( p.node );
148 // Erase node from curParents
149 curParents.erase( node );
150 }
151
152 return anc;
153 }
154
155
156 /// 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)
157 std::set<size_t> DAG::descendants( size_t n, bool inclusive ) const {
158 set<size_t> desc;
159 if( inclusive )
160 desc.insert( n );
161
162 set<size_t> curChildren;
163 curChildren.insert( n );
164 while( curChildren.size() ) {
165 size_t node = *(curChildren.begin());
166 // Add node to descendants
167 if( node != n )
168 desc.insert( node );
169 // Add all children of node to curChildren
170 bforeach( const Neighbor& c, ch(node) )
171 curChildren.insert( c.node );
172 // Erase node from curChildren
173 curChildren.erase( node );
174 }
175
176 return desc;
177 }
178
179
180 bool DAG::existsDirectedPath( size_t n1, size_t n2 ) const {
181 set<size_t> curChildren;
182
183 curChildren.insert( n1 );
184 while( curChildren.size() ) {
185 size_t node = *(curChildren.begin());
186 // If we reached n2, we found a directed path from n1 to n2
187 if( node == n2 )
188 return true;
189 // Add all children of node to curChildren
190 bforeach( const Neighbor& c, ch(node) )
191 curChildren.insert( c.node );
192 // Erase node from curChildren
193 curChildren.erase( node );
194 }
195 return false;
196 }
197
198
199 bool DAG::isConnected() const {
200 if( nrNodes() == 0 ) {
201 return true;
202 } else {
203 std::vector<bool> incomponent( nrNodes(), false );
204
205 incomponent[0] = true;
206 bool found_new_nodes;
207 do {
208 found_new_nodes = false;
209
210 // For all nodes, check if they are connected with the (growing) component
211 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
212 if( !incomponent[n1] ) {
213 bforeach( const Neighbor &n2, pa(n1) )
214 if( incomponent[n2] ) {
215 found_new_nodes = true;
216 incomponent[n1] = true;
217 break;
218 }
219 }
220 if( !incomponent[n1] ) {
221 bforeach( const Neighbor &n2, ch(n1) )
222 if( incomponent[n2] ) {
223 found_new_nodes = true;
224 incomponent[n1] = true;
225 break;
226 }
227 }
228 }
229 } while( found_new_nodes );
230
231 // Check if there are remaining nodes (not in the component)
232 bool all_connected = true;
233 for( size_t n1 = 0; (n1 < nrNodes()) && all_connected; n1++ )
234 if( !incomponent[n1] )
235 all_connected = false;
236
237 return all_connected;
238 }
239 }
240
241
242 void DAG::printDot( std::ostream& os ) const {
243 os << "digraph DAG {" << endl;
244 os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
245 for( size_t n = 0; n < nrNodes(); n++ )
246 os << "\tx" << n << ";" << endl;
247 for( size_t n1 = 0; n1 < nrNodes(); n1++ )
248 bforeach( const Neighbor &n2, ch(n1) )
249 os << "\tx" << n1 << " -> x" << n2 << ";" << endl;
250 os << "}" << endl;
251 }
252
253
254 void DAG::checkConsistency() const {
255 size_t N = nrNodes();
256 for( size_t n1 = 0; n1 < N; n1++ ) {
257 size_t iter = 0;
258 bforeach( const Neighbor &n2, pa(n1) ) {
259 DAI_ASSERT( n2.iter == iter );
260 DAI_ASSERT( n2.node < N );
261 DAI_ASSERT( n2.dual < ch(n2).size() );
262 DAI_ASSERT( ch(n2, n2.dual) == n1 );
263 iter++;
264 }
265 iter = 0;
266 bforeach( const Neighbor &n2, ch(n1) ) {
267 DAI_ASSERT( n2.iter == iter );
268 DAI_ASSERT( n2.node < N );
269 DAI_ASSERT( n2.dual < pa(n2).size() );
270 DAI_ASSERT( pa(n2, n2.dual) == n1 );
271 iter++;
272 }
273 }
274 // Check acyclicity
275 for( size_t n1 = 0; n1 < N; n1++ )
276 bforeach( const Neighbor& n2, ch(n1) )
277 DAI_ASSERT( !existsDirectedPath( n2, n1 ) );
278 }
279
280
281 } // end of namespace dai