e6e3244ae50f3c6043abfa14fb1aa9dd5b0b3009
[libdai.git] / src / bipgraph.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/bipgraph.h>
13
14
15 namespace dai {
16
17
18 using namespace std;
19
20
21 void BipartiteGraph::addEdge( size_t n1, size_t n2, bool check ) {
22 DAI_ASSERT( n1 < nrNodes1() );
23 DAI_ASSERT( n2 < nrNodes2() );
24 bool exists = false;
25 if( check ) {
26 // Check whether the edge already exists
27 foreach( const Neighbor &nb2, nb1(n1) )
28 if( nb2 == n2 ) {
29 exists = true;
30 break;
31 }
32 }
33 if( !exists ) { // Add edge
34 Neighbor nb_1( nb1(n1).size(), n2, nb2(n2).size() );
35 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
36 nb1(n1).push_back( nb_1 );
37 nb2(n2).push_back( nb_2 );
38 }
39 }
40
41
42 void BipartiteGraph::eraseNode1( size_t n1 ) {
43 DAI_ASSERT( n1 < nrNodes1() );
44 // Erase neighbor entry of node n1
45 _nb1.erase( _nb1.begin() + n1 );
46 // Adjust neighbor entries of nodes of type 2
47 for( size_t n2 = 0; n2 < nrNodes2(); n2++ ) {
48 for( size_t iter = 0; iter < nb2(n2).size(); ) {
49 Neighbor &m1 = nb2(n2, iter);
50 if( m1.node == n1 ) {
51 // delete this entry, because it points to the deleted node
52 nb2(n2).erase( nb2(n2).begin() + iter );
53 } else if( m1.node > n1 ) {
54 // update this entry and the corresponding dual of the neighboring node of type 1
55 m1.node--;
56 nb1( m1.node, m1.dual ).dual = iter;
57 m1.iter = iter++;
58 } else {
59 // update this entry and the corresponding dual of the neighboring node of type 1
60 nb1( m1.node, m1.dual ).dual = iter;
61 m1.iter = iter++;
62 }
63 }
64 }
65 }
66
67
68 void BipartiteGraph::eraseNode2( size_t n2 ) {
69 DAI_ASSERT( n2 < nrNodes2() );
70 // Erase neighbor entry of node n2
71 _nb2.erase( _nb2.begin() + n2 );
72 // Adjust neighbor entries of nodes of type 1
73 for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
74 for( size_t iter = 0; iter < nb1(n1).size(); ) {
75 Neighbor &m2 = nb1(n1, iter);
76 if( m2.node == n2 ) {
77 // delete this entry, because it points to the deleted node
78 nb1(n1).erase( nb1(n1).begin() + iter );
79 } else if( m2.node > n2 ) {
80 // update this entry and the corresponding dual of the neighboring node of type 2
81 m2.node--;
82 nb2( m2.node, m2.dual ).dual = iter;
83 m2.iter = iter++;
84 } else {
85 // update this entry and the corresponding dual of the neighboring node of type 2
86 nb2( m2.node, m2.dual ).dual = iter;
87 m2.iter = iter++;
88 }
89 }
90 }
91 }
92
93
94 void BipartiteGraph::eraseEdge( size_t n1, size_t n2 ) {
95 DAI_ASSERT( n1 < nrNodes1() );
96 DAI_ASSERT( n2 < nrNodes2() );
97 size_t iter;
98 // Search for edge among neighbors of n1
99 for( iter = 0; iter < nb1(n1).size(); iter++ )
100 if( nb1(n1, iter).node == n2 ) {
101 // Remove it
102 nb1(n1).erase( nb1(n1).begin() + iter );
103 break;
104 }
105 // Change the iter and dual values of the subsequent neighbors
106 for( ; iter < nb1(n1).size(); iter++ ) {
107 Neighbor &m2 = nb1( n1, iter );
108 m2.iter = iter;
109 nb2( m2.node, m2.dual ).dual = iter;
110 }
111 // Search for edge among neighbors of n2
112 for( iter = 0; iter < nb2(n2).size(); iter++ )
113 if( nb2(n2, iter).node == n1 ) {
114 // Remove it
115 nb2(n2).erase( nb2(n2).begin() + iter );
116 break;
117 }
118 // Change the iter and node values of the subsequent neighbors
119 for( ; iter < nb2(n2).size(); iter++ ) {
120 Neighbor &m1 = nb2( n2, iter );
121 m1.iter = iter;
122 nb1( m1.node, m1.dual ).dual = iter;
123 }
124 }
125
126
127 SmallSet<size_t> BipartiteGraph::nb1Set( size_t n1 ) const {
128 SmallSet<size_t> result;
129 foreach( const Neighbor &n2, nb1(n1) )
130 result |= n2;
131 return result;
132 }
133
134
135 SmallSet<size_t> BipartiteGraph::nb2Set( size_t n2 ) const {
136 SmallSet<size_t> result;
137 foreach( const Neighbor &n1, nb2(n2) )
138 result |= n1;
139 return result;
140 }
141
142
143 SmallSet<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
144 // get all second-order neighbors
145 SmallSet<size_t> result;
146 foreach( const Neighbor &n2, nb1(n1) )
147 foreach( const Neighbor &m1, nb2(n2) )
148 if( include || (m1 != n1) )
149 result |= m1;
150 return result;
151 }
152
153
154 SmallSet<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
155 // store all second-order neighbors
156 SmallSet<size_t> result;
157 foreach( const Neighbor &n1, nb2(n2) )
158 foreach( const Neighbor &m2, nb1(n1) )
159 if( include || (m2 != n2) )
160 result |= m2;
161 return result;
162 }
163
164
165 bool BipartiteGraph::isConnected() const {
166 if( nrNodes1() == 0 ) {
167 return true;
168 } else {
169 /*
170 // The BGL implementation is significantly slower...
171 using namespace boost;
172 typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int> > boostGraph;
173 typedef pair<size_t, size_t> E;
174
175 // Copy graph structure into boostGraph object
176 size_t N = nrNodes1();
177 vector<E> edges;
178 edges.reserve( nrEdges() );
179 for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
180 foreach( const Neighbor &n2, nb1(n1) )
181 edges.push_back( E( n1, n2.node + N ) );
182 boostGraph g( edges.begin(), edges.end(), nrNodes1() + nrNodes2() );
183
184 // Construct connected components using Boost Graph Library
185 std::vector<int> component( num_vertices( g ) );
186 int num_comp = connected_components( g, make_iterator_property_map(component.begin(), get(vertex_index, g)) );
187
188 return (num_comp == 1);
189 */
190
191 std::vector<bool> incomponent1( nrNodes1(), false );
192 std::vector<bool> incomponent2( nrNodes2(), false );
193
194 incomponent1[0] = true;
195 bool found_new_nodes;
196 do {
197 found_new_nodes = false;
198
199 // For all nodes of type 2, check if they are connected with the (growing) component
200 for( size_t n2 = 0; n2 < nrNodes2(); n2++ )
201 if( !incomponent2[n2] ) {
202 foreach( const Neighbor &n1, nb2(n2) ) {
203 if( incomponent1[n1] ) {
204 found_new_nodes = true;
205 incomponent2[n2] = true;
206 break;
207 }
208 }
209 }
210
211 // For all nodes of type 1, check if they are connected with the (growing) component
212 for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
213 if( !incomponent1[n1] ) {
214 foreach( const Neighbor &n2, nb1(n1) ) {
215 if( incomponent2[n2] ) {
216 found_new_nodes = true;
217 incomponent1[n1] = true;
218 break;
219 }
220 }
221 }
222 } while( found_new_nodes );
223
224 // Check if there are remaining nodes (not in the component)
225 bool all_connected = true;
226 for( size_t n1 = 0; (n1 < nrNodes1()) && all_connected; n1++ )
227 if( !incomponent1[n1] )
228 all_connected = false;
229 for( size_t n2 = 0; (n2 < nrNodes2()) && all_connected; n2++ )
230 if( !incomponent2[n2] )
231 all_connected = false;
232
233 return all_connected;
234 }
235 }
236
237
238 bool BipartiteGraph::isTree() const {
239 vector<levelType> levels;
240
241 bool foundCycle = false;
242 size_t nr_1 = 0;
243 size_t nr_2 = 0;
244
245 if( nrNodes1() == 0 )
246 return (nrNodes2() < 2 );
247 else if( nrNodes2() == 0 )
248 return (nrNodes1() < 2 );
249 else {
250 levelType newLevel;
251 do {
252 newLevel.ind1.clear();
253 newLevel.ind2.clear();
254 if( levels.size() == 0 ) {
255 size_t n1 = 0;
256 // add n1 to ind1
257 newLevel.ind1 = vector<size_t>( 1, n1 );
258 // add all neighbors of n1 to ind2
259 newLevel.ind2.reserve( nb1(n1).size() );
260 foreach( const Neighbor &n2, nb1(n1) )
261 newLevel.ind2.push_back( n2 );
262 } else {
263 const levelType &prevLevel = levels.back();
264 // build newLevel.ind1
265 foreach( size_t n2, prevLevel.ind2 ) { // for all n2 in the previous level
266 foreach( const Neighbor &n1, nb2(n2) ) { // for all neighbors n1 of n2
267 if( find( prevLevel.ind1.begin(), prevLevel.ind1.end(), n1 ) == prevLevel.ind1.end() ) { // n1 not in previous level
268 if( find( newLevel.ind1.begin(), newLevel.ind1.end(), n1 ) != newLevel.ind1.end() )
269 foundCycle = true; // n1 already in new level: we found a cycle
270 else
271 newLevel.ind1.push_back( n1 ); // add n1 to new level
272 }
273 if( foundCycle )
274 break;
275 }
276 if( foundCycle )
277 break;
278 }
279 // build newLevel.ind2
280 foreach( size_t n1, newLevel.ind1 ) { // for all n1 in this level
281 foreach( const Neighbor &n2, nb1(n1) ) { // for all neighbors n2 of n1
282 if( find( prevLevel.ind2.begin(), prevLevel.ind2.end(), n2 ) == prevLevel.ind2.end() ) { // n2 not in previous level
283 if( find( newLevel.ind2.begin(), newLevel.ind2.end(), n2 ) != newLevel.ind2.end() )
284 foundCycle = true; // n2 already in new level: we found a cycle
285 else
286 newLevel.ind2.push_back( n2 ); // add n2 to new level
287 }
288 if( foundCycle )
289 break;
290 }
291 if( foundCycle )
292 break;
293 }
294 }
295 levels.push_back( newLevel );
296 nr_1 += newLevel.ind1.size();
297 nr_2 += newLevel.ind2.size();
298 } while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
299 if( nr_1 == nrNodes1() && nr_2 == nrNodes2() && !foundCycle )
300 return true;
301 else
302 return false;
303 }
304 }
305
306
307 void BipartiteGraph::printDot( std::ostream& os ) const {
308 os << "graph BipartiteGraph {" << endl;
309 os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
310 for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
311 os << "\tx" << n1 << ";" << endl;
312 os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
313 for( size_t n2 = 0; n2 < nrNodes2(); n2++ )
314 os << "\ty" << n2 << ";" << endl;
315 for( size_t n1 = 0; n1 < nrNodes1(); n1++ )
316 foreach( const Neighbor &n2, nb1(n1) )
317 os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
318 os << "}" << endl;
319 }
320
321
322 void BipartiteGraph::checkConsistency() const {
323 size_t N1 = nrNodes1();
324 size_t N2 = nrNodes2();
325 for( size_t n1 = 0; n1 < N1; n1++ ) {
326 size_t iter = 0;
327 foreach( const Neighbor &n2, nb1(n1) ) {
328 DAI_ASSERT( n2.iter == iter );
329 DAI_ASSERT( n2.node < N2 );
330 DAI_ASSERT( n2.dual < nb2(n2).size() );
331 DAI_ASSERT( nb2(n2, n2.dual) == n1 );
332 iter++;
333 }
334 }
335 for( size_t n2 = 0; n2 < N2; n2++ ) {
336 size_t iter = 0;
337 foreach( const Neighbor &n1, nb2(n2) ) {
338 DAI_ASSERT( n1.iter == iter );
339 DAI_ASSERT( n1.node < N1 );
340 DAI_ASSERT( n1.dual < nb1(n1).size() );
341 DAI_ASSERT( nb1(n1, n1.dual) == n2 );
342 iter++;
343 }
344 }
345 }
346
347
348 } // end of namespace dai