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