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
5 This file is part of libDAI.
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.
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.
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 */
23 /// \file
24 /// \brief Defines BipartiteGraph class
27 #ifndef __defined_libdai_bipgraph_h
28 #define __defined_libdai_bipgraph_h
31 #include <ostream>
32 #include <vector>
33 #include <cassert>
34 #include <algorithm>
35 #include <dai/util.h>
38 namespace dai {
41 /// Represents the neighborhood structure of nodes in a bipartite graph.
42 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
43 * nodes of different type. Nodes are indexed by an unsigned integer. If there are nr1()
44 * nodes of type 1 and nr2() nodes of type 2, the nodes of type 1 are numbered
45 * 0,1,2,...,nr1()-1 and the nodes of type 2 are numbered 0,1,2,...,nr2()-1. An edge
46 * between node \a n1 of type 1 and node \a n2 of type 2 is represented by a BipartiteGraph::Edge(\a n1,\a n2).
47 *
48 * A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
49 * its neighboring nodes. In particular, it stores for each node of type 1 a vector of Neighbor structures
50 * (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
51 * of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
52 * neighboring nodes of type 1.
53 * Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
54 * Neighbor structures, describing its neighboring nodes of the other type.
55 * \idea Cache second-order neighborhoods in BipartiteGraph.
56 */
57 class BipartiteGraph {
58 public:
59 /// Describes the neighbor relationship of two nodes in a BipartiteGraph.
60 /** Sometimes we want to do an action, such as sending a
61 * message, for all edges in a graph. However, most graphs
62 * will be sparse, so we need some way of storing a set of
63 * the neighbors of a node, which is both fast and
64 * memory-efficient. We also need to be able to go between
65 * viewing node \a A as a neighbor of node \a B, and node \a
66 * B as a neighbor of node \a A. The Neighbor struct solves
67 * both of these problems. Each node has a list of neighbors,
68 * stored as a vector<Neighbor>, and extra information is
69 * included in the Neighbor struct which allows us to access
70 * a node as a neighbor of its neighbor (the \a dual member).
71 *
72 * By convention, variable identifiers naming indices into a
73 * vector of neighbors are prefixed with an underscore ("_").
74 * The neighbor list which they point into is then understood
75 * from context. For example:
76 *
77 * \code
78 * void BP::calcNewMessage( size_t i, size_t _I )
79 * \endcode
80 *
81 * Here, \a i is the "absolute" index of node i, but \a _I is
82 * understood as a "relative" index, giving node I's entry in
83 * nb1(i). The corresponding Neighbor structure can be
84 * accessed as nb1(i,_I) or nb1(i)[_I]. The absolute index of
85 * \a _I, which would be called \a I, can be recovered from
86 * the \a node member: nb1(i,_I).node. The \a iter member
87 * gives the relative index \a _I, and the \a dual member
88 * gives the "dual" relative index, i.e. the index of \a i in
89 * \a I's neighbor list.
90 *
91 * \code
92 * Neighbor n = nb1(i,_I);
93 * n.node == I &&
94 * n.iter == _I &&
95 * nb2(n.node,n.dual).node == i
96 * \endcode
97 *
98 * In a FactorGraph, nb1 is called nbV, and nb2 is called
99 * nbF.
100 *
101 * There is no easy way to transform a pair of absolute node
102 * indices \a i and \a I into a Neighbor structure relative
103 * to one of the nodes. Such a feature has never yet been
104 * found to be necessary. Iteration over edges can always be
105 * accomplished using the Neighbor lists, and by writing
106 * functions that accept relative indices:
107 * \code
108 * for( size_t i = 0; i < nrVars(); ++i )
109 * foreach( const Neighbor &I, nbV(i) )
110 * calcNewMessage( i, I.iter );
111 * \endcode
112 */
113 struct Neighbor {
114 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
115 size_t iter;
116 /// Contains the number of the neighboring node
117 size_t node;
118 /// Contains the "dual" iter
119 size_t dual;
121 /// Default constructor
122 Neighbor() {}
123 /// Constructor that sets the Neighbor members according to the parameters
124 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
126 /// Cast to size_t returns node member
127 operator size_t () const { return node; }
128 };
130 /// Describes the neighbors of some node.
131 typedef std::vector<Neighbor> Neighbors;
133 /// Represents an edge: an Edge(\a n1,\a n2) corresponds to the edge between node \a n1 of type 1 and node \a n2 of type 2.
134 typedef std::pair<size_t,size_t> Edge;
136 private:
137 /// Contains for each node of type 1 a vector of its neighbors
138 std::vector<Neighbors> _nb1;
140 /// Contains for each node of type 2 a vector of its neighbors
141 std::vector<Neighbors> _nb2;
143 /// Used internally by isTree()
144 struct levelType {
145 std::vector<size_t> ind1; // indices of nodes of type 1
146 std::vector<size_t> ind2; // indices of nodes of type 2
147 };
149 // OBSOLETE
150 /// @name Backwards compatibility layer (to be removed soon)
151 //@{
152 /// Enable backwards compatibility layer?
153 bool _edge_indexed;
154 /// Call indexEdges() first to initialize these members
155 std::vector<Edge> _edges;
156 /// Call indexEdges() first to initialize these members
157 hash_map<Edge,size_t> _vv2e;
158 //}@
160 public:
161 /// Default constructor (creates an empty bipartite graph)
162 BipartiteGraph() : _nb1(), _nb2(), _edge_indexed(false) {}
164 /// Constructs BipartiteGraph from a range of edges.
165 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
166 * \param nr1 The number of nodes of type 1.
167 * \param nr2 The number of nodes of type 2.
168 * \param begin Points to the first edge.
169 * \param end Points just beyond the last edge.
170 */
171 template<typename EdgeInputIterator>
172 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ), _edge_indexed(false) {
173 construct( nr1, nr2, begin, end );
174 }
176 /// (Re)constructs BipartiteGraph from a range of edges.
177 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
178 * \param nr1 The number of nodes of type 1.
179 * \param nr2 The number of nodes of type 2.
180 * \param begin Points to the first edge.
181 * \param end Points just beyond the last edge.
182 */
183 template<typename EdgeInputIterator>
184 void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
186 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
187 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
188 #ifdef DAI_DEBUG
189 assert( i1 < _nb1.size() );
190 assert( _i2 < _nb1[i1].size() );
191 #endif
192 return _nb1[i1][_i2];
193 }
194 /// Returns reference to the _i2'th neighbor of node i1 of type 1
195 Neighbor & nb1( size_t i1, size_t _i2 ) {
196 #ifdef DAI_DEBUG
197 assert( i1 < _nb1.size() );
198 assert( _i2 < _nb1[i1].size() );
199 #endif
200 return _nb1[i1][_i2];
201 }
203 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
204 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
205 #ifdef DAI_DEBUG
206 assert( i2 < _nb2.size() );
207 assert( _i1 < _nb2[i2].size() );
208 #endif
209 return _nb2[i2][_i1];
210 }
211 /// Returns reference to the _i1'th neighbor of node i2 of type 2
212 Neighbor & nb2( size_t i2, size_t _i1 ) {
213 #ifdef DAI_DEBUG
214 assert( i2 < _nb2.size() );
215 assert( _i1 < _nb2[i2].size() );
216 #endif
217 return _nb2[i2][_i1];
218 }
220 /// Returns constant reference to all neighbors of node i1 of type 1
221 const Neighbors & nb1( size_t i1 ) const {
222 #ifdef DAI_DEBUG
223 assert( i1 < _nb1.size() );
224 #endif
225 return _nb1[i1];
226 }
227 /// Returns reference to all neighbors of node of i1 type 1
228 Neighbors & nb1( size_t i1 ) {
229 #ifdef DAI_DEBUG
230 assert( i1 < _nb1.size() );
231 #endif
232 return _nb1[i1];
233 }
235 /// Returns constant reference to all neighbors of node i2 of type 2
236 const Neighbors & nb2( size_t i2 ) const {
237 #ifdef DAI_DEBUG
238 assert( i2 < _nb2.size() );
239 #endif
240 return _nb2[i2];
241 }
242 /// Returns reference to all neighbors of node i2 of type 2
243 Neighbors & nb2( size_t i2 ) {
244 #ifdef DAI_DEBUG
245 assert( i2 < _nb2.size() );
246 #endif
247 return _nb2[i2];
248 }
250 /// Returns number of nodes of type 1
251 size_t nr1() const { return _nb1.size(); }
252 /// Returns number of nodes of type 2
253 size_t nr2() const { return _nb2.size(); }
255 /// Calculates the number of edges, time complexity: O(nr1())
256 size_t nrEdges() const {
257 size_t sum = 0;
258 for( size_t i1 = 0; i1 < nr1(); i1++ )
259 sum += nb1(i1).size();
260 return sum;
261 }
263 /// Adds a node of type 1 without neighbors.
264 void add1() { _nb1.push_back( Neighbors() ); }
266 /// Adds a node of type 2 without neighbors.
267 void add2() { _nb2.push_back( Neighbors() ); }
269 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
270 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
271 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
272 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
273 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
274 */
275 template <typename NodeInputIterator>
276 void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
277 Neighbors nbs1new;
278 nbs1new.reserve( sizeHint );
279 size_t iter = 0;
280 for( NodeInputIterator it = begin; it != end; ++it ) {
281 assert( *it < nr2() );
282 Neighbor nb1new( iter, *it, nb2(*it).size() );
283 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
284 nbs1new.push_back( nb1new );
285 nb2( *it ).push_back( nb2new );
286 }
287 _nb1.push_back( nbs1new );
288 }
290 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
291 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
292 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
293 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
294 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
295 */
296 template <typename NodeInputIterator>
297 void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
298 Neighbors nbs2new;
299 nbs2new.reserve( sizeHint );
300 size_t iter = 0;
301 for( NodeInputIterator it = begin; it != end; ++it ) {
302 assert( *it < nr1() );
303 Neighbor nb2new( iter, *it, nb1(*it).size() );
304 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
305 nbs2new.push_back( nb2new );
306 nb1( *it ).push_back( nb1new );
307 }
308 _nb2.push_back( nbs2new );
309 }
311 /// Removes node n1 of type 1 and all incident edges.
312 void erase1( size_t n1 );
314 /// Removes node n2 of type 2 and all incident edges.
315 void erase2( size_t n2 );
317 /// Removes edge between node n1 of type 1 and node n2 of type 2.
318 void eraseEdge( size_t n1, size_t n2 ) {
319 assert( n1 < nr1() );
320 assert( n2 < nr2() );
321 for( Neighbors::iterator i1 = _nb1[n1].begin(); i1 != _nb1[n1].end(); i1++ )
322 if( i1->node == n2 ) {
323 _nb1[n1].erase( i1 );
324 break;
325 }
326 for( Neighbors::iterator i2 = _nb2[n2].begin(); i2 != _nb2[n2].end(); i2++ )
327 if( i2->node == n1 ) {
328 _nb2[n2].erase( i2 );
329 break;
330 }
331 }
333 /// Adds an edge between node n1 of type 1 and node n2 of type 2.
334 /** If check == true, only adds the edge if it does not exist already.
335 */
336 void addEdge( size_t n1, size_t n2, bool check = true ) {
337 assert( n1 < nr1() );
338 assert( n2 < nr2() );
339 bool exists = false;
340 if( check ) {
341 // Check whether the edge already exists
342 foreach( const Neighbor &nb2, nb1(n1) )
343 if( nb2 == n2 ) {
344 exists = true;
345 break;
346 }
347 }
348 if( !exists ) { // Add edge
349 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
350 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
351 _nb1[n1].push_back( nb_1 );
352 _nb2[n2].push_back( nb_2 );
353 }
354 }
356 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
357 /** If include == true, includes n1 itself, otherwise excludes n1.
358 */
359 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
361 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
362 /** If include == true, includes n2 itself, otherwise excludes n2.
363 */
364 std::vector<size_t> delta2( size_t n2, bool include = false ) const;
366 /// Returns true if the graph is connected
367 /** \todo Should be optimized by invoking boost::graph library
368 */
369 bool isConnected() const;
371 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
372 bool isTree() const;
374 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
375 void printDot( std::ostream& os ) const;
377 // OBSOLETE
378 /// @name Backwards compatibility layer (to be removed soon)
379 //@{
380 void indexEdges() {
381 std::cerr << "Warning: this BipartiteGraph edge interface is obsolete!" << std::endl;
382 _edges.clear();
383 _vv2e.clear();
384 size_t i=0;
385 foreach(const Neighbors &nb1s, _nb1) {
386 foreach(const Neighbor &n2, nb1s) {
387 Edge e(i, n2.node);
388 _edges.push_back(e);
389 }
390 i++;
391 }
392 sort(_edges.begin(), _edges.end()); // unnecessary?
394 i=0;
395 foreach(const Edge& e, _edges) {
396 _vv2e[e] = i++;
397 }
399 _edge_indexed = true;
400 }
402 const Edge& edge(size_t e) const {
403 assert(_edge_indexed);
404 return _edges[e];
405 }
407 const std::vector<Edge>& edges() const {
408 return _edges;
409 }
411 size_t VV2E(size_t n1, size_t n2) const {
412 assert(_edge_indexed);
413 Edge e(n1,n2);
414 hash_map<Edge,size_t>::const_iterator i = _vv2e.find(e);
415 assert(i != _vv2e.end());
416 return i->second;
417 }
419 size_t nr_edges() const {
420 assert(_edge_indexed);
421 return _edges.size();
422 }
423 //}@
425 private:
426 /// Checks internal consistency
427 void check() const;
428 };
431 template<typename EdgeInputIterator>
432 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
433 _nb1.clear();
434 _nb1.resize( nr1 );
435 _nb2.clear();
436 _nb2.resize( nr2 );
438 for( EdgeInputIterator e = begin; e != end; e++ ) {
439 #ifdef DAI_DEBUG
440 addEdge( e->first, e->second, true );
441 #else
442 addEdge( e->first, e->second, false );
443 #endif
444 }
445 }
448 } // end of namespace dai
451 /** \example example_bipgraph.cpp
452 * This example deals with the following bipartite graph:
453 * \dot
454 * graph example {
455 * ordering=out;
456 * subgraph cluster_type1 {
457 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
458 * 12 [label="2"];
459 * 11 [label="1"];
460 * 10 [label="0"];
461 * }
462 * subgraph cluster_type2 {
463 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
464 * 21 [label="1"];
465 * 20 [label="0"];
466 * }
467 * 10 -- 20;
468 * 11 -- 20;
469 * 12 -- 20;
470 * 11 -- 21;
471 * 12 -- 21;
472 * }
473 * \enddot
474 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
475 * Node 0 of type 1 has only one neighbor (node 0 of type 2), but node 0 of type 2 has three neighbors (nodes 0,1,2 of type 1).
476 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
477 * how to iterate over nodes and their neighbors.
478 *
479 * \section Output
480 * \verbinclude examples/example_bipgraph.out
481 *
482 * \section Source
483 */
486 #endif