1 /* This file is part of libDAI - http://www.libdai.org/
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.
7 * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
12 #include <dai/graph.h>
13 #include <dai/weightedgraph.h>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/connected_components.hpp>
24 void GraphAL::addEdge( size_t n1
, size_t n2
, bool check
) {
25 DAI_ASSERT( n1
< nrNodes() );
26 DAI_ASSERT( n2
< nrNodes() );
29 // Check whether the edge already exists
30 foreach( const Neighbor
&n
, nb(n1
) )
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
);
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
);
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
60 nb( m
.node
, m
.dual
).dual
= iter
;
71 void GraphAL::eraseEdge( size_t n1
, size_t n2
) {
72 DAI_ASSERT( n1
< nrNodes() );
73 DAI_ASSERT( n2
< nrNodes() );
75 // Search for edge among neighbors of n1
76 for( iter
= 0; iter
< nb(n1
).size(); iter
++ )
77 if( nb(n1
, iter
).node
== n2
) {
79 nb(n1
).erase( nb(n1
).begin() + iter
);
82 // Change the iter and dual values of the subsequent neighbors
83 for( ; iter
< nb(n1
).size(); iter
++ ) {
84 Neighbor
&m
= nb( n1
, iter
);
86 nb( m
.node
, m
.dual
).dual
= iter
;
88 // Search for edge among neighbors of n2
89 for( iter
= 0; iter
< nb(n2
).size(); iter
++ )
90 if( nb(n2
, iter
).node
== n1
) {
92 nb(n2
).erase( nb(n2
).begin() + iter
);
95 // Change the iter and node values of the subsequent neighbors
96 for( ; iter
< nb(n2
).size(); iter
++ ) {
97 Neighbor
&m
= nb( n2
, iter
);
99 nb( m
.node
, m
.dual
).dual
= iter
;
104 bool GraphAL::isConnected() const {
105 if( nrNodes() == 0 ) {
108 std::vector
<bool> incomponent( nrNodes(), false );
110 incomponent
[0] = true;
111 bool found_new_nodes
;
113 found_new_nodes
= false;
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;
126 } while( found_new_nodes
);
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;
134 return all_connected
;
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;
141 // Copy graph structure into boostGraphAL object
143 edges.reserve( nrEdges() );
144 for( size_t n1 = 0; n1 < nrNodes(); n1++ )
145 foreach( const Neighbor &n2, nb(n1) )
147 edges.push_back( E( n1, n2 ) );
148 boostGraphAL g( edges.begin(), edges.end(), nrNodes() );
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)) );
154 return (num_comp == 1);
160 bool GraphAL::isTree() const {
162 vector
<levelType
> levels
;
164 bool foundCycle
= false;
173 if( levels
.size() == 0 ) {
176 newLevel
= vector
<size_t>( 1, n1
);
178 const levelType
&prevLevel
= levels
.back();
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
186 newLevel
.push_back( n1
); // add n1 to new level
195 levels
.push_back( newLevel
);
196 Nr
+= newLevel
.size();
197 } while( (newLevel
.size() != 0) && !foundCycle
);
198 if( Nr
== nrNodes() && !foundCycle
)
206 void GraphAL::printDot( std::ostream
& os
) const {
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
;
219 void GraphAL::checkConsistency() const {
220 size_t N
= nrNodes();
221 for( size_t n1
= 0; n1
< N
; n1
++ ) {
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
);
231 for( size_t n2
= 0; n2
< N
; n2
++ ) {
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
);
244 GraphAL
createGraphFull( size_t 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 );
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 );
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 );
282 GraphAL
createGraphLoop( size_t N
) {
284 for( size_t i
= 0; i
< N
; i
++ )
285 result
.addEdge( i
, (i
+1)%N
, N
<= 2 );
290 GraphAL
createGraphTree( size_t 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 );
300 GraphAL
createGraphRegular( size_t N
, size_t d
) {
301 GraphEL g
= RandomDRegularGraph( N
, d
);
302 return GraphAL( N
, g
.begin(), g
.end() );
306 } // end of namespace dai