977652f1721e8f7f6150129d635dc041ff996580
[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 m such that there exists a directed path from \a m to \a n (excluding \a n itself)
133 std::set<size_t> DAG::ancestors( size_t n ) const {
134 set<size_t> anc;
135
136 set<size_t> curParents;
137 curParents.insert( n );
138 while( curParents.size() ) {
139 size_t node = *(curParents.begin());
140 // Add node to ancestors
141 if( node != n )
142 anc.insert( node );
143 // Add all parents of node to curParents
144 bforeach( const Neighbor& p, pa(node) )
145 curParents.insert( p.node );
146 // Erase node from curParents
147 curParents.erase( node );
148 }
149
150 return anc;
151 }
152
153
154 /// Returns the set of descendants of node \a n, i.e., all nodes \a m such that there exists a directed path from \a n to \a m (excluding \a n itself)
155 std::set<size_t> DAG::descendants( size_t n ) const {
156 set<size_t> desc;
157
158 set<size_t> curChildren;
159 curChildren.insert( n );
160 while( curChildren.size() ) {
161 size_t node = *(curChildren.begin());
162 // Add node to descendants
163 if( node != n )
164 desc.insert( node );
165 // Add all children of node to curChildren
166 bforeach( const Neighbor& c, ch(node) )
167 curChildren.insert( c.node );
168 // Erase node from curChildren
169 curChildren.erase( node );
170 }
171
172 return desc;
173 }
174
175
176 bool DAG::existsDirectedPath( size_t n1, size_t n2 ) const {
177 set<size_t> curChildren;
178
179 curChildren.insert( n1 );
180 while( curChildren.size() ) {
181 size_t node = *(curChildren.begin());
182 // If we reached n2, we found a directed path from n1 to n2
183 if( node == n2 )
184 return true;
185 // Add all children of node to curChildren
186 bforeach( const Neighbor& c, ch(node) )
187 curChildren.insert( c.node );
188 // Erase node from curChildren
189 curChildren.erase( node );
190 }
191 return false;
192 }
193
194
195 bool DAG::isConnected() const {
196 if( nrNodes() == 0 ) {
197 return true;
198 } else {
199 std::vector<bool> incomponent( nrNodes(), false );
200
201 incomponent[0] = true;
202 bool found_new_nodes;
203 do {
204 found_new_nodes = false;
205
206 // For all nodes, check if they are connected with the (growing) component
207 for( size_t n1 = 0; n1 < nrNodes(); n1++ ) {
208 if( !incomponent[n1] ) {
209 bforeach( const Neighbor &n2, pa(n1) )
210 if( incomponent[n2] ) {
211 found_new_nodes = true;
212 incomponent[n1] = true;
213 break;
214 }
215 }
216 if( !incomponent[n1] ) {
217 bforeach( const Neighbor &n2, ch(n1) )
218 if( incomponent[n2] ) {
219 found_new_nodes = true;
220 incomponent[n1] = true;
221 break;
222 }
223 }
224 }
225 } while( found_new_nodes );
226
227 // Check if there are remaining nodes (not in the component)
228 bool all_connected = true;
229 for( size_t n1 = 0; (n1 < nrNodes()) && all_connected; n1++ )
230 if( !incomponent[n1] )
231 all_connected = false;
232
233 return all_connected;
234 }
235 }
236
237
238 void DAG::printDot( std::ostream& os ) const {
239 os << "digraph DAG {" << endl;
240 os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
241 for( size_t n = 0; n < nrNodes(); n++ )
242 os << "\tx" << n << ";" << endl;
243 for( size_t n1 = 0; n1 < nrNodes(); n1++ )
244 bforeach( const Neighbor &n2, ch(n1) )
245 os << "\tx" << n1 << " -> x" << n2 << ";" << endl;
246 os << "}" << endl;
247 }
248
249
250 void DAG::checkConsistency() const {
251 size_t N = nrNodes();
252 for( size_t n1 = 0; n1 < N; n1++ ) {
253 size_t iter = 0;
254 bforeach( const Neighbor &n2, pa(n1) ) {
255 DAI_ASSERT( n2.iter == iter );
256 DAI_ASSERT( n2.node < N );
257 DAI_ASSERT( n2.dual < ch(n2).size() );
258 DAI_ASSERT( ch(n2, n2.dual) == n1 );
259 iter++;
260 }
261 iter = 0;
262 bforeach( const Neighbor &n2, ch(n1) ) {
263 DAI_ASSERT( n2.iter == iter );
264 DAI_ASSERT( n2.node < N );
265 DAI_ASSERT( n2.dual < pa(n2).size() );
266 DAI_ASSERT( pa(n2, n2.dual) == n1 );
267 iter++;
268 }
269 }
270 // Check acyclicity
271 for( size_t n1 = 0; n1 < N; n1++ )
272 bforeach( const Neighbor& n2, ch(n1) )
273 DAI_ASSERT( !existsDirectedPath( n2, n1 ) );
274 }
275
276
277 } // end of namespace dai