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