999e5d3d0b34b5e7abbab676c9ec58b4584558ef
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 /// Describes the neighbor relationship of two nodes in a BipartiteGraph.
51 */
52 typedef dai::Neighbor Neighbor;
54 /// Describes the neighbors of some node.
56 */
57 typedef dai::Neighbors Neighbors;
59 /// 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.
61 */
62 typedef dai::Edge Edge;
64 private:
65 /// Contains for each node of type 1 a vector of its neighbors
66 std::vector<Neighbors> _nb1;
68 /// Contains for each node of type 2 a vector of its neighbors
69 std::vector<Neighbors> _nb2;
71 /// Used internally by isTree()
72 struct levelType {
73 /// Indices of nodes of type 1
74 std::vector<size_t> ind1;
75 /// Indices of nodes of type 2
76 std::vector<size_t> ind2;
77 };
79 public:
80 /// \name Constructors and destructors
81 //@{
82 /// Default constructor (creates an empty bipartite graph)
83 BipartiteGraph() : _nb1(), _nb2() {}
85 /// Constructs BipartiteGraph with \a nr1 nodes of type 1, \a nr2 nodes of type 2 and no edges.
86 BipartiteGraph( size_t nr1, size_t nr2 ) : _nb1(nr1), _nb2(nr2) {}
88 /// Constructs BipartiteGraph from a range of edges.
89 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
90 * \param nrNodes1 The number of nodes of type 1.
91 * \param nrNodes2 The number of nodes of type 2.
92 * \param begin Points to the first edge.
93 * \param end Points just beyond the last edge.
94 * \param check Whether to only add an edge if it does not exist already.
95 */
96 template<typename EdgeInputIterator>
97 BipartiteGraph( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true ) : _nb1(), _nb2() {
98 construct( nrNodes1, nrNodes2, begin, end, check );
99 }
100 //@}
102 /// \name Accessors and mutators
103 //@{
104 /// Returns constant reference to the \a _i2 'th neighbor of node \a i1 of type 1
105 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
106 DAI_DEBASSERT( i1 < _nb1.size() );
107 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
108 return _nb1[i1][_i2];
109 }
110 /// Returns reference to the \a _i2 'th neighbor of node \a i1 of type 1
111 Neighbor & nb1( size_t i1, size_t _i2 ) {
112 DAI_DEBASSERT( i1 < _nb1.size() );
113 DAI_DEBASSERT( _i2 < _nb1[i1].size() );
114 return _nb1[i1][_i2];
115 }
117 /// Returns constant reference to the \a _i1 'th neighbor of node \a i2 of type 2
118 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
119 DAI_DEBASSERT( i2 < _nb2.size() );
120 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
121 return _nb2[i2][_i1];
122 }
123 /// Returns reference to the \a _i1 'th neighbor of node \a i2 of type 2
124 Neighbor & nb2( size_t i2, size_t _i1 ) {
125 DAI_DEBASSERT( i2 < _nb2.size() );
126 DAI_DEBASSERT( _i1 < _nb2[i2].size() );
127 return _nb2[i2][_i1];
128 }
130 /// Returns constant reference to all neighbors of node \a i1 of type 1
131 const Neighbors & nb1( size_t i1 ) const {
132 DAI_DEBASSERT( i1 < _nb1.size() );
133 return _nb1[i1];
134 }
135 /// Returns reference to all neighbors of node \a i1 of type 1
136 Neighbors & nb1( size_t i1 ) {
137 DAI_DEBASSERT( i1 < _nb1.size() );
138 return _nb1[i1];
139 }
141 /// Returns constant reference to all neighbors of node \a i2 of type 2
142 const Neighbors & nb2( size_t i2 ) const {
143 DAI_DEBASSERT( i2 < _nb2.size() );
144 return _nb2[i2];
145 }
146 /// Returns reference to all neighbors of node \a i2 of type 2
147 Neighbors & nb2( size_t i2 ) {
148 DAI_DEBASSERT( i2 < _nb2.size() );
149 return _nb2[i2];
150 }
151 //@}
153 /// \name Adding nodes and edges
154 //@{
155 /// (Re)constructs BipartiteGraph from a range of edges.
156 /** \tparam EdgeInputIterator Iterator that iterates over instances of Edge.
157 * \param nrNodes1 The number of nodes of type 1.
158 * \param nrNodes2 The number of nodes of type 2.
159 * \param begin Points to the first edge.
160 * \param end Points just beyond the last edge.
161 * \param check Whether to only add an edge if it does not exist already.
162 */
163 template<typename EdgeInputIterator>
164 void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
166 /// Adds a node of type 1 without neighbors and returns the index of the added node.
167 size_t addNode1() { _nb1.push_back( Neighbors() ); return _nb1.size() - 1; }
169 /// Adds a node of type 2 without neighbors and returns the index of the added node.
170 size_t addNode2() { _nb2.push_back( Neighbors() ); return _nb2.size() - 1; }
173 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
174 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
175 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
176 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
177 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
178 * \returns Index of the added node.
179 */
180 template <typename NodeInputIterator>
181 size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
182 Neighbors nbs1new;
183 nbs1new.reserve( sizeHint );
184 size_t iter = 0;
185 for( NodeInputIterator it = begin; it != end; ++it ) {
186 DAI_ASSERT( *it < nrNodes2() );
187 Neighbor nb1new( iter, *it, nb2(*it).size() );
188 Neighbor nb2new( nb2(*it).size(), nrNodes1(), iter++ );
189 nbs1new.push_back( nb1new );
190 nb2( *it ).push_back( nb2new );
191 }
192 _nb1.push_back( nbs1new );
193 return _nb1.size() - 1;
194 }
196 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
197 /** \tparam NodeInputIterator Iterator that iterates over instances of \c size_t.
198 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
199 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
200 * \param sizeHint For improved efficiency, the size of the range may be specified by \a sizeHint.
201 * \returns Index of the added node.
202 */
203 template <typename NodeInputIterator>
204 size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
205 Neighbors nbs2new;
206 nbs2new.reserve( sizeHint );
207 size_t iter = 0;
208 for( NodeInputIterator it = begin; it != end; ++it ) {
209 DAI_ASSERT( *it < nrNodes1() );
210 Neighbor nb2new( iter, *it, nb1(*it).size() );
211 Neighbor nb1new( nb1(*it).size(), nrNodes2(), iter++ );
212 nbs2new.push_back( nb2new );
213 nb1( *it ).push_back( nb1new );
214 }
215 _nb2.push_back( nbs2new );
216 return _nb2.size() - 1;
217 }
219 /// Adds an edge between node \a n1 of type 1 and node \a n2 of type 2.
220 /** If \a check == \c true, only adds the edge if it does not exist already.
221 */
222 BipartiteGraph& addEdge( size_t n1, size_t n2, bool check = true );
223 //@}
225 /// \name Erasing nodes and edges
226 //@{
227 /// Removes node \a n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
228 void eraseNode1( size_t n1 );
230 /// Removes node \a n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
231 void eraseNode2( size_t n2 );
233 /// Removes edge between node \a n1 of type 1 and node \a n2 of type 2.
234 void eraseEdge( size_t n1, size_t n2 );
235 //@}
237 /// \name Queries
238 //@{
239 /// Returns number of nodes of type 1
240 size_t nrNodes1() const { return _nb1.size(); }
241 /// Returns number of nodes of type 2
242 size_t nrNodes2() const { return _nb2.size(); }
244 /// Calculates the number of edges, time complexity: O(nrNodes1())
245 size_t nrEdges() const {
246 size_t sum = 0;
247 for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
248 sum += nb1(i1).size();
249 return sum;
250 }
252 /// Returns true if the graph contains an edge between node \a n1 of type 1 and node \a n2 of type 2.
253 /** \note The time complexity is linear in the number of neighbors of \a n1 or \a n2
254 */
255 bool hasEdge( size_t n1, size_t n2 ) const {
256 if( nb1(n1).size() < nb2(n2).size() ) {
257 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
258 if( nb1( n1, _n2 ) == n2 )
259 return true;
260 } else {
261 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
262 if( nb2( n2, _n1 ) == n1 )
263 return true;
264 }
265 return false;
266 }
268 /// Returns the index of a given node \a n2 of type 2 amongst the neighbors of node \a n1 of type 1
269 /** \note The time complexity is linear in the number of neighbors of \a n1
270 * \throw OBJECT_NOT_FOUND if \a n2 is not a neighbor of \a n1
271 */
272 size_t findNb1( size_t n1, size_t n2 ) {
273 for( size_t _n2 = 0; _n2 < nb1(n1).size(); _n2++ )
274 if( nb1( n1, _n2 ) == n2 )
275 return _n2;
276 DAI_THROW(OBJECT_NOT_FOUND);
277 return nb1(n1).size();
278 }
280 /// Returns the index of a given node \a n1 of type 1 amongst the neighbors of node \a n2 of type 2
281 /** \note The time complexity is linear in the number of neighbors of \a n2
282 * \throw OBJECT_NOT_FOUND if \a n1 is not a neighbor of \a n2
283 */
284 size_t findNb2( size_t n1, size_t n2 ) {
285 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
286 if( nb2( n2, _n1 ) == n1 )
287 return _n1;
288 DAI_THROW(OBJECT_NOT_FOUND);
289 return nb2(n2).size();
290 }
292 /// Returns neighbors of node \a n1 of type 1 as a SmallSet<size_t>.
293 SmallSet<size_t> nb1Set( size_t n1 ) const;
295 /// Returns neighbors of node \a n2 of type 2 as a SmallSet<size_t>.
296 SmallSet<size_t> nb2Set( size_t n2 ) const;
298 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n1 of type 1.
299 /** If \a include == \c true, includes \a n1 itself, otherwise excludes \a n1.
300 * \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
301 */
302 SmallSet<size_t> delta1( size_t n1, bool include = false ) const;
304 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node \a n2 of type 2.
305 /** If \a include == \c true, includes \a n2 itself, otherwise excludes \a n2.
306 * \note In libDAI versions 0.2.4 and earlier, this function used to return a std::vector<size_t>
307 */
308 SmallSet<size_t> delta2( size_t n2, bool include = false ) const;
310 /// Returns true if the graph is connected
311 bool isConnected() const;
313 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
314 bool isTree() const;
316 /// Comparison operator which returns true if two graphs are identical
317 /** \note Two graphs are called identical if they have the same number of nodes
318 * of both types and the same edges (i.e., \a x has an edge between nodes
319 * \a n1 and \a n2 if and only if \c *this has an edge between nodes \a n1 and \a n2).
320 */
321 bool operator==( const BipartiteGraph& x ) const {
322 if( nrNodes1() != x.nrNodes1() )
323 return false;
324 if( nrNodes2() != x.nrNodes2() )
325 return false;
326 for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
327 if( nb1(n1).size() != x.nb1(n1).size() )
328 return false;
329 foreach( const Neighbor &n2, nb1(n1) )
330 if( !x.hasEdge( n1, n2 ) )
331 return false;
332 foreach( const Neighbor &n2, x.nb1(n1) )
333 if( !hasEdge( n1, n2 ) )
334 return false;
335 }
336 return true;
337 }
339 /// Asserts internal consistency
340 void checkConsistency() const;
341 //@}
343 /// \name Input and output
344 //@{
345 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
346 void printDot( std::ostream& os ) const;
348 /// Writes this BipartiteGraph to an output stream
349 friend std::ostream& operator<<( std::ostream& os, const BipartiteGraph& g ) {
350 g.printDot( os );
351 return os;
352 }
353 //@}
354 };
357 template<typename EdgeInputIterator>
358 void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
359 _nb1.clear();
360 _nb1.resize( nrNodes1 );
361 _nb2.clear();
362 _nb2.resize( nrNodes2 );
364 for( EdgeInputIterator e = begin; e != end; e++ )
365 addEdge( e->first, e->second, check );
366 }
369 } // end of namespace dai
372 /** \example example_bipgraph.cpp
373 * This example deals with the following bipartite graph:
374 * \dot
375 * graph example {
376 * ordering=out;
377 * subgraph cluster_type1 {
378 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
379 * 12 [label="2"];
380 * 11 [label="1"];
381 * 10 [label="0"];
382 * }
383 * subgraph cluster_type2 {
384 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
385 * 21 [label="1"];
386 * 20 [label="0"];
387 * }
388 * 10 -- 20;
389 * 11 -- 20;
390 * 12 -- 20;
391 * 11 -- 21;
392 * 12 -- 21;
393 * }
394 * \enddot
395 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
396 * 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).
397 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
398 * how to iterate over nodes and their neighbors.
399 *
400 * \section Output
401 * \verbinclude examples/example_bipgraph.out
402 *
403 * \section Source
404 */
407 #endif