Various changes:
[libdai.git] / src / graph.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) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 #include <dai/graph.h>
13 #include <dai/weightedgraph.h>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/connected_components.hpp>
16
17
18 namespace dai {
19
20
21 using namespace std;
22
23
24 void GraphAL::addEdge( size_t n1, size_t n2, bool check ) {
25 DAI_ASSERT( n1 < nrNodes() );
26 DAI_ASSERT( n2 < nrNodes() );
27 bool exists = false;
28 if( check ) {
29 // Check whether the edge already exists
30 foreach( const Neighbor &n, nb(n1) )
31 if( n == n2 ) {
32 exists = true;
33 break;
34 }
35 }
36 if( !exists ) { // Add edge
37 Neighbor nb_1( nb(n1).size(), n2, nb(n2).size() );
38 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
39 nb(n1).push_back( nb_1 );
40 nb(n2).push_back( nb_2 );
41 }
42 }
43
44
45 void GraphAL::eraseNode( size_t n ) {
46 DAI_ASSERT( n < nrNodes() );
47 // Erase neighbor entry of node n
48 _nb.erase( _nb.begin() + n );
49 // Adjust neighbor entries of nodes
50 for( size_t n2 = 0; n2 < nrNodes(); n2++ ) {
51 for( size_t iter = 0; iter < nb(n2).size(); ) {
52 Neighbor &m = nb(n2, iter);
53 if( m.node == n ) {
54 // delete this entry, because it points to the deleted node
55 nb(n2).erase( nb(n2).begin() + iter );
56 } else if( m.node > n ) {
57 // update this entry and the corresponding dual of the neighboring node
58 m.iter = iter;
59 m.node--;
60 nb( m.node, m.dual ).dual = iter;
61 iter++;
62 } else {
63 // skip
64 iter++;
65 }
66 }
67 }
68 }
69
70
71 void GraphAL::eraseEdge( size_t n1, size_t n2 ) {
72 DAI_ASSERT( n1 < nrNodes() );
73 DAI_ASSERT( n2 < nrNodes() );
74 size_t iter;
75 // Search for edge among neighbors of n1
76 for( iter = 0; iter < nb(n1).size(); iter++ )
77 if( nb(n1, iter).node == n2 ) {
78 // Remove it
79 nb(n1).erase( nb(n1).begin() + iter );
80 break;
81 }
82 // Change the iter and dual values of the subsequent neighbors
83 for( ; iter < nb(n1).size(); iter++ ) {
84 Neighbor &m = nb( n1, iter );
85 m.iter = iter;
86 nb( m.node, m.dual ).dual = iter;
87 }
88 // Search for edge among neighbors of n2
89 for( iter = 0; iter < nb(n2).size(); iter++ )
90 if( nb(n2, iter).node == n1 ) {
91 // Remove it
92 nb(n2).erase( nb(n2).begin() + iter );
93 break;
94 }
95 // Change the iter and node values of the subsequent neighbors
96 for( ; iter < nb(n2).size(); iter++ ) {
97 Neighbor &m = nb( n2, iter );
98 m.iter = iter;
99 nb( m.node, m.dual ).dual = iter;
100 }
101 }
102
103
104 bool GraphAL::isConnected() const {
105 if( nrNodes() == 0 ) {
106 return true;
107 } else {
108 std::vector<bool> incomponent( nrNodes(), false );
109
110 incomponent[0] = true;
111 bool found_new_nodes;
112 do {
113 found_new_nodes = false;
114
115 // For all nodes, check if they are connected with the (growing) component
116 for( size_t n1 = 0; n1 < nrNodes(); n1++ )
117 if( !incomponent[n1] ) {
118 foreach( const Neighbor &n2, nb(n1) ) {
119 if( incomponent[n2] ) {
120 found_new_nodes = true;
121 incomponent[n1] = true;
122 break;
123 }
124 }
125 }
126 } while( found_new_nodes );
127
128 // Check if there are remaining nodes (not in the component)
129 bool all_connected = true;
130 for( size_t n1 = 0; (n1 < nrNodes()) && all_connected; n1++ )
131 if( !incomponent[n1] )
132 all_connected = false;
133
134 return all_connected;
135
136 // BGL implementation is slower...
137 /* using namespace boost;
138 typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int> > boostGraphAL;
139 typedef pair<size_t, size_t> E;
140
141 // Copy graph structure into boostGraphAL object
142 vector<E> edges;
143 edges.reserve( nrEdges() );
144 for( size_t n1 = 0; n1 < nrNodes(); n1++ )
145 foreach( const Neighbor &n2, nb(n1) )
146 if( n1 < n2 )
147 edges.push_back( E( n1, n2 ) );
148 boostGraphAL g( edges.begin(), edges.end(), nrNodes() );
149
150 // Construct connected components using Boost GraphAL Library
151 std::vector<int> component( num_vertices( g ) );
152 int num_comp = connected_components( g, make_iterator_property_map(component.begin(), get(vertex_index, g)) );
153
154 return (num_comp == 1);
155 */
156 }
157 }
158
159
160 bool GraphAL::isTree() const {
161 using namespace std;
162 vector<levelType> levels;
163
164 bool foundCycle = false;
165 size_t Nr = 0;
166
167 if( nrNodes() == 0 )
168 return true;
169 else {
170 levelType newLevel;
171 do {
172 newLevel.clear();
173 if( levels.size() == 0 ) {
174 size_t n1 = 0;
175 // add n1
176 newLevel = vector<size_t>( 1, n1 );
177 } else {
178 const levelType &prevLevel = levels.back();
179 // build newLevel
180 foreach( size_t n2, prevLevel ) { // for all n2 in the previous level
181 foreach( const Neighbor &n1, nb(n2) ) { // for all neighbors n1 of n2
182 if( find( prevLevel.begin(), prevLevel.end(), n1 ) == prevLevel.end() ) { // n1 not in previous level
183 if( find( newLevel.begin(), newLevel.end(), n1 ) != newLevel.end() )
184 foundCycle = true; // n1 already in new level: we found a cycle
185 else
186 newLevel.push_back( n1 ); // add n1 to new level
187 }
188 if( foundCycle )
189 break;
190 }
191 if( foundCycle )
192 break;
193 }
194 }
195 levels.push_back( newLevel );
196 Nr += newLevel.size();
197 } while( (newLevel.size() != 0) && !foundCycle );
198 if( Nr == nrNodes() && !foundCycle )
199 return true;
200 else
201 return false;
202 }
203 }
204
205
206 void GraphAL::printDot( std::ostream& os ) const {
207 using namespace std;
208 os << "graph G {" << endl;
209 os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
210 for( size_t n = 0; n < nrNodes(); n++ )
211 os << "\tx" << n << ";" << endl;
212 for( size_t n1 = 0; n1 < nrNodes(); n1++ )
213 foreach( const Neighbor &n2, nb(n1) )
214 os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
215 os << "}" << endl;
216 }
217
218
219 void GraphAL::checkConsistency() const {
220 size_t N = nrNodes();
221 for( size_t n1 = 0; n1 < N; n1++ ) {
222 size_t iter = 0;
223 foreach( const Neighbor &n2, nb(n1) ) {
224 DAI_ASSERT( n2.iter == iter );
225 DAI_ASSERT( n2.node < N );
226 DAI_ASSERT( n2.dual < nb(n2).size() );
227 DAI_ASSERT( nb(n2, n2.dual) == n1 );
228 iter++;
229 }
230 }
231 for( size_t n2 = 0; n2 < N; n2++ ) {
232 size_t iter = 0;
233 foreach( const Neighbor &n1, nb(n2) ) {
234 DAI_ASSERT( n1.iter == iter );
235 DAI_ASSERT( n1.node < N );
236 DAI_ASSERT( n1.dual < nb(n1).size() );
237 DAI_ASSERT( nb(n1, n1.dual) == n2 );
238 iter++;
239 }
240 }
241 }
242
243
244 GraphAL createGraphFull( size_t N ) {
245 GraphAL result( N );
246 for( size_t i = 0; i < N; i++ )
247 for( size_t j = i+1; j < N; j++ )
248 result.addEdge( i, j, false );
249 return result;
250 }
251
252
253 GraphAL createGraphGrid( size_t n1, size_t n2, bool periodic ) {
254 GraphAL result( n1*n2 );
255 for( size_t i1 = 0; i1 < n1; i1++ )
256 for( size_t i2 = 0; i2 < n2; i2++ ) {
257 if( i1+1 < n1 || periodic )
258 result.addEdge( i1*n2 + i2, ((i1+1)%n1)*n2 + i2, n1 <= 2 );
259 if( i2+1 < n2 || periodic )
260 result.addEdge( i1*n2 + i2, i1*n2 + ((i2+1)%n2), n2 <= 2 );
261 }
262 return result;
263 }
264
265
266 GraphAL createGraphGrid3D( size_t n1, size_t n2, size_t n3, bool periodic ) {
267 GraphAL result( n1*n2*n3 );
268 for( size_t i1 = 0; i1 < n1; i1++ )
269 for( size_t i2 = 0; i2 < n2; i2++ )
270 for( size_t i3 = 0; i3 < n3; i3++ ) {
271 if( i1+1 < n1 || periodic )
272 result.addEdge( i1*n2*n3 + i2*n3 + i3, ((i1+1)%n1)*n2*n3 + i2*n3 + i3, n1 <= 2 );
273 if( i2+1 < n2 || periodic )
274 result.addEdge( i1*n2*n3 + i2*n3 + i3, i1*n2*n3 + ((i2+1)%n2)*n3 + i3, n2 <= 2 );
275 if( i3+1 < n2 || periodic )
276 result.addEdge( i1*n2*n3 + i2*n3 + i3, i1*n2*n3 + i2*n3 + ((i3+1)%n3), n3 <= 2 );
277 }
278 return result;
279 }
280
281
282 GraphAL createGraphLoop( size_t N ) {
283 GraphAL result( N );
284 for( size_t i = 0; i < N; i++ )
285 result.addEdge( i, (i+1)%N, N <= 2 );
286 return result;
287 }
288
289
290 GraphAL createGraphTree( size_t N ) {
291 GraphAL result( N );
292 for( size_t i = 1; i < N; i++ ) {
293 size_t j = rnd_int( 0, i-1 );
294 result.addEdge( i, j, false );
295 }
296 return result;
297 }
298
299
300 GraphAL createGraphRegular( size_t N, size_t d ) {
301 GraphEL g = RandomDRegularGraph( N, d );
302 return GraphAL( N, g.begin(), g.end() );
303 }
304
305
306 } // end of namespace dai