569f815a802a0301abcc447ac1547811180b71ea
[libdai.git] / include / dai / bipgraph.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4 *
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6 */
7
8
9 /// \file
10 /// \brief Defines the BipartiteGraph class, which represents a bipartite graph
11
12
13 #ifndef __defined_libdai_bipgraph_h
14 #define __defined_libdai_bipgraph_h
15
16
17 #include <ostream>
18 #include <vector>
19 #include <algorithm>
20 #include <dai/util.h>
21 #include <dai/smallset.h>
22 #include <dai/exceptions.h>
23 #include <dai/graph.h>
24
25
26 namespace dai {
27
28
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).
35 *
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.
44 */
45 class BipartiteGraph {
46 private:
47 /// Contains for each node of type 1 a vector of its neighbors
48 std::vector<Neighbors> _nb1;
49
50 /// Contains for each node of type 2 a vector of its neighbors
51 std::vector<Neighbors> _nb2;
52
53 /// Used internally by isTree()
54 struct levelType {
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;
59 };
60
61 public:
62 /// \name Constructors and destructors
63 //@{
64 /// Default constructor (creates an empty bipartite graph)
65 BipartiteGraph() : _nb1(), _nb2() {}
66
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) {}
69
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.
77 */
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 );
81 }
82 //@}
83
84 /// \name Accessors and mutators
85 //@{
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() );
90 return _nb1[i1][_i2];
91 }
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() );
96 return _nb1[i1][_i2];
97 }
98
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];
104 }
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];
110 }
111
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() );
115 return _nb1[i1];
116 }
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() );
120 return _nb1[i1];
121 }
122
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() );
126 return _nb2[i2];
127 }
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() );
131 return _nb2[i2];
132 }
133 //@}
134
135 /// \name Adding nodes and edges
136 //@{
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.
144 */
145 template<typename EdgeInputIterator>
146 void construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true );
147
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; }
150
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; }
153
154
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.
161 */
162 template <typename NodeInputIterator>
163 size_t addNode1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
164 Neighbors nbs1new;
165 nbs1new.reserve( sizeHint );
166 size_t iter = 0;
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 );
173 }
174 _nb1.push_back( nbs1new );
175 return _nb1.size() - 1;
176 }
177
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.
184 */
185 template <typename NodeInputIterator>
186 size_t addNode2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
187 Neighbors nbs2new;
188 nbs2new.reserve( sizeHint );
189 size_t iter = 0;
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 );
196 }
197 _nb2.push_back( nbs2new );
198 return _nb2.size() - 1;
199 }
200
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.
203 */
204 BipartiteGraph& addEdge( size_t n1, size_t n2, bool check = true );
205 //@}
206
207 /// \name Erasing nodes and edges
208 //@{
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 );
211
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 );
214
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 );
217 //@}
218
219 /// \name Queries
220 //@{
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(); }
225
226 /// Calculates the number of edges, time complexity: O(nrNodes1())
227 size_t nrEdges() const {
228 size_t sum = 0;
229 for( size_t i1 = 0; i1 < nrNodes1(); i1++ )
230 sum += nb1(i1).size();
231 return sum;
232 }
233
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
236 */
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 )
241 return true;
242 } else {
243 for( size_t _n1 = 0; _n1 < nb2(n2).size(); _n1++ )
244 if( nb2( n2, _n1 ) == n1 )
245 return true;
246 }
247 return false;
248 }
249
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
253 */
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 )
257 return _n2;
258 DAI_THROW(OBJECT_NOT_FOUND);
259 return nb1(n1).size();
260 }
261
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
265 */
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 )
269 return _n1;
270 DAI_THROW(OBJECT_NOT_FOUND);
271 return nb2(n2).size();
272 }
273
274 /// Returns neighbors of node \a n1 of type 1 as a SmallSet<size_t>.
275 SmallSet<size_t> nb1Set( size_t n1 ) const;
276
277 /// Returns neighbors of node \a n2 of type 2 as a SmallSet<size_t>.
278 SmallSet<size_t> nb2Set( size_t n2 ) const;
279
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>
283 */
284 SmallSet<size_t> delta1( size_t n1, bool include = false ) const;
285
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>
289 */
290 SmallSet<size_t> delta2( size_t n2, bool include = false ) const;
291
292 /// Returns true if the graph is connected
293 bool isConnected() const;
294
295 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
296 bool isTree() const;
297
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).
302 */
303 bool operator==( const BipartiteGraph& x ) const {
304 if( nrNodes1() != x.nrNodes1() )
305 return false;
306 if( nrNodes2() != x.nrNodes2() )
307 return false;
308 for( size_t n1 = 0; n1 < nrNodes1(); n1++ ) {
309 if( nb1(n1).size() != x.nb1(n1).size() )
310 return false;
311 bforeach( const Neighbor &n2, nb1(n1) )
312 if( !x.hasEdge( n1, n2 ) )
313 return false;
314 bforeach( const Neighbor &n2, x.nb1(n1) )
315 if( !hasEdge( n1, n2 ) )
316 return false;
317 }
318 return true;
319 }
320
321 /// Asserts internal consistency
322 void checkConsistency() const;
323 //@}
324
325 /// \name Input and output
326 //@{
327 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
328 void printDot( std::ostream& os ) const;
329
330 /// Writes this BipartiteGraph to an output stream
331 friend std::ostream& operator<<( std::ostream& os, const BipartiteGraph& g ) {
332 g.printDot( os );
333 return os;
334 }
335 //@}
336 };
337
338
339 template<typename EdgeInputIterator>
340 void BipartiteGraph::construct( size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check ) {
341 _nb1.clear();
342 _nb1.resize( nrNodes1 );
343 _nb2.clear();
344 _nb2.resize( nrNodes2 );
345
346 for( EdgeInputIterator e = begin; e != end; e++ )
347 addEdge( e->first, e->second, check );
348 }
349
350
351 } // end of namespace dai
352
353
354 /** \example example_bipgraph.cpp
355 * This example deals with the following bipartite graph:
356 * \dot
357 * graph example {
358 * ordering=out;
359 * subgraph cluster_type1 {
360 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
361 * 12 [label="2"];
362 * 11 [label="1"];
363 * 10 [label="0"];
364 * }
365 * subgraph cluster_type2 {
366 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
367 * 21 [label="1"];
368 * 20 [label="0"];
369 * }
370 * 10 -- 20;
371 * 11 -- 20;
372 * 12 -- 20;
373 * 11 -- 21;
374 * 12 -- 21;
375 * }
376 * \enddot
377 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
378 * 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).
379 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
380 * how to iterate over nodes and their neighbors.
381 *
382 * \section Output
383 * \verbinclude examples/example_bipgraph.out
384 *
385 * \section Source
386 */
387
388
389 #endif