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