1 /* This file is part of libDAI - http://www.libdai.org/
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
10 /// \brief Defines the BipartiteGraph class, which represents a bipartite graph
13 #ifndef __defined_libdai_bipgraph_h
14 #define __defined_libdai_bipgraph_h
21 #include <dai/smallset.h>
22 #include <dai/exceptions.h>
23 #include <dai/graph.h>
29 /// Represents the neighborhood structure of nodes in an undirected, bipartite graph.
30 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
31 * nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1()
32 * nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered
33 * 0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-1. An edge
34 * between node \a n1 of type 1 and node \a n2 of type 2 is represented by a Edge(\a n1,\a n2).
36 * A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
37 * its neighboring nodes. More precisely: it stores for each node of type 1 a vector of Neighbor structures
38 * (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
39 * of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
40 * neighboring nodes of type 1.
41 * Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
42 * Neighbor structures, describing its neighboring nodes of the other type.
43 * \idea Cache second-order neighborhoods in BipartiteGraph.
45 class BipartiteGraph
{
47 /// Contains for each node of type 1 a vector of its neighbors
48 std::vector
<Neighbors
> _nb1
;
50 /// Contains for each node of type 2 a vector of its neighbors
51 std::vector
<Neighbors
> _nb2
;
53 /// Used internally by isTree()
55 /// Indices of nodes of type 1
56 std::vector
<size_t> ind1
;
57 /// Indices of nodes of type 2
58 std::vector
<size_t> ind2
;
62 /// \name Constructors and destructors
64 /// Default constructor (creates an empty bipartite graph)
65 BipartiteGraph() : _nb1(), _nb2() {}
67 /// Constructs BipartiteGraph with \a nr1 nodes of type 1, \a nr2 nodes of type 2 and no edges.
68 BipartiteGraph( size_t nr1
, size_t nr2
) : _nb1(nr1
), _nb2(nr2
) {}
70 /// Constructs BipartiteGraph from a range of edges.
71 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
72 * \param nrNodes1 The number of nodes of type 1.
73 * \param nrNodes2 The number of nodes of type 2.
74 * \param begin Points to the first edge.
75 * \param end Points just beyond the last edge.
76 * \param check Whether to only add an edge if it does not exist already.
78 template<typename EdgeInputIterator
>
79 BipartiteGraph( size_t nrNodes1
, size_t nrNodes2
, EdgeInputIterator begin
, EdgeInputIterator end
, bool check
=true ) : _nb1(), _nb2() {
80 construct( nrNodes1
, nrNodes2
, begin
, end
, check
);
84 /// \name Accessors and mutators
86 /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
87 const Neighbor
& nb1( size_t i1
, size_t _i2
) const {
88 DAI_DEBASSERT( i1
< _nb1
.size() );
89 DAI_DEBASSERT( _i2
< _nb1
[i1
].size() );
92 /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
93 Neighbor
& nb1( size_t i1
, size_t _i2
) {
94 DAI_DEBASSERT( i1
< _nb1
.size() );
95 DAI_DEBASSERT( _i2
< _nb1
[i1
].size() );
99 /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
100 const Neighbor
& nb2( size_t i2
, size_t _i1
) const {
101 DAI_DEBASSERT( i2
< _nb2
.size() );
102 DAI_DEBASSERT( _i1
< _nb2
[i2
].size() );
103 return _nb2
[i2
][_i1
];
105 /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
106 Neighbor
& nb2( size_t i2
, size_t _i1
) {
107 DAI_DEBASSERT( i2
< _nb2
.size() );
108 DAI_DEBASSERT( _i1
< _nb2
[i2
].size() );
109 return _nb2
[i2
][_i1
];
112 /// Returns constant reference to all neighbors of node \a i1 of type 1
113 const Neighbors
& nb1( size_t i1
) const {
114 DAI_DEBASSERT( i1
< _nb1
.size() );
117 /// Returns reference to all neighbors of node \a i1 of type 1
118 Neighbors
& nb1( size_t i1
) {
119 DAI_DEBASSERT( i1
< _nb1
.size() );
123 /// Returns constant reference to all neighbors of node \a i2 of type 2
124 const Neighbors
& nb2( size_t i2
) const {
125 DAI_DEBASSERT( i2
< _nb2
.size() );
128 /// Returns reference to all neighbors of node \a i2 of type 2
129 Neighbors
& nb2( size_t i2
) {
130 DAI_DEBASSERT( i2
< _nb2
.size() );
135 /// \name Adding nodes and edges
137 /// (Re)constructs BipartiteGraph from a range of edges.
138 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
139 * \param nrNodes1 The number of nodes of type 1.
140 * \param nrNodes2 The number of nodes of type 2.
141 * \param begin Points to the first edge.
142 * \param end Points just beyond the last edge.
143 * \param check Whether to only add an edge if it does not exist already.
145 template<typename EdgeInputIterator
>
146 void construct( size_t nrNodes1
, size_t nrNodes2
, EdgeInputIterator begin
, EdgeInputIterator end
, bool check
=true );
148 /// Adds a node of type 1 without neighbors and returns the index of the added node.
149 size_t addNode1() { _nb1
.push_back( Neighbors() ); return _nb1
.size() - 1; }
151 /// Adds a node of type 2 without neighbors and returns the index of the added node.
152 size_t addNode2() { _nb2
.push_back( Neighbors() ); return _nb2
.size() - 1; }
155 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
156 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
157 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
158 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
159 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
160 * \returns Index of the added node.
162 template <typename NodeInputIterator
>
163 size_t addNode1( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
165 nbs1new
.reserve( sizeHint
);
167 for( NodeInputIterator it
= begin
; it
!= end
; ++it
) {
168 DAI_ASSERT( *it
< nrNodes2() );
169 Neighbor
nb1new( iter
, *it
, nb2(*it
).size() );
170 Neighbor
nb2new( nb2(*it
).size(), nrNodes1(), iter
++ );
171 nbs1new
.push_back( nb1new
);
172 nb2( *it
).push_back( nb2new
);
174 _nb1
.push_back( nbs1new
);
175 return _nb1
.size() - 1;
178 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
179 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
180 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
181 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
182 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
183 * \returns Index of the added node.
185 template <typename NodeInputIterator
>
186 size_t addNode2( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
188 nbs2new
.reserve( sizeHint
);
190 for( NodeInputIterator it
= begin
; it
!= end
; ++it
) {
191 DAI_ASSERT( *it
< nrNodes1() );
192 Neighbor
nb2new( iter
, *it
, nb1(*it
).size() );
193 Neighbor
nb1new( nb1(*it
).size(), nrNodes2(), iter
++ );
194 nbs2new
.push_back( nb2new
);
195 nb1( *it
).push_back( nb1new
);
197 _nb2
.push_back( nbs2new
);
198 return _nb2
.size() - 1;
201 /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
202 /** If \a check == \c true, only adds the edge if it does not exist already.
204 BipartiteGraph
& addEdge( size_t n1
, size_t n2
, bool check
= true );
207 /// \name Erasing nodes and edges
209 /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
210 void eraseNode1( size_t n1
);
212 /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
213 void eraseNode2( size_t n2
);
215 /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
216 void eraseEdge( size_t n1
, size_t n2
);
221 /// Returns number of nodes of type 1
222 size_t nrNodes1() const { return _nb1
.size(); }
223 /// Returns number of nodes of type 2
224 size_t nrNodes2() const { return _nb2
.size(); }
226 /// Calculates the number of edges, time complexity: O(nrNodes1())
227 size_t nrEdges() const {
229 for( size_t i1
= 0; i1
< nrNodes1(); i1
++ )
230 sum
+= nb1(i1
).size();
234 /// Returns true if the graph contains an edge between node \a n1 of type 1 and node \a n2 of type 2.
235 /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
237 bool hasEdge( size_t n1
, size_t n2
) const {
238 if( nb1(n1
).size() < nb2(n2
).size() ) {
239 for( size_t _n2
= 0; _n2
< nb1(n1
).size(); _n2
++ )
240 if( nb1( n1
, _n2
) == n2
)
243 for( size_t _n1
= 0; _n1
< nb2(n2
).size(); _n1
++ )
244 if( nb2( n2
, _n1
) == n1
)
250 /// Returns the index of a given node \a n2 of type 2 amongst the neighbors of node \a n1 of type 1
251 /** \note The time complexity is linear in the number of neighbors of \a n1
252 * \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1
254 size_t findNb1( size_t n1
, size_t n2
) {
255 for( size_t _n2
= 0; _n2
< nb1(n1
).size(); _n2
++ )
256 if( nb1( n1
, _n2
) == n2
)
258 DAI_THROW(OBJECT_NOT_FOUND
);
259 return nb1(n1
).size();
262 /// Returns the index of a given node \a n1 of type 1 amongst the neighbors of node \a n2 of type 2
263 /** \note The time complexity is linear in the number of neighbors of \a n2
264 * \throw OBJECT_NOT_FOUND if \a n1 is not a neighbor of \a n2
266 size_t findNb2( size_t n1
, size_t n2
) {
267 for( size_t _n1
= 0; _n1
< nb2(n2
).size(); _n1
++ )
268 if( nb2( n2
, _n1
) == n1
)
270 DAI_THROW(OBJECT_NOT_FOUND
);
271 return nb2(n2
).size();
274 /// Returns neighbors of node \a n1 of type 1 as a SmallSet<size_t>.
275 SmallSet
<size_t> nb1Set( size_t n1
) const;
277 /// Returns neighbors of node \a n2 of type 2 as a SmallSet<size_t>.
278 SmallSet
<size_t> nb2Set( size_t n2
) const;
280 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
281 /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
282 * \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
284 SmallSet
<size_t> delta1( size_t n1
, bool include
= false ) const;
286 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
287 /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
288 * \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
290 SmallSet
<size_t> delta2( size_t n2
, bool include
= false ) const;
292 /// Returns true if the graph is connected
293 bool isConnected() const;
295 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
298 /// Comparison operator which returns true if two graphs are identical
299 /** \note Two graphs are called identical if they have the same number of nodes
300 * of both types and the same edges (i.e., \a x has an edge between nodes
301 * \a n1 and \a n2 if and only if \c *this has an edge between nodes \a n1 and \a n2).
303 bool operator==( const BipartiteGraph
& x
) const {
304 if( nrNodes1() != x
.nrNodes1() )
306 if( nrNodes2() != x
.nrNodes2() )
308 for( size_t n1
= 0; n1
< nrNodes1(); n1
++ ) {
309 if( nb1(n1
).size() != x
.nb1(n1
).size() )
311 bforeach( const Neighbor
&n2
, nb1(n1
) )
312 if( !x
.hasEdge( n1
, n2
) )
314 bforeach( const Neighbor
&n2
, x
.nb1(n1
) )
315 if( !hasEdge( n1
, n2
) )
321 /// Asserts internal consistency
322 void checkConsistency() const;
325 /// \name Input and output
327 /// Writes a BipartiteGraph to an output stream in GraphViz .dot syntax
328 void printDot( std::ostream
& os
) const;
330 /// Writes a BipartiteGraph to an output stream
331 friend std::ostream
& operator<<( std::ostream
& os
, const BipartiteGraph
& g
) {
336 /// Formats a BipartiteGraph as a string
337 std::string
toString() const {
338 std::stringstream ss
;
346 template<typename EdgeInputIterator
>
347 void BipartiteGraph::construct( size_t nrNodes1
, size_t nrNodes2
, EdgeInputIterator begin
, EdgeInputIterator end
, bool check
) {
349 _nb1
.resize( nrNodes1
);
351 _nb2
.resize( nrNodes2
);
353 for( EdgeInputIterator e
= begin
; e
!= end
; e
++ )
354 addEdge( e
->first
, e
->second
, check
);
358 } // end of namespace dai
361 /** \example example_bipgraph.cpp
362 * This example deals with the following bipartite graph:
366 * subgraph cluster_type1 {
367 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
372 * subgraph cluster_type2 {
373 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
384 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
385 * 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).
386 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
387 * how to iterate over nodes and their neighbors.
390 * \verbinclude examples/example_bipgraph.out