1 /* This file is part of libDAI - http://www.libdai.org/
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.
7 * Copyright (C) 2006-2009 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
13 /// \brief Defines the BipartiteGraph class, which represents a bipartite graph
16 #ifndef __defined_libdai_bipgraph_h
17 #define __defined_libdai_bipgraph_h
24 #include <dai/exceptions.h>
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 nrNodes1()
33 * nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered
34 * 0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-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).
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.
46 class BipartiteGraph
{
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).
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:
68 * void BP::calcNewMessage( size_t i, size_t _I )
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.
82 * Neighbor n = nb1(i,_I);
85 * nb2(n.node,n.dual).node == i
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().
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:
99 * for( size_t i = 0; i < nrVars(); ++i )
100 * foreach( const Neighbor &I, nbV(i) )
101 * calcNewMessage( i, I.iter );
105 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
107 /// Contains the number of the neighboring node
109 /// Contains the "dual" iter
112 /// Default constructor
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
; }
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
;
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()
136 /// Indices of nodes of type 1
137 std::vector
<size_t> ind1
;
138 /// Indices of nodes of type 2
139 std::vector
<size_t> ind2
;
143 /// \name Constructors and destructors
145 /// Default constructor (creates an empty bipartite graph)
146 BipartiteGraph() : _nb1(), _nb2() {}
148 /// Constructs BipartiteGraph from a range of edges.
149 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
150 * \param nrNodes1 The number of nodes of type 1.
151 * \param nrNodes2 The number of nodes of type 2.
152 * \param begin Points to the first edge.
153 * \param end Points just beyond the last edge.
155 template<typename EdgeInputIterator
>
156 BipartiteGraph( size_t nrNodes1
, size_t nrNodes2
, EdgeInputIterator begin
, EdgeInputIterator end
) : _nb1(), _nb2() {
157 construct( nrNodes1
, nrNodes2
, begin
, end
);
161 /// \name Accessors and mutators
163 /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
164 const Neighbor
& nb1( size_t i1
, size_t _i2
) const {
165 DAI_DEBASSERT( i1
< _nb1
.size() );
166 DAI_DEBASSERT( _i2
< _nb1
[i1
].size() );
167 return _nb1
[i1
][_i2
];
169 /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
170 Neighbor
& nb1( size_t i1
, size_t _i2
) {
171 DAI_DEBASSERT( i1
< _nb1
.size() );
172 DAI_DEBASSERT( _i2
< _nb1
[i1
].size() );
173 return _nb1
[i1
][_i2
];
176 /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
177 const Neighbor
& nb2( size_t i2
, size_t _i1
) const {
178 DAI_DEBASSERT( i2
< _nb2
.size() );
179 DAI_DEBASSERT( _i1
< _nb2
[i2
].size() );
180 return _nb2
[i2
][_i1
];
182 /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
183 Neighbor
& nb2( size_t i2
, size_t _i1
) {
184 DAI_DEBASSERT( i2
< _nb2
.size() );
185 DAI_DEBASSERT( _i1
< _nb2
[i2
].size() );
186 return _nb2
[i2
][_i1
];
189 /// Returns constant reference to all neighbors of node \a i1 of type 1
190 const Neighbors
& nb1( size_t i1
) const {
191 DAI_DEBASSERT( i1
< _nb1
.size() );
194 /// Returns reference to all neighbors of node \a i1 of type 1
195 Neighbors
& nb1( size_t i1
) {
196 DAI_DEBASSERT( i1
< _nb1
.size() );
200 /// Returns constant reference to all neighbors of node \a i2 of type 2
201 const Neighbors
& nb2( size_t i2
) const {
202 DAI_DEBASSERT( i2
< _nb2
.size() );
205 /// Returns reference to all neighbors of node \a i2 of type 2
206 Neighbors
& nb2( size_t i2
) {
207 DAI_DEBASSERT( i2
< _nb2
.size() );
212 /// \name Adding nodes and edges
214 /// (Re)constructs BipartiteGraph from a range of edges.
215 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
216 * \param nrNodes1 The number of nodes of type 1.
217 * \param nrNodes2 The number of nodes of type 2.
218 * \param begin Points to the first edge.
219 * \param end Points just beyond the last edge.
221 template<typename EdgeInputIterator
>
222 void construct( size_t nrNodes1
, size_t nrNodes2
, EdgeInputIterator begin
, EdgeInputIterator end
);
224 /// Adds a node of type 1 without neighbors and returns the index of the added node.
225 size_t addNode1() { _nb1
.push_back( Neighbors() ); return _nb1
.size() - 1; }
227 /// Adds a node of type 2 without neighbors and returns the index of the added node.
228 size_t addNode2() { _nb2
.push_back( Neighbors() ); return _nb2
.size() - 1; }
231 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
232 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
233 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
234 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
235 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
236 * \returns Index of the added node.
238 template <typename NodeInputIterator
>
239 size_t addNode1( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
241 nbs1new
.reserve( sizeHint
);
243 for( NodeInputIterator it
= begin
; it
!= end
; ++it
) {
244 DAI_ASSERT( *it
< nrNodes2() );
245 Neighbor
nb1new( iter
, *it
, nb2(*it
).size() );
246 Neighbor
nb2new( nb2(*it
).size(), nrNodes1(), iter
++ );
247 nbs1new
.push_back( nb1new
);
248 nb2( *it
).push_back( nb2new
);
250 _nb1
.push_back( nbs1new
);
251 return _nb1
.size() - 1;
254 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
255 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
256 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
257 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
258 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
259 * \returns Index of the added node.
261 template <typename NodeInputIterator
>
262 size_t addNode2( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
264 nbs2new
.reserve( sizeHint
);
266 for( NodeInputIterator it
= begin
; it
!= end
; ++it
) {
267 DAI_ASSERT( *it
< nrNodes1() );
268 Neighbor
nb2new( iter
, *it
, nb1(*it
).size() );
269 Neighbor
nb1new( nb1(*it
).size(), nrNodes2(), iter
++ );
270 nbs2new
.push_back( nb2new
);
271 nb1( *it
).push_back( nb1new
);
273 _nb2
.push_back( nbs2new
);
274 return _nb2
.size() - 1;
277 /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
278 /** If \a check == \c true, only adds the edge if it does not exist already.
280 void addEdge( size_t n1
, size_t n2
, bool check
= true );
283 /// \name Erasing nodes and edges
285 /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
286 void eraseNode1( size_t n1
);
288 /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
289 void eraseNode2( size_t n2
);
291 /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
292 void eraseEdge( size_t n1
, size_t n2
);
297 /// Returns number of nodes of type 1
298 size_t nrNodes1() const { return _nb1
.size(); }
299 /// Returns number of nodes of type 2
300 size_t nrNodes2() const { return _nb2
.size(); }
302 /// Calculates the number of edges, time complexity: O(nrNodes1())
303 size_t nrEdges() const {
305 for( size_t i1
= 0; i1
< nrNodes1(); i1
++ )
306 sum
+= nb1(i1
).size();
310 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
311 /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
313 std::vector
<size_t> delta1( size_t n1
, bool include
= false ) const;
315 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
316 /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
318 std::vector
<size_t> delta2( size_t n2
, bool include
= false ) const;
320 /// Returns true if the graph is connected
321 bool isConnected() const;
323 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
326 /// Checks internal consistency
327 void checkConsistency() const;
330 /// \name Input and output
332 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
333 void printDot( std::ostream
& os
) const;
338 template<typename EdgeInputIterator
>
339 void BipartiteGraph::construct( size_t nrNodes1
, size_t nrNodes2
, EdgeInputIterator begin
, EdgeInputIterator end
) {
341 _nb1
.resize( nrNodes1
);
343 _nb2
.resize( nrNodes2
);
345 for( EdgeInputIterator e
= begin
; e
!= end
; e
++ ) {
347 addEdge( e
->first
, e
->second
, true );
349 addEdge( e
->first
, e
->second
, false );
355 } // end of namespace dai
358 /** \example example_bipgraph.cpp
359 * This example deals with the following bipartite graph:
363 * subgraph cluster_type1 {
364 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
369 * subgraph cluster_type2 {
370 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
381 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
382 * 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).
383 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
384 * how to iterate over nodes and their neighbors.
387 * \verbinclude examples/example_bipgraph.out