1e87de1f09c4f382a62d5bb817a728188074bf08
[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 /// Remove node of type 1 and all incident edges.
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 /// Remove node of type 2 and all incident edges.
59 void BipartiteGraph::erase2( size_t n2 ) {
60 assert( n2 < nr2() );
61 // Erase neighbor entry of node n2
62 _nb2.erase( _nb2.begin() + n2 );
63 // Adjust neighbor entries of nodes of type 1
64 for( size_t n1 = 0; n1 < nr1(); n1++ ) {
65 for( size_t iter = 0; iter < nb1(n1).size(); ) {
66 Neighbor &m2 = nb1(n1, iter);
67 if( m2.node == n2 ) {
68 // delete this entry, because it points to the deleted node
69 nb1(n1).erase( nb1(n1).begin() + iter );
70 } else if( m2.node > n2 ) {
71 // update this entry and the corresponding dual of the neighboring node of type 2
72 m2.iter = iter;
73 m2.node--;
74 nb2( m2.node, m2.dual ).dual = iter;
75 iter++;
76 } else {
77 // skip
78 iter++;
79 }
80 }
81 }
82 }
83
84
85 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
86 /** If include == true, include n1 itself, otherwise exclude n1.
87 */
88 std::vector<size_t> BipartiteGraph::delta1( size_t n1, bool include ) const {
89 std::vector<size_t> result;
90 foreach( const Neighbor &n2, nb1(n1) )
91 foreach( const Neighbor &m1, nb2(n2) )
92 if( include || (m1 != n1) )
93 result.push_back( m1 );
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 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
102 /** If include == true, include n2 itself, otherwise exclude n2.
103 */
104 std::vector<size_t> BipartiteGraph::delta2( size_t n2, bool include ) const {
105 std::vector<size_t> result;
106 foreach( const Neighbor &n1, nb2(n2) )
107 foreach( const Neighbor &m2, nb1(n1) )
108 if( include || (m2 != n2) )
109 result.push_back( m2 );
110 // remove duplicates
111 std::vector<size_t>::iterator it = std::unique( result.begin(), result.end() );
112 result.erase( it, result.end() );
113 return result;
114 }
115
116
117 /// Returns true if the graph is connected
118 bool BipartiteGraph::isConnected() const {
119 if( nr1() == 0 ) {
120 return true;
121 } else {
122 std::vector<bool> incomponent1( nr1(), false );
123 std::vector<bool> incomponent2( nr2(), false );
124
125 incomponent1[0] = true;
126 bool found_new_nodes;
127 do {
128 found_new_nodes = false;
129
130 // For all nodes of type 2, check if they are connected with the (growing) component
131 for( size_t n2 = 0; n2 < nr2(); n2++ )
132 if( !incomponent2[n2] ) {
133 foreach( const Neighbor &n1, nb2(n2) ) {
134 if( incomponent1[n1] ) {
135 found_new_nodes = true;
136 incomponent2[n2] = true;
137 break;
138 }
139 }
140 }
141
142 // For all nodes of type 1, check if they are connected with the (growing) component
143 for( size_t n1 = 0; n1 < nr1(); n1++ )
144 if( !incomponent1[n1] ) {
145 foreach( const Neighbor &n2, nb1(n1) ) {
146 if( incomponent2[n2] ) {
147 found_new_nodes = true;
148 incomponent1[n1] = true;
149 break;
150 }
151 }
152 }
153 } while( found_new_nodes );
154
155 // Check if there are remaining nodes (not in the component)
156 bool all_connected = true;
157 for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
158 if( !incomponent1[n1] )
159 all_connected = false;
160 for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
161 if( !incomponent2[n2] )
162 all_connected = false;
163
164 return all_connected;
165 }
166 }
167
168
169 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
170 /** This is equivalent to whether for each pair of vertices in the graph, there exists
171 * a unique path in the graph that starts at the first and ends at the second vertex.
172 */
173 bool BipartiteGraph::isTree() const {
174 using namespace std;
175 vector<levelType> levels;
176
177 bool foundCycle = false;
178 size_t nr_1 = 0;
179 size_t nr_2 = 0;
180
181 if( nr1() == 0 || nr2() == 0 )
182 return true;
183 else {
184 levelType newLevel;
185 do {
186 newLevel.ind1.clear();
187 newLevel.ind2.clear();
188 if( levels.size() == 0 ) {
189 size_t n1 = 0;
190 // add n1 to ind1
191 newLevel.ind1 = vector<size_t>( 1, n1 );
192 // add all neighbors of n1 to ind2
193 newLevel.ind2.reserve( nb1(n1).size() );
194 foreach( const Neighbor &n2, nb1(n1) )
195 newLevel.ind2.push_back( n2 );
196 } else {
197 const levelType &prevLevel = levels.back();
198 // build newLevel.ind1
199 foreach( size_t n2, prevLevel.ind2 ) { // for all n2 in the previous level
200 foreach( const Neighbor &n1, nb2(n2) ) { // for all neighbors n1 of n2
201 if( find( prevLevel.ind1.begin(), prevLevel.ind1.end(), n1 ) == prevLevel.ind1.end() ) { // n1 not in previous level
202 if( find( newLevel.ind1.begin(), newLevel.ind1.end(), n1 ) != newLevel.ind1.end() )
203 foundCycle = true; // n1 already in new level: we found a cycle
204 else
205 newLevel.ind1.push_back( n1 ); // add n1 to new level
206 }
207 if( foundCycle )
208 break;
209 }
210 if( foundCycle )
211 break;
212 }
213 // build newLevel.ind2
214 foreach( size_t n1, newLevel.ind1 ) { // for all n1 in this level
215 foreach( const Neighbor &n2, nb1(n1) ) { // for all neighbors n2 of n1
216 if( find( prevLevel.ind2.begin(), prevLevel.ind2.end(), n2 ) == prevLevel.ind2.end() ) { // n2 not in previous level
217 if( find( newLevel.ind2.begin(), newLevel.ind2.end(), n2 ) != newLevel.ind2.end() )
218 foundCycle = true; // n2 already in new level: we found a cycle
219 else
220 newLevel.ind2.push_back( n2 ); // add n2 to new level
221 }
222 if( foundCycle )
223 break;
224 }
225 if( foundCycle )
226 break;
227 }
228 }
229 levels.push_back( newLevel );
230 nr_1 += newLevel.ind1.size();
231 nr_2 += newLevel.ind2.size();
232 } while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
233 if( nr_1 == nr1() && nr_2 == nr2() && !foundCycle )
234 return true;
235 else
236 return false;
237 }
238 }
239
240
241 /// Stream to output stream os in graphviz .dot syntax
242 void BipartiteGraph::display( std::ostream& os ) const {
243 using namespace std;
244 os << "graph G {" << endl;
245 os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
246 for( size_t n1 = 0; n1 < nr1(); n1++ )
247 os << "\tx" << n1 << ";" << endl;
248 os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
249 for( size_t n2 = 0; n2 < nr2(); n2++ )
250 os << "\ty" << n2 << ";" << endl;
251 for( size_t n1 = 0; n1 < nr1(); n1++ )
252 foreach( const Neighbor &n2, nb1(n1) )
253 os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
254 os << "}" << endl;
255 }
256
257
258 /// Checks internal consistency
259 void BipartiteGraph::check() const {
260 size_t N1 = nr1();
261 size_t N2 = nr2();
262 for( size_t n1 = 0; n1 < N1; n1++ ) {
263 size_t iter = 0;
264 foreach( const Neighbor &n2, nb1(n1) ) {
265 assert( n2.iter == iter );
266 assert( n2.node < N2 );
267 assert( n2.dual < nb2(n2).size() );
268 assert( nb2(n2, n2.dual) == n1 );
269 iter++;
270 }
271 }
272 for( size_t n2 = 0; n2 < N2; n2++ ) {
273 size_t iter = 0;
274 foreach( const Neighbor &n1, nb2(n2) ) {
275 assert( n1.iter == iter );
276 assert( n1.node < N1 );
277 assert( n1.dual < nb1(n1).size() );
278 assert( nb1(n1, n1.dual) == n2 );
279 iter++;
280 }
281 }
282 }
283
284
285 } // end of namespace dai