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-2010 Joris Mooij [joris dot mooij at libdai dot org]
9 */
12 /// \file
13 /// \brief Defines the BipartiteGraph class, which represents a bipartite graph
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/smallset.h>
25 #include <dai/exceptions.h>
28 namespace dai {
31 /// Represents the neighborhood structure of nodes in an undirected, bipartite graph.
32 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
33 * nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1()
34 * nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered
35 * 0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-1. An edge
36 * between node \a n1 of type 1 and node \a n2 of type 2 is represented by a BipartiteGraph::Edge(\a n1,\a n2).
37 *
38 * A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
39 * its neighboring nodes. More precisely: it stores for each node of type 1 a vector of Neighbor structures
40 * (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
41 * of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
42 * neighboring nodes of type 1.
43 * Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
44 * Neighbor structures, describing its neighboring nodes of the other type.
45 * \idea Cache second-order neighborhoods in BipartiteGraph.
46 */
47 class BipartiteGraph {
48 public:
49 /// Describes the neighbor relationship of two nodes in a BipartiteGraph.
50 /** Sometimes we want to do an action, such as sending a
51 * message, for all edges in a graph. However, most graphs
52 * will be sparse, so we need some way of storing a set of
53 * the neighbors of a node, which is both fast and
54 * memory-efficient. We also need to be able to go between
55 * viewing node \a a as a neighbor of node \a b, and node \a b
56 * as a neighbor of node \a a. The Neighbor struct solves
57 * both of these problems. Each node has a list of neighbors,
59 * extra information is included in the Neighbor struct which
60 * allows us to access a node as a neighbor of its neighbor
61 * (the \c dual member).
62 *
63 * By convention, variable identifiers naming indices into a
64 * vector of neighbors are prefixed with an underscore ("_").
65 * The neighbor list which they point into is then understood
66 * from context. For example:
67 *
68 * \code
69 * void BP::calcNewMessage( size_t i, size_t _I )
70 * \endcode
71 *
72 * Here, \a i is the "absolute" index of node i, but \a _I is
73 * understood as a "relative" index, giving node \a I 's entry in
74 * <tt>nb1(i)</tt>. The corresponding Neighbor structure can be
75 * accessed as <tt>nb1(i,_I)</tt> or <tt>nb1(i)[_I]</tt>. The
76 * absolute index of \a _I, which would be called \a I, can be
77 * recovered from the \c node member: <tt>nb1(i,_I).node</tt>.
78 * The \c iter member gives the relative index \a _I, and the
79 * \c dual member gives the "dual" relative index, i.e., the
80 * index of \a i in \a I 's neighbor list.
81 *
82 * \code
83 * Neighbor n = nb1(i,_I);
84 * n.node == I &&
85 * n.iter == _I &&
86 * nb2(n.node,n.dual).node == i
87 * \endcode
88 *
89 * In a FactorGraph, the nodes of type 1 represent variables, and
90 * the nodes of type 2 represent factors. For convenience, nb1() is
91 * called FactorGraph::nbV(), and nb2() is called FactorGraph::nbF().
92 *
93 * There is no easy way to transform a pair of absolute node
94 * indices \a i and \a I into a Neighbor structure relative
95 * to one of the nodes. Such a feature has never yet been
96 * found to be necessary. Iteration over edges can always be
97 * accomplished using the Neighbor lists, and by writing
98 * functions that accept relative indices:
99 * \code
100 * for( size_t i = 0; i < nrVars(); ++i )
101 * foreach( const Neighbor &I, nbV(i) )
102 * calcNewMessage( i, I.iter );
103 * \endcode
104 */
105 struct Neighbor {
106 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
107 size_t iter;
108 /// Contains the number of the neighboring node
109 size_t node;
110 /// Contains the "dual" iter
111 size_t dual;
113 /// Default constructor
114 Neighbor() {}
115 /// Constructor that sets the Neighbor members according to the parameters
116 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
118 /// Cast to \c size_t returns \c node member
119 operator size_t () const { return node; }
120 };
122 /// Describes the neighbors of some node.
123 typedef std::vector<Neighbor> Neighbors;
125 /// 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.
126 typedef std::pair<size_t,size_t> Edge;
128 private:
129 /// Contains for each node of type 1 a vector of its neighbors
130 std::vector<Neighbors> _nb1;
132 /// Contains for each node of type 2 a vector of its neighbors
133 std::vector<Neighbors> _nb2;
135 /// Used internally by isTree()
136 struct levelType {
137 /// Indices of nodes of type 1
138 std::vector<size_t> ind1;
139 /// Indices of nodes of type 2
140 std::vector<size_t> ind2;
141 };
143 public:
144 /// \name Constructors and destructors
145 //@{
146 /// Default constructor (creates an empty bipartite graph)
147 BipartiteGraph() : _nb1(), _nb2() {}
149 /// Constructs BipartiteGraph with \a nr1 nodes of type 1, \a nr2 nodes of type 2 and no edges.
150 BipartiteGraph( size_t nr1, size_t nr2 ) : _nb1(nr1), _nb2(nr2) {}
152 /// Constructs BipartiteGraph from a range of edges.
153 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
154 * \param nrNodes1 The number of nodes of type 1.
155 * \param nrNodes2 The number of nodes of type 2.
156 * \param begin Points to the first edge.
157 * \param end Points just beyond the last edge.
158 * \param check Whether to only add an edge if it does not exist already.
159 */
160 template<typename EdgeInputIterator>
161 BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb1(), _nb2() {
162 construct( nrNodes1, nrNodes2, begin, end, check );
163 }
164 //@}
166 /// \name Accessors and mutators
167 //@{
168 /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
169 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
170 DAI_DEBASSERT( i1 < _nb1.size() );
171 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
172 return _nb1[i1][_i2];
173 }
174 /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
175 Neighbor & nb1( size_t i1, size_t _i2 ) {
176 DAI_DEBASSERT( i1 < _nb1.size() );
177 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
178 return _nb1[i1][_i2];
179 }
181 /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
182 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
183 DAI_DEBASSERT( i2 < _nb2.size() );
184 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
185 return _nb2[i2][_i1];
186 }
187 /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
188 Neighbor & nb2( size_t i2, size_t _i1 ) {
189 DAI_DEBASSERT( i2 < _nb2.size() );
190 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
191 return _nb2[i2][_i1];
192 }
194 /// Returns constant reference to all neighbors of node \a i1 of type 1
195 const Neighbors & nb1( size_t i1 ) const {
196 DAI_DEBASSERT( i1 < _nb1.size() );
197 return _nb1[i1];
198 }
199 /// Returns reference to all neighbors of node \a i1 of type 1
200 Neighbors & nb1( size_t i1 ) {
201 DAI_DEBASSERT( i1 < _nb1.size() );
202 return _nb1[i1];
203 }
205 /// Returns constant reference to all neighbors of node \a i2 of type 2
206 const Neighbors & nb2( size_t i2 ) const {
207 DAI_DEBASSERT( i2 < _nb2.size() );
208 return _nb2[i2];
209 }
210 /// Returns reference to all neighbors of node \a i2 of type 2
211 Neighbors & nb2( size_t i2 ) {
212 DAI_DEBASSERT( i2 < _nb2.size() );
213 return _nb2[i2];
214 }
215 //@}
217 /// \name Adding nodes and edges
218 //@{
219 /// (Re)constructs BipartiteGraph from a range of edges.
220 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
221 * \param nrNodes1 The number of nodes of type 1.
222 * \param nrNodes2 The number of nodes of type 2.
223 * \param begin Points to the first edge.
224 * \param end Points just beyond the last edge.
225 * \param check Whether to only add an edge if it does not exist already.
226 */
227 template<typename EdgeInputIterator>
228 void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
230 /// Adds a node of type 1 without neighbors and returns the index of the added node.
231 size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
233 /// Adds a node of type 2 without neighbors and returns the index of the added node.
234 size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
237 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
238 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
239 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
240 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
241 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
242 * \returns Index of the added node.
243 */
244 template <typename NodeInputIterator>
245 size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
246 Neighbors nbs1new;
247 nbs1new.reserve( sizeHint );
248 size_t iter = 0;
249 for( NodeInputIterator it = begin; it != end; ++it ) {
250 DAI_ASSERT( *it < nrNodes2() );
251 Neighbor nb1new( iter, *it, nb2(*it).size() );
252 Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
253 nbs1new.push_back( nb1new );
254 nb2( *it ).push_back( nb2new );
255 }
256 _nb1.push_back( nbs1new );
257 return _nb1.size() - 1;
258 }
260 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
261 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
262 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
263 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
264 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
265 * \returns Index of the added node.
266 */
267 template <typename NodeInputIterator>
268 size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
269 Neighbors nbs2new;
270 nbs2new.reserve( sizeHint );
271 size_t iter = 0;
272 for( NodeInputIterator it = begin; it != end; ++it ) {
273 DAI_ASSERT( *it < nrNodes1() );
274 Neighbor nb2new( iter, *it, nb1(*it).size() );
275 Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
276 nbs2new.push_back( nb2new );
277 nb1( *it ).push_back( nb1new );
278 }
279 _nb2.push_back( nbs2new );
280 return _nb2.size() - 1;
281 }
283 /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
284 /** If \a check == \c true, only adds the edge if it does not exist already.
285 */
286 void addEdge( size_t n1, size_t n2, bool check = true );
287 //@}
289 /// \name Erasing nodes and edges
290 //@{
291 /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
292 void eraseNode1( size_t n1 );
294 /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
295 void eraseNode2( size_t n2 );
297 /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
298 void eraseEdge( size_t n1, size_t n2 );
299 //@}
301 /// \name Queries
302 //@{
303 /// Returns number of nodes of type 1
304 size_t nrNodes1() const { return _nb1.size(); }
305 /// Returns number of nodes of type 2
306 size_t nrNodes2() const { return _nb2.size(); }
308 /// Calculates the number of edges, time complexity: O(nrNodes1())
309 size_t nrEdges() const {
310 size_t sum = 0;
311 for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
312 sum += nb1(i1).size();
313 return sum;
314 }
316 /// Returns true if the graph contains an edge between node \a n1 of type 1 and node \a n2 of type 2.
317 /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
318 */
319 bool hasEdge( size_t n1, size_t n2 ) const {
320 if( nb1(n1).size() < nb2(n2).size() ) {
321 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
322 if( nb1( n1, _n2 ) == n2 )
323 return true;
324 } else {
325 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
326 if( nb2( n2, _n1 ) == n1 )
327 return true;
328 }
329 return false;
330 }
332 /// Returns the index of a given node \a n2 of type 2 amongst the neighbors of node \a n1 of type 1
333 /** \note The time complexity is linear in the number of neighbors of \a n1
334 * \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1
335 */
336 size_t findNb1( size_t n1, size_t n2 ) {
337 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
338 if( nb1( n1, _n2 ) == n2 )
339 return _n2;
340 DAI_THROW(OBJECT_NOT_FOUND);
341 return nb1(n1).size();
342 }
344 /// Returns the index of a given node \a n1 of type 1 amongst the neighbors of node \a n2 of type 2
345 /** \note The time complexity is linear in the number of neighbors of \a n2
346 * \throw OBJECT_NOT_FOUND if \a n1 is not a neighbor of \a n2
347 */
348 size_t findNb2( size_t n1, size_t n2 ) {
349 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
350 if( nb2( n2, _n1 ) == n1 )
351 return _n1;
352 DAI_THROW(OBJECT_NOT_FOUND);
353 return nb2(n2).size();
354 }
356 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
357 /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
358 * \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
359 */
360 SmallSet<size_t> delta1( size_t n1, bool include = false ) const;
362 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
363 /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
364 * \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
365 */
366 SmallSet<size_t> delta2( size_t n2, bool include = false ) const;
368 /// Returns true if the graph is connected
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 /// Comparison operator which returns true if two graphs are identical
375 /** \note Two graphs are called identical if they have the same number of nodes
376 * of both types and the same edges (i.e., \a x has an edge between nodes
377 * n1 and n2 if and only if \c *this has an edge between nodes n1 and n2).
378 */
379 bool operator==( const BipartiteGraph& x ) const {
380 if( nrNodes1() != x.nrNodes1() )
381 return false;
382 if( nrNodes2() != x.nrNodes2() )
383 return false;
384 for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
385 if( nb1(n1).size() != x.nb1(n1).size() )
386 return false;
387 foreach( const Neighbor &n2, nb1(n1) )
388 if( !x.hasEdge( n1, n2 ) )
389 return false;
390 foreach( const Neighbor &n2, x.nb1(n1) )
391 if( !hasEdge( n1, n2 ) )
392 return false;
393 }
394 return true;
395 }
397 /// Asserts internal consistency
398 void checkConsistency() const;
399 //@}
401 /// \name Input and output
402 //@{
403 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
404 void printDot( std::ostream& os ) const;
406 /// Writes this BipartiteGraph to an output stream
407 friend std::ostream& operator<<( std::ostream& os, const BipartiteGraph& g ) {
408 g.printDot( os );
409 return os;
410 }
411 //@}
412 };
415 template<typename EdgeInputIterator>
416 void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
417 _nb1.clear();
418 _nb1.resize( nrNodes1 );
419 _nb2.clear();
420 _nb2.resize( nrNodes2 );
422 for( EdgeInputIterator e = begin; e != end; e++ )
423 addEdge( e->first, e->second, check );
424 }
427 } // end of namespace dai
430 /** \example example_bipgraph.cpp
431 * This example deals with the following bipartite graph:
432 * \dot
433 * graph example {
434 * ordering=out;
435 * subgraph cluster_type1 {
436 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
437 * 12 [label="2"];
438 * 11 [label="1"];
439 * 10 [label="0"];
440 * }
441 * subgraph cluster_type2 {
442 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
443 * 21 [label="1"];
444 * 20 [label="0"];
445 * }
446 * 10 -- 20;
447 * 11 -- 20;
448 * 12 -- 20;
449 * 11 -- 21;
450 * 12 -- 21;
451 * }
452 * \enddot
453 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
454 * 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).
455 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
456 * how to iterate over nodes and their neighbors.
457 *
458 * \section Output
459 * \verbinclude examples/example_bipgraph.out
460 *
461 * \section Source
462 */
465 #endif