Improved BipartiteGraph doxygen documentation.
[libdai.git] / include / dai / bipgraph.h
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 #ifndef __defined_libdai_bipgraph_h
23 #define __defined_libdai_bipgraph_h
24
25
26 #include <ostream>
27 #include <vector>
28 #include <cassert>
29 #include <dai/util.h>
30
31
32 namespace dai {
33
34
35 /// A BipartiteGraph represents the neighborhood structure of nodes in a bipartite graph.
36 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
37 * nodes of different type. Nodes are indexed by an unsigned integer, edges are indexed as
38 * a pair of unsigned integers (where the pair (a,b) means the b'th neighbor of the a'th node).
39 * The BipartiteGraph stores neighborhood structures as vectors of vectors of Neighbor entries.
40 */
41 class BipartiteGraph {
42 public:
43 /// A Neighbor describes a neighboring node of some other node.
44 /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
45 * \code
46 * foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
47 * size_t _n2 = n2.iter;
48 * size_t _n1 = n2.dual;
49 * // n2 == n2.node;
50 * // The _n2'th neighbor of n1 is n2, and the _n1'th neighbor of n2 is n1:
51 * // nb1(n1)[_n2] == n2, nb2(n2)[_n1] == n1
52 * }
53 * \endcode
54 */
55 struct Neighbor {
56 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
57 unsigned iter;
58 /// Contains the number of the neighboring node
59 unsigned node;
60 /// Contains the "dual" iter
61 unsigned dual;
62 /// Cast to unsigned returns node
63 operator unsigned () const { return node; }
64 /// Default constructor
65 Neighbor() {}
66 /// Constructor
67 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
68 };
69
70 /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
71 typedef std::vector<Neighbor> Neighbors;
72
73 /// Edge is used as index of an edge: an Edge(a,b) corresponds to the edge between the a'th node and its b'th neighbor.
74 typedef std::pair<size_t,size_t> Edge;
75
76 private:
77 /// _nb1 contains for each node of type 1 a vector of its neighbors
78 std::vector<Neighbors> _nb1;
79 /// _nb2 contains for each node of type 2 a vector of its neighbors
80 std::vector<Neighbors> _nb2;
81
82 /// Used internally by isTree()
83 struct levelType {
84 std::vector<size_t> ind1; // indices of vertices of type 1
85 std::vector<size_t> ind2; // indices of vertices of type 2
86 };
87
88 public:
89 /// Default constructor
90 BipartiteGraph() : _nb1(), _nb2() {}
91
92 /// Copy constructor
93 BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
94
95 /// Assignment operator
96 BipartiteGraph & operator=( const BipartiteGraph & x ) {
97 if( this != &x ) {
98 _nb1 = x._nb1;
99 _nb2 = x._nb2;
100 }
101 return *this;
102 }
103
104 /// Create bipartite graph from a range of edges.
105 /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
106 * The value_type of an EdgeInputIterator should be Edge.
107 */
108 template<typename EdgeInputIterator>
109 void create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
110
111 /// Construct bipartite graph from a range of edges.
112 /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
113 * The value_type of an EdgeInputIterator should be Edge.
114 */
115 template<typename EdgeInputIterator>
116 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
117 create( nr1, nr2, begin, end );
118 }
119
120 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
121 const Neighbor & nb1( size_t i1, size_t _i2 ) const { return _nb1[i1][_i2]; }
122 /// Returns reference to the _i2'th neighbor of node i1 of type 1
123 Neighbor & nb1( size_t i1, size_t _i2 ) { return _nb1[i1][_i2]; }
124
125 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
126 const Neighbor & nb2( size_t i2, size_t _i1 ) const { return _nb2[i2][_i1]; }
127 /// Returns reference to the _i1'th neighbor of node i2 of type 2
128 Neighbor & nb2( size_t i2, size_t _i1 ) { return _nb2[i2][_i1]; }
129
130 /// Returns constant reference to all neighbors of node i1 of type 1
131 const Neighbors & nb1( size_t i1 ) const { return _nb1[i1]; }
132 /// Returns reference to all neighbors of node of i1 type 1
133 Neighbors & nb1( size_t i1 ) { return _nb1[i1]; }
134
135 /// Returns constant reference to all neighbors of node i2 of type 2
136 const Neighbors & nb2( size_t i2 ) const { return _nb2[i2]; }
137 /// Returns reference to all neighbors of node i2 of type 2
138 Neighbors & nb2( size_t i2 ) { return _nb2[i2]; }
139
140 /// Returns number of nodes of type 1
141 size_t nr1() const { return _nb1.size(); }
142 /// Returns number of nodes of type 2
143 size_t nr2() const { return _nb2.size(); }
144
145 /// Calculates the number of edges
146 size_t nrEdges() const {
147 size_t sum = 0;
148 for( size_t i1 = 0; i1 < nr1(); i1++ )
149 sum += nb1(i1).size();
150 return sum;
151 }
152
153 /// Add node of type 1 without neighbors.
154 void add1() {
155 _nb1.push_back( Neighbors() );
156 }
157
158 /// Add node of type 2 without neighbors.
159 void add2() {
160 _nb2.push_back( Neighbors() );
161 }
162
163 /// Add node of type 1 with neighbors specified by a range.
164 /** The value_type of an NodeInputIterator should be a size_t, corresponding to
165 * the indices of nodes of type 2 that should become neighbors of the added node.
166 * For improved efficiency, the size of the range may be specified by sizeHint.
167 */
168 template <typename NodeInputIterator>
169 void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
170 Neighbors nbs1new;
171 nbs1new.reserve( sizeHint );
172 size_t iter = 0;
173 for( NodeInputIterator it = begin; it != end; ++it ) {
174 assert( *it < nr2() );
175 Neighbor nb1new( iter, *it, nb2(*it).size() );
176 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
177 nbs1new.push_back( nb1new );
178 nb2( *it ).push_back( nb2new );
179 }
180 _nb1.push_back( nbs1new );
181 }
182
183 /// Add node of type 2 with neighbors specified by a range.
184 /** The value_type of an NodeInputIterator should be a size_t, corresponding to
185 * the indices of nodes of type 1 that should become neighbors of the added node.
186 * For improved efficiency, the size of the range may be specified by sizeHint.
187 */
188 template <typename NodeInputIterator>
189 void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
190 Neighbors nbs2new;
191 nbs2new.reserve( sizeHint );
192 size_t iter = 0;
193 for( NodeInputIterator it = begin; it != end; ++it ) {
194 assert( *it < nr1() );
195 Neighbor nb2new( iter, *it, nb1(*it).size() );
196 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
197 nbs2new.push_back( nb2new );
198 nb1( *it ).push_back( nb1new );
199 }
200 _nb2.push_back( nbs2new );
201 }
202
203 /// Remove node of type 1 and all incident edges.
204 void erase1( size_t n1 ) {
205 assert( n1 < nr1() );
206 // Erase neighbor entry of node n1
207 _nb1.erase( _nb1.begin() + n1 );
208 // Adjust neighbor entries of nodes of type 2
209 for( size_t n2 = 0; n2 < nr2(); n2++ )
210 for( size_t iter = 0; iter < nb2(n2).size(); ) {
211 if( nb2(n2, iter).node == n1 ) {
212 // delete this entry, because it points to the deleted node
213 nb2(n2).erase( nb2(n2).begin() + iter );
214 // adjust all subsequent entries:
215 // update their iter and the corresponding dual of the neighboring node of type 1
216 for( size_t newiter = iter; newiter < nb2(n2).size(); newiter++ ) {
217 nb2( n2, newiter ).iter = newiter;
218 nb1( nb2(n2, newiter).node, nb2(n2, newiter).dual ).dual = newiter;
219 }
220 } else if( nb2(n2, iter).node > n1 ) {
221 nb2(n2, iter).node--;
222 iter++;
223 } else
224 iter++;
225 }
226 }
227
228 /// Remove node of type 2 and all incident edges.
229 void erase2( size_t n2 ) {
230 assert( n2 < nr2() );
231 // Erase neighbor entry of node n2
232 _nb2.erase( _nb2.begin() + n2 );
233 // Adjust neighbor entries of nodes of type 1
234 for( size_t n1 = 0; n1 < nr1(); n1++ )
235 for( size_t iter = 0; iter < nb1(n1).size(); ) {
236 if( nb1(n1, iter).node == n2 ) {
237 // delete this entry, because it points to the deleted node
238 nb1(n1).erase( nb1(n1).begin() + iter );
239 // adjust all subsequent entries:
240 // update their iter and the corresponding dual of the neighboring node of type 2
241 for( size_t newiter = iter; newiter < nb1(n1).size(); newiter++ ) {
242 nb1( n1, newiter ).iter = newiter;
243 nb2( nb1(n1, newiter).node, nb1(n1, newiter).dual ).dual = newiter;
244 }
245 } else if( nb1(n1, iter).node > n2 ) {
246 nb1(n1, iter).node--;
247 iter++;
248 } else
249 iter++;
250 }
251 }
252
253 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
254 /** If include == true, include n1 itself, otherwise exclude n1.
255 */
256 std::vector<size_t> delta1( size_t n1, bool include = false ) const {
257 std::vector<size_t> result;
258 foreach( const Neighbor &n2, nb1(n1) )
259 foreach( const Neighbor &m1, nb2(n2) )
260 if( include || (m1 != n1) )
261 result.push_back( m1 );
262 // remove duplicates
263 std::vector<size_t>::iterator it = unique( result.begin(), result.end() );
264 result.erase( it, result.end() );
265 return result;
266 }
267
268 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
269 /** If include == true, include n2 itself, otherwise exclude n2.
270 */
271 std::vector<size_t> delta2( size_t n2, bool include = false ) const {
272 std::vector<size_t> result;
273 foreach( const Neighbor &n1, nb2(n2) )
274 foreach( const Neighbor &m2, nb1(n1) )
275 if( include || (m2 != n2) )
276 result.push_back( m2 );
277 // remove duplicates
278 std::vector<size_t>::iterator it = unique( result.begin(), result.end() );
279 result.erase( it, result.end() );
280 return result;
281 }
282
283 /// Returns true if the graph is connected
284 bool isConnected() const {
285 if( nr1() == 0 ) {
286 return true;
287 } else {
288 std::vector<bool> incomponent1( nr1(), false );
289 std::vector<bool> incomponent2( nr2(), false );
290
291 incomponent1[0] = true;
292 bool found_new_nodes;
293 do {
294 found_new_nodes = false;
295
296 // For all nodes of type 2, check if they are connected with the (growing) component
297 for( size_t n2 = 0; n2 < nr2(); n2++ )
298 if( !incomponent2[n2] ) {
299 foreach( const Neighbor &n1, nb2(n2) ) {
300 if( incomponent1[n1] ) {
301 found_new_nodes = true;
302 incomponent2[n2] = true;
303 break;
304 }
305 }
306 }
307
308 // For all nodes of type 1, check if they are connected with the (growing) component
309 for( size_t n1 = 0; n1 < nr1(); n1++ )
310 if( !incomponent1[n1] ) {
311 foreach( const Neighbor &n2, nb1(n1) ) {
312 if( incomponent2[n2] ) {
313 found_new_nodes = true;
314 incomponent1[n1] = true;
315 break;
316 }
317 }
318 }
319 } while( found_new_nodes );
320
321 // Check if there are remaining nodes (not in the component)
322 bool all_connected = true;
323 for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
324 if( !incomponent1[n1] )
325 all_connected = false;
326 for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
327 if( !incomponent2[n2] )
328 all_connected = false;
329
330 return all_connected;
331 }
332 }
333
334 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
335 /** This is equivalent to whether for each pair of vertices in the graph, there exists
336 * a unique path in the graph that starts at the first and ends at the second vertex.
337 */
338 bool isTree() const {
339 using namespace std;
340 vector<levelType> levels;
341
342 bool foundCycle = false;
343 size_t nr_1 = 0;
344 size_t nr_2 = 0;
345
346 if( nr1() == 0 || nr2() == 0 )
347 return true;
348 else {
349 levelType newLevel;
350 do {
351 newLevel.ind1.clear();
352 newLevel.ind2.clear();
353 if( levels.size() == 0 ) {
354 size_t n1 = 0;
355 // add n1 to ind1
356 newLevel.ind1 = vector<size_t>( 1, n1 );
357 // add all neighbors of n1 to ind2
358 newLevel.ind2.reserve( nb1(n1).size() );
359 foreach( const Neighbor &n2, nb1(n1) )
360 newLevel.ind2.push_back( n2 );
361 } else {
362 const levelType &prevLevel = levels.back();
363 // build newLevel.ind1
364 foreach( size_t n2, prevLevel.ind2 ) { // for all n2 in the previous level
365 foreach( const Neighbor &n1, nb2(n2) ) { // for all neighbors n1 of n2
366 if( find( prevLevel.ind1.begin(), prevLevel.ind1.end(), n1 ) == prevLevel.ind1.end() ) { // n1 not in previous level
367 if( find( newLevel.ind1.begin(), newLevel.ind1.end(), n1 ) != newLevel.ind1.end() )
368 foundCycle = true; // n1 already in new level: we found a cycle
369 else
370 newLevel.ind1.push_back( n1 ); // add n1 to new level
371 }
372 if( foundCycle )
373 break;
374 }
375 if( foundCycle )
376 break;
377 }
378 // build newLevel.ind2
379 foreach( size_t n1, newLevel.ind1 ) { // for all n1 in this level
380 foreach( const Neighbor &n2, nb1(n1) ) { // for all neighbors n2 of n1
381 if( find( prevLevel.ind2.begin(), prevLevel.ind2.end(), n2 ) == prevLevel.ind2.end() ) { // n2 not in previous level
382 if( find( newLevel.ind2.begin(), newLevel.ind2.end(), n2 ) != newLevel.ind2.end() )
383 foundCycle = true; // n2 already in new level: we found a cycle
384 else
385 newLevel.ind2.push_back( n2 ); // add n2 to new level
386 }
387 if( foundCycle )
388 break;
389 }
390 if( foundCycle )
391 break;
392 }
393 }
394 levels.push_back( newLevel );
395 nr_1 += newLevel.ind1.size();
396 nr_2 += newLevel.ind2.size();
397 } while( ((newLevel.ind1.size() != 0) || (newLevel.ind2.size() != 0)) && !foundCycle );
398 if( nr_1 == nr1() && nr_2 == nr2() && !foundCycle )
399 return true;
400 else
401 return false;
402 }
403 }
404
405 /// Stream to output stream os in graphviz .dot syntax
406 void display( std::ostream& os ) const {
407 using namespace std;
408 os << "graph G {" << endl;
409 os << "node[shape=circle,width=0.4,fixedsize=true];" << endl;
410 for( size_t n1 = 0; n1 < nr1(); n1++ )
411 os << "\tx" << n1 << ";" << endl;
412 os << "node[shape=box,width=0.3,height=0.3,fixedsize=true];" << endl;
413 for( size_t n2 = 0; n2 < nr2(); n2++ )
414 os << "\ty" << n2 << ";" << endl;
415 for( size_t n1 = 0; n1 < nr1(); n1++ )
416 foreach( const Neighbor &n2, nb1(n1) )
417 os << "\tx" << n1 << " -- y" << n2 << ";" << endl;
418 os << "}" << endl;
419 }
420 };
421
422
423 template<typename EdgeInputIterator>
424 void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
425 _nb1.clear();
426 _nb1.resize( nr1 );
427 _nb2.clear();
428 _nb2.resize( nr2 );
429
430 for( EdgeInputIterator e = begin; e != end; e++ ) {
431 // Each edge yields a neighbor pair
432 Neighbor nb_1( _nb1[e->first].size(), e->second, _nb2[e->second].size() );
433 Neighbor nb_2( nb_1.dual, e->first, nb_1.iter );
434 _nb1[e->first].push_back( nb_1 );
435 _nb2[e->second].push_back( nb_2 );
436 }
437 }
438
439
440 } // end of namespace dai
441
442
443 #endif