1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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-2010 Joris Mooij [joris dot mooij at libdai dot org]
9 */
12 /// \file
13 /// \brief Defines the BipartiteGraph class, which represents a bipartite graph
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/smallset.h>
25 #include <dai/exceptions.h>
26 #include <dai/graph.h>
29 namespace dai {
32 /// Represents the neighborhood structure of nodes in an undirected, bipartite graph.
33 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
34 * nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1()
35 * nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered
36 * 0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-1. An edge
37 * between node \a n1 of type 1 and node \a n2 of type 2 is represented by a Edge(\a n1,\a n2).
38 *
39 * A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of
40 * its neighboring nodes. More precisely: it stores for each node of type 1 a vector of Neighbor structures
41 * (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node
42 * of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the
43 * neighboring nodes of type 1.
44 * Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of
45 * Neighbor structures, describing its neighboring nodes of the other type.
46 * \idea Cache second-order neighborhoods in BipartiteGraph.
47 */
48 class BipartiteGraph {
49 private:
50 /// Contains for each node of type 1 a vector of its neighbors
51 std::vector<Neighbors> _nb1;
53 /// Contains for each node of type 2 a vector of its neighbors
54 std::vector<Neighbors> _nb2;
56 /// Used internally by isTree()
57 struct levelType {
58 /// Indices of nodes of type 1
59 std::vector<size_t> ind1;
60 /// Indices of nodes of type 2
61 std::vector<size_t> ind2;
62 };
64 public:
65 /// \name Constructors and destructors
66 //@{
67 /// Default constructor (creates an empty bipartite graph)
68 BipartiteGraph() : _nb1(), _nb2() {}
70 /// Constructs BipartiteGraph with \a nr1 nodes of type 1, \a nr2 nodes of type 2 and no edges.
71 BipartiteGraph( size_t nr1, size_t nr2 ) : _nb1(nr1), _nb2(nr2) {}
73 /// Constructs BipartiteGraph from a range of edges.
74 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
75 * \param nrNodes1 The number of nodes of type 1.
76 * \param nrNodes2 The number of nodes of type 2.
77 * \param begin Points to the first edge.
78 * \param end Points just beyond the last edge.
79 * \param check Whether to only add an edge if it does not exist already.
80 */
81 template<typename EdgeInputIterator>
82 BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb1(), _nb2() {
83 construct( nrNodes1, nrNodes2, begin, end, check );
84 }
85 //@}
87 /// \name Accessors and mutators
88 //@{
89 /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
90 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
91 DAI_DEBASSERT( i1 < _nb1.size() );
92 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
93 return _nb1[i1][_i2];
94 }
95 /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
96 Neighbor & nb1( size_t i1, size_t _i2 ) {
97 DAI_DEBASSERT( i1 < _nb1.size() );
98 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
99 return _nb1[i1][_i2];
100 }
102 /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
103 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
104 DAI_DEBASSERT( i2 < _nb2.size() );
105 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
106 return _nb2[i2][_i1];
107 }
108 /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
109 Neighbor & nb2( size_t i2, size_t _i1 ) {
110 DAI_DEBASSERT( i2 < _nb2.size() );
111 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
112 return _nb2[i2][_i1];
113 }
115 /// Returns constant reference to all neighbors of node \a i1 of type 1
116 const Neighbors & nb1( size_t i1 ) const {
117 DAI_DEBASSERT( i1 < _nb1.size() );
118 return _nb1[i1];
119 }
120 /// Returns reference to all neighbors of node \a i1 of type 1
121 Neighbors & nb1( size_t i1 ) {
122 DAI_DEBASSERT( i1 < _nb1.size() );
123 return _nb1[i1];
124 }
126 /// Returns constant reference to all neighbors of node \a i2 of type 2
127 const Neighbors & nb2( size_t i2 ) const {
128 DAI_DEBASSERT( i2 < _nb2.size() );
129 return _nb2[i2];
130 }
131 /// Returns reference to all neighbors of node \a i2 of type 2
132 Neighbors & nb2( size_t i2 ) {
133 DAI_DEBASSERT( i2 < _nb2.size() );
134 return _nb2[i2];
135 }
136 //@}
138 /// \name Adding nodes and edges
139 //@{
140 /// (Re)constructs BipartiteGraph from a range of edges.
141 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
142 * \param nrNodes1 The number of nodes of type 1.
143 * \param nrNodes2 The number of nodes of type 2.
144 * \param begin Points to the first edge.
145 * \param end Points just beyond the last edge.
146 * \param check Whether to only add an edge if it does not exist already.
147 */
148 template<typename EdgeInputIterator>
149 void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
151 /// Adds a node of type 1 without neighbors and returns the index of the added node.
152 size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
154 /// Adds a node of type 2 without neighbors and returns the index of the added node.
155 size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
158 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
159 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
160 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
161 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
162 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
163 * \returns Index of the added node.
164 */
165 template <typename NodeInputIterator>
166 size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
167 Neighbors nbs1new;
168 nbs1new.reserve( sizeHint );
169 size_t iter = 0;
170 for( NodeInputIterator it = begin; it != end; ++it ) {
171 DAI_ASSERT( *it < nrNodes2() );
172 Neighbor nb1new( iter, *it, nb2(*it).size() );
173 Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
174 nbs1new.push_back( nb1new );
175 nb2( *it ).push_back( nb2new );
176 }
177 _nb1.push_back( nbs1new );
178 return _nb1.size() - 1;
179 }
181 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
182 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
183 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
184 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
185 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
186 * \returns Index of the added node.
187 */
188 template <typename NodeInputIterator>
189 size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
190 Neighbors nbs2new;
191 nbs2new.reserve( sizeHint );
192 size_t iter = 0;
193 for( NodeInputIterator it = begin; it != end; ++it ) {
194 DAI_ASSERT( *it < nrNodes1() );
195 Neighbor nb2new( iter, *it, nb1(*it).size() );
196 Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
197 nbs2new.push_back( nb2new );
198 nb1( *it ).push_back( nb1new );
199 }
200 _nb2.push_back( nbs2new );
201 return _nb2.size() - 1;
202 }
204 /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
205 /** If \a check == \c true, only adds the edge if it does not exist already.
206 */
207 BipartiteGraph& addEdge( size_t n1, size_t n2, bool check = true );
208 //@}
210 /// \name Erasing nodes and edges
211 //@{
212 /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
213 void eraseNode1( size_t n1 );
215 /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
216 void eraseNode2( size_t n2 );
218 /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
219 void eraseEdge( size_t n1, size_t n2 );
220 //@}
222 /// \name Queries
223 //@{
224 /// Returns number of nodes of type 1
225 size_t nrNodes1() const { return _nb1.size(); }
226 /// Returns number of nodes of type 2
227 size_t nrNodes2() const { return _nb2.size(); }
229 /// Calculates the number of edges, time complexity: O(nrNodes1())
230 size_t nrEdges() const {
231 size_t sum = 0;
232 for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
233 sum += nb1(i1).size();
234 return sum;
235 }
237 /// Returns true if the graph contains an edge between node \a n1 of type 1 and node \a n2 of type 2.
238 /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
239 */
240 bool hasEdge( size_t n1, size_t n2 ) const {
241 if( nb1(n1).size() < nb2(n2).size() ) {
242 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
243 if( nb1( n1, _n2 ) == n2 )
244 return true;
245 } else {
246 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
247 if( nb2( n2, _n1 ) == n1 )
248 return true;
249 }
250 return false;
251 }
253 /// Returns the index of a given node \a n2 of type 2 amongst the neighbors of node \a n1 of type 1
254 /** \note The time complexity is linear in the number of neighbors of \a n1
255 * \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1
256 */
257 size_t findNb1( size_t n1, size_t n2 ) {
258 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
259 if( nb1( n1, _n2 ) == n2 )
260 return _n2;
261 DAI_THROW(OBJECT_NOT_FOUND);
262 return nb1(n1).size();
263 }
265 /// Returns the index of a given node \a n1 of type 1 amongst the neighbors of node \a n2 of type 2
266 /** \note The time complexity is linear in the number of neighbors of \a n2
267 * \throw OBJECT_NOT_FOUND if \a n1 is not a neighbor of \a n2
268 */
269 size_t findNb2( size_t n1, size_t n2 ) {
270 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
271 if( nb2( n2, _n1 ) == n1 )
272 return _n1;
273 DAI_THROW(OBJECT_NOT_FOUND);
274 return nb2(n2).size();
275 }
277 /// Returns neighbors of node \a n1 of type 1 as a SmallSet<size_t>.
278 SmallSet<size_t> nb1Set( size_t n1 ) const;
280 /// Returns neighbors of node \a n2 of type 2 as a SmallSet<size_t>.
281 SmallSet<size_t> nb2Set( size_t n2 ) const;
283 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
284 /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
285 * \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
286 */
287 SmallSet<size_t> delta1( size_t n1, bool include = false ) const;
289 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
290 /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
291 * \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
292 */
293 SmallSet<size_t> delta2( size_t n2, bool include = false ) const;
295 /// Returns true if the graph is connected
296 bool isConnected() const;
298 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
299 bool isTree() const;
301 /// Comparison operator which returns true if two graphs are identical
302 /** \note Two graphs are called identical if they have the same number of nodes
303 * of both types and the same edges (i.e., \a x has an edge between nodes
304 * \a n1 and \a n2 if and only if \c *this has an edge between nodes \a n1 and \a n2).
305 */
306 bool operator==( const BipartiteGraph& x ) const {
307 if( nrNodes1() != x.nrNodes1() )
308 return false;
309 if( nrNodes2() != x.nrNodes2() )
310 return false;
311 for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
312 if( nb1(n1).size() != x.nb1(n1).size() )
313 return false;
314 foreach( const Neighbor &n2, nb1(n1) )
315 if( !x.hasEdge( n1, n2 ) )
316 return false;
317 foreach( const Neighbor &n2, x.nb1(n1) )
318 if( !hasEdge( n1, n2 ) )
319 return false;
320 }
321 return true;
322 }
324 /// Asserts internal consistency
325 void checkConsistency() const;
326 //@}
328 /// \name Input and output
329 //@{
330 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
331 void printDot( std::ostream& os ) const;
333 /// Writes this BipartiteGraph to an output stream
334 friend std::ostream& operator<<( std::ostream& os, const BipartiteGraph& g ) {
335 g.printDot( os );
336 return os;
337 }
338 //@}
339 };
342 template<typename EdgeInputIterator>
343 void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
344 _nb1.clear();
345 _nb1.resize( nrNodes1 );
346 _nb2.clear();
347 _nb2.resize( nrNodes2 );
349 for( EdgeInputIterator e = begin; e != end; e++ )
350 addEdge( e->first, e->second, check );
351 }
354 } // end of namespace dai
357 /** \example example_bipgraph.cpp
358 * This example deals with the following bipartite graph:
359 * \dot
360 * graph example {
361 * ordering=out;
362 * subgraph cluster_type1 {
363 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
364 * 12 [label="2"];
365 * 11 [label="1"];
366 * 10 [label="0"];
367 * }
368 * subgraph cluster_type2 {
369 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
370 * 21 [label="1"];
371 * 20 [label="0"];
372 * }
373 * 10 -- 20;
374 * 11 -- 20;
375 * 12 -- 20;
376 * 11 -- 21;
377 * 12 -- 21;
378 * }
379 * \enddot
380 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
381 * 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).
382 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
383 * how to iterate over nodes and their neighbors.
384 *
385 * \section Output
386 * \verbinclude examples/example_bipgraph.out
387 *
388 * \section Source
389 */
392 #endif