1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
5 This file is part of libDAI.
7 libDAI is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 libDAI is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with libDAI; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24 /// \brief Defines BipartiteGraph class
27 #ifndef __defined_libdai_bipgraph_h
28 #define __defined_libdai_bipgraph_h
41 /// Represents the neighborhood structure of nodes in a bipartite graph.
42 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
43 * nodes of different type. Nodes are indexed by an unsigned integer. If there are nr1()
44 * nodes of type 1 and nr2() nodes of type 2, the nodes of type 1 are numbered
45 * 0,1,2,...,nr1()-1 and the nodes of type 2 are numbered 0,1,2,...,nr2()-1. An edge
46 * between node \a n1 of type 1 and node \a n2 of type 2 is represented by a BipartiteGraph::Edge(\a n1,\a n2).
48 * A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
49 * its neighboring nodes. In particular, it stores for each node of type 1 a vector of Neighbor structures
50 * (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
51 * of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
52 * neighboring nodes of type 1.
53 * Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
54 * Neighbor structures, describing its neighboring nodes of the other type.
55 * \idea Cache second-order neighborhoods in BipartiteGraph.
57 class BipartiteGraph
{
59 /// Describes the neighbor relationship of two nodes in a BipartiteGraph.
60 /** Sometimes we want to do an action, such as sending a
61 * message, for all edges in a graph. However, most graphs
62 * will be sparse, so we need some way of storing a set of
63 * the neighbors of a node, which is both fast and
64 * memory-efficient. We also need to be able to go between
65 * viewing node \a A as a neighbor of node \a B, and node \a
66 * B as a neighbor of node \a A. The Neighbor struct solves
67 * both of these problems. Each node has a list of neighbors,
68 * stored as a vector<Neighbor>, and extra information is
69 * included in the Neighbor struct which allows us to access
70 * a node as a neighbor of its neighbor (the \a dual member).
72 * By convention, variable identifiers naming indices into a
73 * vector of neighbors are prefixed with an underscore ("_").
74 * The neighbor list which they point into is then understood
75 * from context. For example:
78 * void BP::calcNewMessage( size_t i, size_t _I )
81 * Here, \a i is the "absolute" index of node i, but \a _I is
82 * understood as a "relative" index, giving node I's entry in
83 * nb1(i). The corresponding Neighbor structure can be
84 * accessed as nb1(i,_I) or nb1(i)[_I]. The absolute index of
85 * \a _I, which would be called \a I, can be recovered from
86 * the \a node member: nb1(i,_I).node. The \a iter member
87 * gives the relative index \a _I, and the \a dual member
88 * gives the "dual" relative index, i.e. the index of \a i in
89 * \a I's neighbor list.
92 * Neighbor n = nb1(i,_I);
95 * nb2(n.node,n.dual).node == i
98 * In a FactorGraph, nb1 is called nbV, and nb2 is called
101 * There is no easy way to transform a pair of absolute node
102 * indices \a i and \a I into a Neighbor structure relative
103 * to one of the nodes. Such a feature has never yet been
104 * found to be necessary. Iteration over edges can always be
105 * accomplished using the Neighbor lists, and by writing
106 * functions that accept relative indices:
108 * for( size_t i = 0; i < nrVars(); ++i )
109 * foreach( const Neighbor &I, nbV(i) )
110 * calcNewMessage( i, I.iter );
114 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
116 /// Contains the number of the neighboring node
118 /// Contains the "dual" iter
121 /// Default constructor
123 /// Constructor that sets the Neighbor members according to the parameters
124 Neighbor( size_t iter
, size_t node
, size_t dual
) : iter(iter
), node(node
), dual(dual
) {}
126 /// Cast to size_t returns node member
127 operator size_t () const { return node
; }
130 /// Describes the neighbors of some node.
131 typedef std::vector
<Neighbor
> Neighbors
;
133 /// 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.
134 typedef std::pair
<size_t,size_t> Edge
;
137 /// Contains for each node of type 1 a vector of its neighbors
138 std::vector
<Neighbors
> _nb1
;
140 /// Contains for each node of type 2 a vector of its neighbors
141 std::vector
<Neighbors
> _nb2
;
143 /// Used internally by isTree()
145 std::vector
<size_t> ind1
; // indices of nodes of type 1
146 std::vector
<size_t> ind2
; // indices of nodes of type 2
150 /// @name Backwards compatibility layer (to be removed soon)
152 /// Enable backwards compatibility layer?
154 /// Call indexEdges() first to initialize these members
155 std::vector
<Edge
> _edges
;
156 /// Call indexEdges() first to initialize these members
157 hash_map
<Edge
,size_t> _vv2e
;
161 /// Default constructor (creates an empty bipartite graph)
162 BipartiteGraph() : _nb1(), _nb2(), _edge_indexed(false) {}
164 /// Constructs BipartiteGraph from a range of edges.
165 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
166 * \param nr1 The number of nodes of type 1.
167 * \param nr2 The number of nodes of type 2.
168 * \param begin Points to the first edge.
169 * \param end Points just beyond the last edge.
171 template<typename EdgeInputIterator
>
172 BipartiteGraph( size_t nr1
, size_t nr2
, EdgeInputIterator begin
, EdgeInputIterator end
) : _nb1( nr1
), _nb2( nr2
), _edge_indexed(false) {
173 construct( nr1
, nr2
, begin
, end
);
176 /// (Re)constructs BipartiteGraph from a range of edges.
177 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
178 * \param nr1 The number of nodes of type 1.
179 * \param nr2 The number of nodes of type 2.
180 * \param begin Points to the first edge.
181 * \param end Points just beyond the last edge.
183 template<typename EdgeInputIterator
>
184 void construct( size_t nr1
, size_t nr2
, EdgeInputIterator begin
, EdgeInputIterator end
);
186 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
187 const Neighbor
& nb1( size_t i1
, size_t _i2
) const {
188 DAI_DEBASSERT( i1
< _nb1
.size() );
189 DAI_DEBASSERT( _i2
< _nb1
[i1
].size() );
190 return _nb1
[i1
][_i2
];
192 /// Returns reference to the _i2'th neighbor of node i1 of type 1
193 Neighbor
& nb1( size_t i1
, size_t _i2
) {
194 DAI_DEBASSERT( i1
< _nb1
.size() );
195 DAI_DEBASSERT( _i2
< _nb1
[i1
].size() );
196 return _nb1
[i1
][_i2
];
199 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
200 const Neighbor
& nb2( size_t i2
, size_t _i1
) const {
201 DAI_DEBASSERT( i2
< _nb2
.size() );
202 DAI_DEBASSERT( _i1
< _nb2
[i2
].size() );
203 return _nb2
[i2
][_i1
];
205 /// Returns reference to the _i1'th neighbor of node i2 of type 2
206 Neighbor
& nb2( size_t i2
, size_t _i1
) {
207 DAI_DEBASSERT( i2
< _nb2
.size() );
208 DAI_DEBASSERT( _i1
< _nb2
[i2
].size() );
209 return _nb2
[i2
][_i1
];
212 /// Returns constant reference to all neighbors of node i1 of type 1
213 const Neighbors
& nb1( size_t i1
) const {
214 DAI_DEBASSERT( i1
< _nb1
.size() );
217 /// Returns reference to all neighbors of node of i1 type 1
218 Neighbors
& nb1( size_t i1
) {
219 DAI_DEBASSERT( i1
< _nb1
.size() );
223 /// Returns constant reference to all neighbors of node i2 of type 2
224 const Neighbors
& nb2( size_t i2
) const {
225 DAI_DEBASSERT( i2
< _nb2
.size() );
228 /// Returns reference to all neighbors of node i2 of type 2
229 Neighbors
& nb2( size_t i2
) {
230 DAI_DEBASSERT( i2
< _nb2
.size() );
234 /// Returns number of nodes of type 1
235 size_t nr1() const { return _nb1
.size(); }
236 /// Returns number of nodes of type 2
237 size_t nr2() const { return _nb2
.size(); }
239 /// Calculates the number of edges, time complexity: O(nr1())
240 size_t nrEdges() const {
242 for( size_t i1
= 0; i1
< nr1(); i1
++ )
243 sum
+= nb1(i1
).size();
247 /// Adds a node of type 1 without neighbors.
248 void add1() { _nb1
.push_back( Neighbors() ); }
250 /// Adds a node of type 2 without neighbors.
251 void add2() { _nb2
.push_back( Neighbors() ); }
253 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
254 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
255 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
256 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
257 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
259 template <typename NodeInputIterator
>
260 void add1( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
262 nbs1new
.reserve( sizeHint
);
264 for( NodeInputIterator it
= begin
; it
!= end
; ++it
) {
265 assert( *it
< nr2() );
266 Neighbor
nb1new( iter
, *it
, nb2(*it
).size() );
267 Neighbor
nb2new( nb2(*it
).size(), nr1(), iter
++ );
268 nbs1new
.push_back( nb1new
);
269 nb2( *it
).push_back( nb2new
);
271 _nb1
.push_back( nbs1new
);
274 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
275 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
276 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
277 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
278 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
280 template <typename NodeInputIterator
>
281 void add2( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
283 nbs2new
.reserve( sizeHint
);
285 for( NodeInputIterator it
= begin
; it
!= end
; ++it
) {
286 assert( *it
< nr1() );
287 Neighbor
nb2new( iter
, *it
, nb1(*it
).size() );
288 Neighbor
nb1new( nb1(*it
).size(), nr2(), iter
++ );
289 nbs2new
.push_back( nb2new
);
290 nb1( *it
).push_back( nb1new
);
292 _nb2
.push_back( nbs2new
);
295 /// Removes node n1 of type 1 and all incident edges.
296 void erase1( size_t n1
);
298 /// Removes node n2 of type 2 and all incident edges.
299 void erase2( size_t n2
);
301 /// Removes edge between node n1 of type 1 and node n2 of type 2.
302 void eraseEdge( size_t n1
, size_t n2
) {
303 assert( n1
< nr1() );
304 assert( n2
< nr2() );
305 for( Neighbors::iterator i1
= _nb1
[n1
].begin(); i1
!= _nb1
[n1
].end(); i1
++ )
306 if( i1
->node
== n2
) {
307 _nb1
[n1
].erase( i1
);
310 for( Neighbors::iterator i2
= _nb2
[n2
].begin(); i2
!= _nb2
[n2
].end(); i2
++ )
311 if( i2
->node
== n1
) {
312 _nb2
[n2
].erase( i2
);
317 /// Adds an edge between node n1 of type 1 and node n2 of type 2.
318 /** If check == true, only adds the edge if it does not exist already.
320 void addEdge( size_t n1
, size_t n2
, bool check
= true ) {
321 assert( n1
< nr1() );
322 assert( n2
< nr2() );
325 // Check whether the edge already exists
326 foreach( const Neighbor
&nb2
, nb1(n1
) )
332 if( !exists
) { // Add edge
333 Neighbor
nb_1( _nb1
[n1
].size(), n2
, _nb2
[n2
].size() );
334 Neighbor
nb_2( nb_1
.dual
, n1
, nb_1
.iter
);
335 _nb1
[n1
].push_back( nb_1
);
336 _nb2
[n2
].push_back( nb_2
);
340 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
341 /** If include == true, includes n1 itself, otherwise excludes n1.
343 std::vector
<size_t> delta1( size_t n1
, bool include
= false ) const;
345 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
346 /** If include == true, includes n2 itself, otherwise excludes n2.
348 std::vector
<size_t> delta2( size_t n2
, bool include
= false ) const;
350 /// Returns true if the graph is connected
351 /** \todo Should be optimized by invoking boost::graph library
353 bool isConnected() const;
355 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
358 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
359 void printDot( std::ostream
& os
) const;
362 /// @name Backwards compatibility layer (to be removed soon)
365 std::cerr
<< "Warning: this BipartiteGraph edge interface is obsolete!" << std::endl
;
369 foreach(const Neighbors
&nb1s
, _nb1
) {
370 foreach(const Neighbor
&n2
, nb1s
) {
376 sort(_edges
.begin(), _edges
.end()); // unnecessary?
379 foreach(const Edge
& e
, _edges
) {
383 _edge_indexed
= true;
386 const Edge
& edge(size_t e
) const {
387 assert(_edge_indexed
);
391 const std::vector
<Edge
>& edges() const {
395 size_t VV2E(size_t n1
, size_t n2
) const {
396 assert(_edge_indexed
);
398 hash_map
<Edge
,size_t>::const_iterator i
= _vv2e
.find(e
);
399 assert(i
!= _vv2e
.end());
403 size_t nr_edges() const {
404 assert(_edge_indexed
);
405 return _edges
.size();
410 /// Checks internal consistency
415 template<typename EdgeInputIterator
>
416 void BipartiteGraph::construct( size_t nr1
, size_t nr2
, EdgeInputIterator begin
, EdgeInputIterator end
) {
422 for( EdgeInputIterator e
= begin
; e
!= end
; e
++ ) {
424 addEdge( e
->first
, e
->second
, true );
426 addEdge( e
->first
, e
->second
, false );
432 } // end of namespace dai
435 /** \example example_bipgraph.cpp
436 * This example deals with the following bipartite graph:
440 * subgraph cluster_type1 {
441 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
446 * subgraph cluster_type2 {
447 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
458 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
459 * 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).
460 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
461 * how to iterate over nodes and their neighbors.
464 * \verbinclude examples/example_bipgraph.out