Merge branch 'pletscher'
[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
14
15 namespace dai {
16
17
18 using namespace std;
19
20
21 void BipartiteGraph::erase1( size_t n1 ) {
22 DAI_ASSERT( n1 < nr1() );
23 // Erase neighbor entry of node n1
24 _nb1.erase( _nb1.begin() + n1 );
25 // Adjust neighbor entries of nodes of type 2
26 for( size_t n2 = 0; n2 < nr2(); n2++ ) {
27 for( size_t iter = 0; iter < nb2(n2).size(); ) {
28 Neighbor &m1 = nb2(n2, iter);
29 if( m1.node == n1 ) {
30 // delete this entry, because it points to the deleted node
31 nb2(n2).erase( nb2(n2).begin() + iter );
32 } else if( m1.node > n1 ) {
33 // update this entry and the corresponding dual of the neighboring node of type 1
34 m1.iter = iter;
35 m1.node--;
36 nb1( m1.node, m1.dual ).dual = iter;
37 iter++;
38 } else {
39 // skip
40 iter++;
41 }
42 }
43 }
44 }
45
46
47 void BipartiteGraph::erase2( size_t n2 ) {
48 DAI_ASSERT( n2 < nr2() );
49 // Erase neighbor entry of node n2
50 _nb2.erase( _nb2.begin() + n2 );
51 // Adjust neighbor entries of nodes of type 1
52 for( size_t n1 = 0; n1 < nr1(); n1++ ) {
53 for( size_t iter = 0; iter < nb1(n1).size(); ) {
54 Neighbor &m2 = nb1(n1, iter);
55 if( m2.node == n2 ) {
56 // delete this entry, because it points to the deleted node
57 nb1(n1).erase( nb1(n1).begin() + iter );
58 } else if( m2.node > n2 ) {
59 // update this entry and the corresponding dual of the neighboring node of type 2
60 m2.iter = iter;
61 m2.node--;
62 nb2( m2.node, m2.dual ).dual = iter;
63 iter++;
64 } else {
65 // skip
66 iter++;
67 }
68 }
69 }
70 }
71
72
73 std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
74 // get all second-order neighbors
75 std::vector<size_t> result;
76 foreach( const Neighbor &n2, nb1(n1) )
77 foreach( const Neighbor &m1, nb2(n2) )
78 if( include || (m1 != n1) )
79 result.push_back( m1 );
80 // remove duplicates
81 std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
82 result.erase( it, result.end() );
83 return result;
84 }
85
86
87 std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
88 // store all second-order neighbors
89 std::vector<size_t> result;
90 foreach( const Neighbor &n1, nb2(n2) )
91 foreach( const Neighbor &m2, nb1(n1) )
92 if( include || (m2 != n2) )
93 result.push_back( m2 );
94 // remove duplicates
95 std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
96 result.erase( it, result.end() );
97 return result;
98 }
99
100
101 bool BipartiteGraph::isConnected() const {
102 // TODO: use BGL, like:
103 // std::vector<int> component( num_vertices( g ) );
104 // int num_comp = connected_components( g, make_iterator_property_map(component.begin(), get(vertex_index, g)) );
105 if( nr1() == 0 ) {
106 return true;
107 } else {
108 std::vector<bool> incomponent1( nr1(), false );
109 std::vector<bool> incomponent2( nr2(), false );
110
111 incomponent1[0] = true;
112 bool found_new_nodes;
113 do {
114 found_new_nodes = false;
115
116 // For all nodes of type 2, check if they are connected with the (growing) component
117 for( size_t n2 = 0; n2 < nr2(); n2++ )
118 if( !incomponent2[n2] ) {
119 foreach( const Neighbor &n1, nb2(n2) ) {
120 if( incomponent1[n1] ) {
121 found_new_nodes = true;
122 incomponent2[n2] = true;
123 break;
124 }
125 }
126 }
127
128 // For all nodes of type 1, check if they are connected with the (growing) component
129 for( size_t n1 = 0; n1 < nr1(); n1++ )
130 if( !incomponent1[n1] ) {
131 foreach( const Neighbor &n2, nb1(n1) ) {
132 if( incomponent2[n2] ) {
133 found_new_nodes = true;
134 incomponent1[n1] = true;
135 break;
136 }
137 }
138 }
139 } while( found_new_nodes );
140
141 // Check if there are remaining nodes (not in the component)
142 bool all_connected = true;
143 for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
144 if( !incomponent1[n1] )
145 all_connected = false;
146 for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
147 if( !incomponent2[n2] )
148 all_connected = false;
149
150 return all_connected;
151 }
152 }
153
154
155 bool BipartiteGraph::isTree() const {
156 using namespace std;
157 vector<levelType> levels;
158
159 bool foundCycle = false;
160 size_t nr_1 = 0;
161 size_t nr_2 = 0;
162
163 if( nr1() == 0 || nr2() == 0 )
164 return true;
165 else {
166 levelType newLevel;
167 do {
168 newLevel.ind1.clear();
169 newLevel.ind2.clear();
170 if( levels.size() == 0 ) {
171 size_t n1 = 0;
172 // add n1 to ind1
173 newLevel.ind1 = vector<size_t>( 1, n1 );
174 // add all neighbors of n1 to ind2
175 newLevel.ind2.reserve( nb1(n1).size() );
176 foreach( const Neighbor &n2, nb1(n1) )
177 newLevel.ind2.push_back( n2 );
178 } else {
179 const levelType &prevLevel = levels.back();
180 // build newLevel.ind1
181 foreach( size_t n2, prevLevel.ind2 ) { // for all n2 in the previous level
182 foreach( const Neighbor &n1, nb2(n2) ) { // for all neighbors n1 of n2
183 if( find( prevLevel.ind1.begin(), prevLevel.ind1.end(), n1 ) == prevLevel.ind1.end() ) { // n1 not in previous level
184 if( find( newLevel.ind1.begin(), newLevel.ind1.end(), n1 ) != newLevel.ind1.end() )
185 foundCycle = true; // n1 already in new level: we found a cycle
186 else
187 newLevel.ind1.push_back( n1 ); // add n1 to new level
188 }
189 if( foundCycle )
190 break;
191 }
192 if( foundCycle )
193 break;
194 }
195 // build newLevel.ind2
196 foreach( size_t n1, newLevel.ind1 ) { // for all n1 in this level
197 foreach( const Neighbor &n2, nb1(n1) ) { // for all neighbors n2 of n1
198 if( find( prevLevel.ind2.begin(), prevLevel.ind2.end(), n2 ) == prevLevel.ind2.end() ) { // n2 not in previous level
199 if( find( newLevel.ind2.begin(), newLevel.ind2.end(), n2 ) != newLevel.ind2.end() )
200 foundCycle = true; // n2 already in new level: we found a cycle
201 else
202 newLevel.ind2.push_back( n2 ); // add n2 to new level
203 }
204 if( foundCycle )
205 break;
206 }
207 if( foundCycle )
208 break;
209 }
210 }
211 levels.push_back( newLevel );
212 nr_1 += newLevel.ind1.size();
213 nr_2 += newLevel.ind2.size();
214 } while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
215 if( nr_1 == nr1() && nr_2 == nr2() && !foundCycle )
216 return true;
217 else
218 return false;
219 }
220 }
221
222
223 void BipartiteGraph::printDot( std::ostream& os ) const {
224 using namespace std;
225 os << "graph G {" << endl;
226 os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
227 for( size_t n1 = 0; n1 < nr1(); n1++ )
228 os << "\tx" << n1 << ";" << endl;
229 os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
230 for( size_t n2 = 0; n2 < nr2(); n2++ )
231 os << "\ty" << n2 << ";" << endl;
232 for( size_t n1 = 0; n1 < nr1(); n1++ )
233 foreach( const Neighbor &n2, nb1(n1) )
234 os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
235 os << "}" << endl;
236 }
237
238
239 void BipartiteGraph::check() const {
240 size_t N1 = nr1();
241 size_t N2 = nr2();
242 for( size_t n1 = 0; n1 < N1; n1++ ) {
243 size_t iter = 0;
244 foreach( const Neighbor &n2, nb1(n1) ) {
245 DAI_ASSERT( n2.iter == iter );
246 DAI_ASSERT( n2.node < N2 );
247 DAI_ASSERT( n2.dual < nb2(n2).size() );
248 DAI_ASSERT( nb2(n2, n2.dual) == n1 );
249 iter++;
250 }
251 }
252 for( size_t n2 = 0; n2 < N2; n2++ ) {
253 size_t iter = 0;
254 foreach( const Neighbor &n1, nb2(n2) ) {
255 DAI_ASSERT( n1.iter == iter );
256 DAI_ASSERT( n1.node < N1 );
257 DAI_ASSERT( n1.dual < nb1(n1).size() );
258 DAI_ASSERT( nb1(n1, n1.dual) == n2 );
259 iter++;
260 }
261 }
262 }
263
264
265 } // end of namespace dai