1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
4 This file is part of libDAI.
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.
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.
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
22 #include <dai/bipgraph.h>
31 /// Remove node of type 1 and all incident edges.
32 void BipartiteGraph::erase1( size_t n1
) {
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
);
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
47 nb1( m1
.node
, m1
.dual
).dual
= iter
;
58 /// Remove node of type 2 and all incident edges.
59 void BipartiteGraph::erase2( size_t n2
) {
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
);
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
74 nb2( m2
.node
, m2
.dual
).dual
= iter
;
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.
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
);
95 std::vector
<size_t>::iterator it
= std::unique( result
.begin(), result
.end() );
96 result
.erase( it
, result
.end() );
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.
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
);
111 std::vector
<size_t>::iterator it
= std::unique( result
.begin(), result
.end() );
112 result
.erase( it
, result
.end() );
117 /// Returns true if the graph is connected
118 bool BipartiteGraph::isConnected() const {
122 std::vector
<bool> incomponent1( nr1(), false );
123 std::vector
<bool> incomponent2( nr2(), false );
125 incomponent1
[0] = true;
126 bool found_new_nodes
;
128 found_new_nodes
= false;
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;
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;
153 } while( found_new_nodes
);
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;
164 return all_connected
;
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.
173 bool BipartiteGraph::isTree() const {
175 vector
<levelType
> levels
;
177 bool foundCycle
= false;
181 if( nr1() == 0 || nr2() == 0 )
186 newLevel
.ind1
.clear();
187 newLevel
.ind2
.clear();
188 if( levels
.size() == 0 ) {
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
);
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
205 newLevel
.ind1
.push_back( n1
); // add n1 to new level
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
220 newLevel
.ind2
.push_back( n2
); // add n2 to new level
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
)
241 /// Stream to output stream os in graphviz .dot syntax
242 void BipartiteGraph::display( std::ostream
& os
) const {
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
;
258 /// Checks internal consistency
259 void BipartiteGraph::check() const {
262 for( size_t n1
= 0; n1
< N1
; n1
++ ) {
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
);
272 for( size_t n2
= 0; n2
< N2
; n2
++ ) {
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
);
285 } // end of namespace dai