Merge branch 'joris'
[libdai.git] / src / bipgraph.cpp
1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
4
5 This file is part of libDAI.
6
7 libDAI is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 libDAI is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with libDAI; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22
23 #include <dai/bipgraph.h>
24
25
26 namespace dai {
27
28
29 using namespace std;
30
31
32 void BipartiteGraph::erase1( size_t n1 ) {
33 assert( n1 < nr1() );
34 // Erase neighbor entry of node n1
35 _nb1.erase( _nb1.begin() + n1 );
36 // Adjust neighbor entries of nodes of type 2
37 for( size_t n2 = 0; n2 < nr2(); n2++ ) {
38 for( size_t iter = 0; iter < nb2(n2).size(); ) {
39 Neighbor &m1 = nb2(n2, iter);
40 if( m1.node == n1 ) {
41 // delete this entry, because it points to the deleted node
42 nb2(n2).erase( nb2(n2).begin() + iter );
43 } else if( m1.node > n1 ) {
44 // update this entry and the corresponding dual of the neighboring node of type 1
45 m1.iter = iter;
46 m1.node--;
47 nb1( m1.node, m1.dual ).dual = iter;
48 iter++;
49 } else {
50 // skip
51 iter++;
52 }
53 }
54 }
55 }
56
57
58 void BipartiteGraph::erase2( size_t n2 ) {
59 assert( n2 < nr2() );
60 // Erase neighbor entry of node n2
61 _nb2.erase( _nb2.begin() + n2 );
62 // Adjust neighbor entries of nodes of type 1
63 for( size_t n1 = 0; n1 < nr1(); n1++ ) {
64 for( size_t iter = 0; iter < nb1(n1).size(); ) {
65 Neighbor &m2 = nb1(n1, iter);
66 if( m2.node == n2 ) {
67 // delete this entry, because it points to the deleted node
68 nb1(n1).erase( nb1(n1).begin() + iter );
69 } else if( m2.node > n2 ) {
70 // update this entry and the corresponding dual of the neighboring node of type 2
71 m2.iter = iter;
72 m2.node--;
73 nb2( m2.node, m2.dual ).dual = iter;
74 iter++;
75 } else {
76 // skip
77 iter++;
78 }
79 }
80 }
81 }
82
83
84 std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
85 // get all second-order neighbors
86 std::vector<size_t> result;
87 foreach( const Neighbor &n2, nb1(n1) )
88 foreach( const Neighbor &m1, nb2(n2) )
89 if( include || (m1 != n1) )
90 result.push_back( m1 );
91 // remove duplicates
92 std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
93 result.erase( it, result.end() );
94 return result;
95 }
96
97
98 std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
99 // store all second-order neighbors
100 std::vector<size_t> result;
101 foreach( const Neighbor &n1, nb2(n2) )
102 foreach( const Neighbor &m2, nb1(n1) )
103 if( include || (m2 != n2) )
104 result.push_back( m2 );
105 // remove duplicates
106 std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
107 result.erase( it, result.end() );
108 return result;
109 }
110
111
112 bool BipartiteGraph::isConnected() const {
113 // TODO: use BGL, like:
114 // std::vector<int> component( num_vertices( g ) );
115 // int num_comp = connected_components( g, make_iterator_property_map(component.begin(), get(vertex_index, g)) );
116 if( nr1() == 0 ) {
117 return true;
118 } else {
119 std::vector<bool> incomponent1( nr1(), false );
120 std::vector<bool> incomponent2( nr2(), false );
121
122 incomponent1[0] = true;
123 bool found_new_nodes;
124 do {
125 found_new_nodes = false;
126
127 // For all nodes of type 2, check if they are connected with the (growing) component
128 for( size_t n2 = 0; n2 < nr2(); n2++ )
129 if( !incomponent2[n2] ) {
130 foreach( const Neighbor &n1, nb2(n2) ) {
131 if( incomponent1[n1] ) {
132 found_new_nodes = true;
133 incomponent2[n2] = true;
134 break;
135 }
136 }
137 }
138
139 // For all nodes of type 1, check if they are connected with the (growing) component
140 for( size_t n1 = 0; n1 < nr1(); n1++ )
141 if( !incomponent1[n1] ) {
142 foreach( const Neighbor &n2, nb1(n1) ) {
143 if( incomponent2[n2] ) {
144 found_new_nodes = true;
145 incomponent1[n1] = true;
146 break;
147 }
148 }
149 }
150 } while( found_new_nodes );
151
152 // Check if there are remaining nodes (not in the component)
153 bool all_connected = true;
154 for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
155 if( !incomponent1[n1] )
156 all_connected = false;
157 for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
158 if( !incomponent2[n2] )
159 all_connected = false;
160
161 return all_connected;
162 }
163 }
164
165
166 bool BipartiteGraph::isTree() const {
167 using namespace std;
168 vector<levelType> levels;
169
170 bool foundCycle = false;
171 size_t nr_1 = 0;
172 size_t nr_2 = 0;
173
174 if( nr1() == 0 || nr2() == 0 )
175 return true;
176 else {
177 levelType newLevel;
178 do {
179 newLevel.ind1.clear();
180 newLevel.ind2.clear();
181 if( levels.size() == 0 ) {
182 size_t n1 = 0;
183 // add n1 to ind1
184 newLevel.ind1 = vector<size_t>( 1, n1 );
185 // add all neighbors of n1 to ind2
186 newLevel.ind2.reserve( nb1(n1).size() );
187 foreach( const Neighbor &n2, nb1(n1) )
188 newLevel.ind2.push_back( n2 );
189 } else {
190 const levelType &prevLevel = levels.back();
191 // build newLevel.ind1
192 foreach( size_t n2, prevLevel.ind2 ) { // for all n2 in the previous level
193 foreach( const Neighbor &n1, nb2(n2) ) { // for all neighbors n1 of n2
194 if( find( prevLevel.ind1.begin(), prevLevel.ind1.end(), n1 ) == prevLevel.ind1.end() ) { // n1 not in previous level
195 if( find( newLevel.ind1.begin(), newLevel.ind1.end(), n1 ) != newLevel.ind1.end() )
196 foundCycle = true; // n1 already in new level: we found a cycle
197 else
198 newLevel.ind1.push_back( n1 ); // add n1 to new level
199 }
200 if( foundCycle )
201 break;
202 }
203 if( foundCycle )
204 break;
205 }
206 // build newLevel.ind2
207 foreach( size_t n1, newLevel.ind1 ) { // for all n1 in this level
208 foreach( const Neighbor &n2, nb1(n1) ) { // for all neighbors n2 of n1
209 if( find( prevLevel.ind2.begin(), prevLevel.ind2.end(), n2 ) == prevLevel.ind2.end() ) { // n2 not in previous level
210 if( find( newLevel.ind2.begin(), newLevel.ind2.end(), n2 ) != newLevel.ind2.end() )
211 foundCycle = true; // n2 already in new level: we found a cycle
212 else
213 newLevel.ind2.push_back( n2 ); // add n2 to new level
214 }
215 if( foundCycle )
216 break;
217 }
218 if( foundCycle )
219 break;
220 }
221 }
222 levels.push_back( newLevel );
223 nr_1 += newLevel.ind1.size();
224 nr_2 += newLevel.ind2.size();
225 } while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
226 if( nr_1 == nr1() && nr_2 == nr2() && !foundCycle )
227 return true;
228 else
229 return false;
230 }
231 }
232
233
234 void BipartiteGraph::printDot( std::ostream& os ) const {
235 using namespace std;
236 os << "graph G {" << endl;
237 os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
238 for( size_t n1 = 0; n1 < nr1(); n1++ )
239 os << "\tx" << n1 << ";" << endl;
240 os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
241 for( size_t n2 = 0; n2 < nr2(); n2++ )
242 os << "\ty" << n2 << ";" << endl;
243 for( size_t n1 = 0; n1 < nr1(); n1++ )
244 foreach( const Neighbor &n2, nb1(n1) )
245 os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
246 os << "}" << endl;
247 }
248
249
250 void BipartiteGraph::check() const {
251 size_t N1 = nr1();
252 size_t N2 = nr2();
253 for( size_t n1 = 0; n1 < N1; n1++ ) {
254 size_t iter = 0;
255 foreach( const Neighbor &n2, nb1(n1) ) {
256 assert( n2.iter == iter );
257 assert( n2.node < N2 );
258 assert( n2.dual < nb2(n2).size() );
259 assert( nb2(n2, n2.dual) == n1 );
260 iter++;
261 }
262 }
263 for( size_t n2 = 0; n2 < N2; n2++ ) {
264 size_t iter = 0;
265 foreach( const Neighbor &n1, nb2(n2) ) {
266 assert( n1.iter == iter );
267 assert( n1.node < N1 );
268 assert( n1.dual < nb1(n1).size() );
269 assert( nb1(n1, n1.dual) == n2 );
270 iter++;
271 }
272 }
273 }
274
275
276 } // end of namespace dai