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