1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
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]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
12 /// \file
13 /// \brief Defines the 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 an undirected, 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. More precisely: 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 b
55 * 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 std::vector<\link Neighbor \endlink>, and
58 * extra information is included in the Neighbor struct which
59 * allows us to access a node as a neighbor of its neighbor
60 * (the \c dual member).
61 *
62 * By convention, variable identifiers naming indices into a
63 * vector of neighbors are prefixed with an underscore ("_").
64 * The neighbor list which they point into is then understood
65 * from context. For example:
66 *
67 * \code
68 * void BP::calcNewMessage( size_t i, size_t _I )
69 * \endcode
70 *
71 * Here, \a i is the "absolute" index of node i, but \a _I is
72 * understood as a "relative" index, giving node \a I 's entry in
73 * <tt>nb1(i)</tt>. The corresponding Neighbor structure can be
74 * accessed as <tt>nb1(i,_I)</tt> or <tt>nb1(i)[_I]</tt>. The
75 * absolute index of \a _I, which would be called \a I, can be
76 * recovered from the \c node member: <tt>nb1(i,_I).node</tt>.
77 * The \c iter member gives the relative index \a _I, and the
78 * \c dual member gives the "dual" relative index, i.e., the
79 * index of \a i in \a I 's neighbor list.
80 *
81 * \code
82 * Neighbor n = nb1(i,_I);
83 * n.node == I &&
84 * n.iter == _I &&
85 * nb2(n.node,n.dual).node == i
86 * \endcode
87 *
88 * In a FactorGraph, the nodes of type 1 represent variables, and
89 * the nodes of type 2 represent factors. For convenience, nb1() is
90 * called FactorGraph::nbV(), and nb2() is called FactorGraph::nbF().
91 *
92 * There is no easy way to transform a pair of absolute node
93 * indices \a i and \a I into a Neighbor structure relative
94 * to one of the nodes. Such a feature has never yet been
95 * found to be necessary. Iteration over edges can always be
96 * accomplished using the Neighbor lists, and by writing
97 * functions that accept relative indices:
98 * \code
99 * for( size_t i = 0; i < nrVars(); ++i )
100 * foreach( const Neighbor &I, nbV(i) )
101 * calcNewMessage( i, I.iter );
102 * \endcode
103 */
104 struct Neighbor {
105 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
106 size_t iter;
107 /// Contains the number of the neighboring node
108 size_t node;
109 /// Contains the "dual" iter
110 size_t dual;
112 /// Default constructor
113 Neighbor() {}
114 /// Constructor that sets the Neighbor members according to the parameters
115 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
117 /// Cast to \c size_t returns \c node member
118 operator size_t () const { return node; }
119 };
121 /// Describes the neighbors of some node.
122 typedef std::vector<Neighbor> Neighbors;
124 /// 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.
125 typedef std::pair<size_t,size_t> Edge;
127 private:
128 /// Contains for each node of type 1 a vector of its neighbors
129 std::vector<Neighbors> _nb1;
131 /// Contains for each node of type 2 a vector of its neighbors
132 std::vector<Neighbors> _nb2;
134 /// Used internally by isTree()
135 struct levelType {
136 std::vector<size_t> ind1; // indices of nodes of type 1
137 std::vector<size_t> ind2; // indices of nodes of type 2
138 };
140 // OBSOLETE
141 /// \name Backwards compatibility layer (to be removed soon)
142 //@{
143 /// Enable backwards compatibility layer?
144 /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
145 */
146 bool _edge_indexed;
147 /// Call indexEdges() first to initialize these members
148 /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
149 */
150 std::vector<Edge> _edges;
151 /// Call indexEdges() first to initialize these members
152 /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
153 */
154 hash_map<Edge,size_t> _vv2e;
155 //@}
157 public:
158 /// \name Constructors and destructors
159 //@{
160 /// Default constructor (creates an empty bipartite graph)
161 BipartiteGraph() : _nb1(), _nb2(), _edge_indexed(false) {}
163 /// Constructs BipartiteGraph from a range of edges.
164 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
165 * \param nr1 The number of nodes of type 1.
166 * \param nr2 The number of nodes of type 2.
167 * \param begin Points to the first edge.
168 * \param end Points just beyond the last edge.
169 */
170 template<typename EdgeInputIterator>
171 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ), _edge_indexed(false) {
172 construct( nr1, nr2, begin, end );
173 }
174 //@}
176 /// \name Accessors and mutators
177 //@{
178 /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
179 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
180 DAI_DEBASSERT( i1 < _nb1.size() );
181 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
182 return _nb1[i1][_i2];
183 }
184 /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
185 Neighbor & nb1( size_t i1, size_t _i2 ) {
186 DAI_DEBASSERT( i1 < _nb1.size() );
187 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
188 return _nb1[i1][_i2];
189 }
191 /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
192 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
193 DAI_DEBASSERT( i2 < _nb2.size() );
194 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
195 return _nb2[i2][_i1];
196 }
197 /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
198 Neighbor & nb2( size_t i2, size_t _i1 ) {
199 DAI_DEBASSERT( i2 < _nb2.size() );
200 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
201 return _nb2[i2][_i1];
202 }
204 /// Returns constant reference to all neighbors of node \a i1 of type 1
205 const Neighbors & nb1( size_t i1 ) const {
206 DAI_DEBASSERT( i1 < _nb1.size() );
207 return _nb1[i1];
208 }
209 /// Returns reference to all neighbors of node \a i1 of type 1
210 Neighbors & nb1( size_t i1 ) {
211 DAI_DEBASSERT( i1 < _nb1.size() );
212 return _nb1[i1];
213 }
215 /// Returns constant reference to all neighbors of node \a i2 of type 2
216 const Neighbors & nb2( size_t i2 ) const {
217 DAI_DEBASSERT( i2 < _nb2.size() );
218 return _nb2[i2];
219 }
220 /// Returns reference to all neighbors of node \a i2 of type 2
221 Neighbors & nb2( size_t i2 ) {
222 DAI_DEBASSERT( i2 < _nb2.size() );
223 return _nb2[i2];
224 }
225 //@}
227 /// \name Adding nodes and edges
228 //@{
229 /// (Re)constructs BipartiteGraph from a range of edges.
230 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
231 * \param nr1 The number of nodes of type 1.
232 * \param nr2 The number of nodes of type 2.
233 * \param begin Points to the first edge.
234 * \param end Points just beyond the last edge.
235 */
236 template<typename EdgeInputIterator>
237 void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
239 /// Adds a node of type 1 without neighbors and returns the index of the added node.
240 size_t add1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
242 /// Adds a node of type 2 without neighbors and returns the index of the added node.
243 size_t add2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
245 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
246 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
247 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
248 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
249 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
250 * \returns Index of the added node.
251 */
252 template <typename NodeInputIterator>
253 size_t add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
254 Neighbors nbs1new;
255 nbs1new.reserve( sizeHint );
256 size_t iter = 0;
257 for( NodeInputIterator it = begin; it != end; ++it ) {
258 DAI_ASSERT( *it < nr2() );
259 Neighbor nb1new( iter, *it, nb2(*it).size() );
260 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
261 nbs1new.push_back( nb1new );
262 nb2( *it ).push_back( nb2new );
263 }
264 _nb1.push_back( nbs1new );
265 return _nb1.size() - 1;
266 }
268 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
269 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
270 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
271 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
272 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
273 * \returns Index of the added node.
274 */
275 template <typename NodeInputIterator>
276 size_t add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
277 Neighbors nbs2new;
278 nbs2new.reserve( sizeHint );
279 size_t iter = 0;
280 for( NodeInputIterator it = begin; it != end; ++it ) {
281 DAI_ASSERT( *it < nr1() );
282 Neighbor nb2new( iter, *it, nb1(*it).size() );
283 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
284 nbs2new.push_back( nb2new );
285 nb1( *it ).push_back( nb1new );
286 }
287 _nb2.push_back( nbs2new );
288 return _nb2.size() - 1;
289 }
291 /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
292 /** If \a check == \c true, only adds the edge if it does not exist already.
293 */
294 void addEdge( size_t n1, size_t n2, bool check = true );
295 //@}
297 /// \name Erasing nodes and edges
298 //@{
299 /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
300 void erase1( size_t n1 );
302 /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
303 void erase2( size_t n2 );
305 /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
306 void eraseEdge( size_t n1, size_t n2 );
307 //@}
309 /// \name Queries
310 //@{
311 /// Returns number of nodes of type 1
312 size_t nr1() const { return _nb1.size(); }
313 /// Returns number of nodes of type 2
314 size_t nr2() const { return _nb2.size(); }
316 /// Calculates the number of edges, time complexity: O(nr1())
317 size_t nrEdges() const {
318 size_t sum = 0;
319 for( size_t i1 = 0; i1 < nr1(); i1++ )
320 sum += nb1(i1).size();
321 return sum;
322 }
324 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
325 /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
326 */
327 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
329 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
330 /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
331 */
332 std::vector<size_t> delta2( size_t n2, bool include = false ) const;
334 /// Returns true if the graph is connected
335 /** \todo Should be optimized by invoking boost::graph library
336 */
337 bool isConnected() const;
339 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
340 bool isTree() const;
342 /// Checks internal consistency
343 void checkConsistency() const;
344 //@}
346 /// \name Input and output
347 //@{
348 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
349 void printDot( std::ostream& os ) const;
350 //@}
352 // OBSOLETE
353 /// \name Backwards compatibility layer (to be removed soon)
354 //@{
355 /// Prepare backwards compatibility layer for indexed edges
356 /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
357 */
358 void indexEdges() {
359 std::cerr << "Warning: this BipartiteGraph edge interface is obsolete!" << std::endl;
360 _edges.clear();
361 _vv2e.clear();
362 size_t i=0;
363 foreach(const Neighbors &nb1s, _nb1) {
364 foreach(const Neighbor &n2, nb1s) {
365 Edge e(i, n2.node);
366 _edges.push_back(e);
367 }
368 i++;
369 }
370 sort(_edges.begin(), _edges.end()); // unnecessary?
372 i=0;
373 foreach(const Edge& e, _edges) {
374 _vv2e[e] = i++;
375 }
377 _edge_indexed = true;
378 }
380 /// Returns edge with index \a e
381 /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
382 */
383 const Edge& edge(size_t e) const {
384 DAI_ASSERT(_edge_indexed);
385 return _edges[e];
386 }
388 /// Returns all edges
389 /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
390 */
391 const std::vector<Edge>& edges() const {
392 return _edges;
393 }
395 /// Converts a pair of node indices to an edge index
396 /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
397 */
398 size_t VV2E(size_t n1, size_t n2) const {
399 DAI_ASSERT(_edge_indexed);
400 Edge e(n1,n2);
401 hash_map<Edge,size_t>::const_iterator i = _vv2e.find(e);
402 DAI_ASSERT(i != _vv2e.end());
403 return i->second;
404 }
406 /// Returns number of edges
407 /** \deprecated Please use the BipartiteGraph::Neighbor interface instead
408 */
409 size_t nr_edges() const {
410 DAI_ASSERT(_edge_indexed);
411 return _edges.size();
412 }
413 //@}
414 };
417 template<typename EdgeInputIterator>
418 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
419 _nb1.clear();
420 _nb1.resize( nr1 );
421 _nb2.clear();
422 _nb2.resize( nr2 );
424 for( EdgeInputIterator e = begin; e != end; e++ ) {
425 #ifdef DAI_DEBUG
426 addEdge( e->first, e->second, true );
427 #else
428 addEdge( e->first, e->second, false );
429 #endif
430 }
431 }
434 } // end of namespace dai
437 /** \example example_bipgraph.cpp
438 * This example deals with the following bipartite graph:
439 * \dot
440 * graph example {
441 * ordering=out;
442 * subgraph cluster_type1 {
443 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
444 * 12 [label="2"];
445 * 11 [label="1"];
446 * 10 [label="0"];
447 * }
448 * subgraph cluster_type2 {
449 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
450 * 21 [label="1"];
451 * 20 [label="0"];
452 * }
453 * 10 -- 20;
454 * 11 -- 20;
455 * 12 -- 20;
456 * 11 -- 21;
457 * 12 -- 21;
458 * }
459 * \enddot
460 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
461 * 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).
462 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
463 * how to iterate over nodes and their neighbors.
464 *
465 * \section Output
466 * \verbinclude examples/example_bipgraph.out
467 *
468 * \section Source
469 */
472 #endif