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