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 bool _edge_indexed;
145 /// Call indexEdges() first to initialize these members
146 std::vector<Edge> _edges;
147 /// Call indexEdges() first to initialize these members
148 hash_map<Edge,size_t> _vv2e;
149 //@}
151 public:
152 /// \name Constructors and destructors
153 //@{
154 /// Default constructor (creates an empty bipartite graph)
155 BipartiteGraph() : _nb1(), _nb2(), _edge_indexed(false) {}
157 /// Constructs BipartiteGraph from a range of edges.
158 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
159 * \param nr1 The number of nodes of type 1.
160 * \param nr2 The number of nodes of type 2.
161 * \param begin Points to the first edge.
162 * \param end Points just beyond the last edge.
163 */
164 template<typename EdgeInputIterator>
165 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ), _edge_indexed(false) {
166 construct( nr1, nr2, begin, end );
167 }
168 //@}
170 /// \name Accessors and mutators
171 //@{
172 /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
173 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
174 DAI_DEBASSERT( i1 < _nb1.size() );
175 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
176 return _nb1[i1][_i2];
177 }
178 /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
179 Neighbor & nb1( size_t i1, size_t _i2 ) {
180 DAI_DEBASSERT( i1 < _nb1.size() );
181 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
182 return _nb1[i1][_i2];
183 }
185 /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
186 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
187 DAI_DEBASSERT( i2 < _nb2.size() );
188 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
189 return _nb2[i2][_i1];
190 }
191 /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
192 Neighbor & nb2( size_t i2, size_t _i1 ) {
193 DAI_DEBASSERT( i2 < _nb2.size() );
194 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
195 return _nb2[i2][_i1];
196 }
198 /// Returns constant reference to all neighbors of node \a i1 of type 1
199 const Neighbors & nb1( size_t i1 ) const {
200 DAI_DEBASSERT( i1 < _nb1.size() );
201 return _nb1[i1];
202 }
203 /// Returns reference to all neighbors of node \a i1 of type 1
204 Neighbors & nb1( size_t i1 ) {
205 DAI_DEBASSERT( i1 < _nb1.size() );
206 return _nb1[i1];
207 }
209 /// Returns constant reference to all neighbors of node \a i2 of type 2
210 const Neighbors & nb2( size_t i2 ) const {
211 DAI_DEBASSERT( i2 < _nb2.size() );
212 return _nb2[i2];
213 }
214 /// Returns reference to all neighbors of node \a i2 of type 2
215 Neighbors & nb2( size_t i2 ) {
216 DAI_DEBASSERT( i2 < _nb2.size() );
217 return _nb2[i2];
218 }
219 //@}
221 /// \name Adding nodes and edges
222 //@{
223 /// (Re)constructs BipartiteGraph from a range of edges.
224 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
225 * \param nr1 The number of nodes of type 1.
226 * \param nr2 The number of nodes of type 2.
227 * \param begin Points to the first edge.
228 * \param end Points just beyond the last edge.
229 */
230 template<typename EdgeInputIterator>
231 void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
233 /// Adds a node of type 1 without neighbors and returns the index of the added node.
234 size_t add1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
236 /// Adds a node of type 2 without neighbors and returns the index of the added node.
237 size_t add2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
239 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
240 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
241 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
242 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
243 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
244 * \returns Index of the added node.
245 */
246 template <typename NodeInputIterator>
247 size_t add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
248 Neighbors nbs1new;
249 nbs1new.reserve( sizeHint );
250 size_t iter = 0;
251 for( NodeInputIterator it = begin; it != end; ++it ) {
252 DAI_ASSERT( *it < nr2() );
253 Neighbor nb1new( iter, *it, nb2(*it).size() );
254 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
255 nbs1new.push_back( nb1new );
256 nb2( *it ).push_back( nb2new );
257 }
258 _nb1.push_back( nbs1new );
259 return _nb1.size() - 1;
260 }
262 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
263 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
264 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
265 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
266 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
267 * \returns Index of the added node.
268 */
269 template <typename NodeInputIterator>
270 size_t 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 return _nb2.size() - 1;
283 }
285 /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
286 /** If \a check == \c true, only adds the edge if it does not exist already.
287 */
288 void addEdge( size_t n1, size_t n2, bool check = true );
289 //@}
291 /// \name Erasing nodes and edges
292 //@{
293 /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
294 void erase1( size_t n1 );
296 /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
297 void erase2( size_t n2 );
299 /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
300 void eraseEdge( size_t n1, size_t n2 );
301 //@}
303 /// \name Queries
304 //@{
305 /// Returns number of nodes of type 1
306 size_t nr1() const { return _nb1.size(); }
307 /// Returns number of nodes of type 2
308 size_t nr2() const { return _nb2.size(); }
310 /// Calculates the number of edges, time complexity: O(nr1())
311 size_t nrEdges() const {
312 size_t sum = 0;
313 for( size_t i1 = 0; i1 < nr1(); i1++ )
314 sum += nb1(i1).size();
315 return sum;
316 }
318 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
319 /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
320 */
321 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
323 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
324 /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
325 */
326 std::vector<size_t> delta2( size_t n2, bool include = false ) const;
328 /// Returns true if the graph is connected
329 /** \todo Should be optimized by invoking boost::graph library
330 */
331 bool isConnected() const;
333 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
334 bool isTree() const;
336 /// Checks internal consistency
337 void checkConsistency() const;
338 //@}
340 /// \name Input and output
341 //@{
342 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
343 void printDot( std::ostream& os ) const;
344 //@}
346 // OBSOLETE
347 /// \name Backwards compatibility layer (to be removed soon)
348 //@{
349 void indexEdges() {
350 std::cerr << "Warning: this BipartiteGraph edge interface is obsolete!" << std::endl;
351 _edges.clear();
352 _vv2e.clear();
353 size_t i=0;
354 foreach(const Neighbors &nb1s, _nb1) {
355 foreach(const Neighbor &n2, nb1s) {
356 Edge e(i, n2.node);
357 _edges.push_back(e);
358 }
359 i++;
360 }
361 sort(_edges.begin(), _edges.end()); // unnecessary?
363 i=0;
364 foreach(const Edge& e, _edges) {
365 _vv2e[e] = i++;
366 }
368 _edge_indexed = true;
369 }
371 const Edge& edge(size_t e) const {
372 DAI_ASSERT(_edge_indexed);
373 return _edges[e];
374 }
376 const std::vector<Edge>& edges() const {
377 return _edges;
378 }
380 size_t VV2E(size_t n1, size_t n2) const {
381 DAI_ASSERT(_edge_indexed);
382 Edge e(n1,n2);
383 hash_map<Edge,size_t>::const_iterator i = _vv2e.find(e);
384 DAI_ASSERT(i != _vv2e.end());
385 return i->second;
386 }
388 size_t nr_edges() const {
389 DAI_ASSERT(_edge_indexed);
390 return _edges.size();
391 }
392 //@}
393 };
396 template<typename EdgeInputIterator>
397 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
398 _nb1.clear();
399 _nb1.resize( nr1 );
400 _nb2.clear();
401 _nb2.resize( nr2 );
403 for( EdgeInputIterator e = begin; e != end; e++ ) {
404 #ifdef DAI_DEBUG
405 addEdge( e->first, e->second, true );
406 #else
407 addEdge( e->first, e->second, false );
408 #endif
409 }
410 }
413 } // end of namespace dai
416 /** \example example_bipgraph.cpp
417 * This example deals with the following bipartite graph:
418 * \dot
419 * graph example {
420 * ordering=out;
421 * subgraph cluster_type1 {
422 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
423 * 12 [label="2"];
424 * 11 [label="1"];
425 * 10 [label="0"];
426 * }
427 * subgraph cluster_type2 {
428 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
429 * 21 [label="1"];
430 * 20 [label="0"];
431 * }
432 * 10 -- 20;
433 * 11 -- 20;
434 * 12 -- 20;
435 * 11 -- 21;
436 * 12 -- 21;
437 * }
438 * \enddot
439 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
440 * 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).
441 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
442 * how to iterate over nodes and their neighbors.
443 *
444 * \section Output
445 * \verbinclude examples/example_bipgraph.out
446 *
447 * \section Source
448 */
451 #endif