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
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
20 */
23 /// \file
24 /// \brief Defines BipartiteGraph class
27 #ifndef __defined_libdai_bipgraph_h
28 #define __defined_libdai_bipgraph_h
31 #include <ostream>
32 #include <vector>
33 #include <cassert>
34 #include <algorithm>
35 #include <dai/util.h>
38 namespace dai {
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).
47 *
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 */
56 class BipartiteGraph {
57 public:
58 /// Describes a neighboring node of some other node in a BipartiteGraph.
59 /** A Neighbor structure has three members: \a iter, \a node and \a dual. The \a
60 * node member is the most important member: it contains the index of the neighboring node. The \a iter
61 * member is useful for iterating over neighbors, and contains the index of this Neighbor entry in the
62 * corresponding BipartiteGraph::Neighbors variable. The \a dual member is useful to find the dual Neighbor
63 * element: a pair of neighboring nodes can be either specified as a node of type 1 and a neighbor of type
64 * 2, or as a node of type 2 and a neighbor of type 1; the \a dual member contains the index of the dual
65 * Neighbor element (see the example for another explanation of the dual member).
66 */
67 struct Neighbor {
68 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
69 size_t iter;
70 /// Contains the number of the neighboring node
71 size_t node;
72 /// Contains the "dual" iter
73 size_t dual;
75 /// Default constructor
76 Neighbor() {}
77 /// Constructor that sets the Neighbor members according to the parameters
78 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
80 /// Cast to size_t returns node member
81 operator size_t () const { return node; }
82 };
84 /// Describes the neighbors of some node.
85 typedef std::vector<Neighbor> Neighbors;
87 /// 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.
88 typedef std::pair<size_t,size_t> Edge;
90 private:
91 /// Contains for each node of type 1 a vector of its neighbors
92 std::vector<Neighbors> _nb1;
94 /// Contains for each node of type 2 a vector of its neighbors
95 std::vector<Neighbors> _nb2;
97 /// Used internally by isTree()
98 struct levelType {
99 std::vector<size_t> ind1; // indices of nodes of type 1
100 std::vector<size_t> ind2; // indices of nodes of type 2
101 };
103 public:
104 /// Default constructor (creates an empty bipartite graph)
105 BipartiteGraph() : _nb1(), _nb2() {}
107 /// Copy constructor (constructs a bipartite graph containing a copy of \c x)
108 BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
110 /// Assignment operator (makes \c *this equal to \c x)
111 BipartiteGraph & operator=( const BipartiteGraph & x ) {
112 if( this != &x ) {
113 _nb1 = x._nb1;
114 _nb2 = x._nb2;
115 }
116 return *this;
117 }
119 /// Constructs BipartiteGraph from a range of edges.
120 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
121 * \param nr1 The number of nodes of type 1.
122 * \param nr2 The number of nodes of type 2.
123 * \param begin Points to the first edge.
124 * \param end Points just beyond the last edge.
125 */
126 template<typename EdgeInputIterator>
127 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
128 construct( nr1, nr2, begin, end );
129 }
131 /// (Re)constructs BipartiteGraph from a range of edges.
132 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
133 * \param nr1 The number of nodes of type 1.
134 * \param nr2 The number of nodes of type 2.
135 * \param begin Points to the first edge.
136 * \param end Points just beyond the last edge.
137 */
138 template<typename EdgeInputIterator>
139 void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
141 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
142 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
143 #ifdef DAI_DEBUG
144 assert( i1 < _nb1.size() );
145 assert( _i2 < _nb1[i1].size() );
146 #endif
147 return _nb1[i1][_i2];
148 }
149 /// Returns reference to the _i2'th neighbor of node i1 of type 1
150 Neighbor & nb1( size_t i1, size_t _i2 ) {
151 #ifdef DAI_DEBUG
152 assert( i1 < _nb1.size() );
153 assert( _i2 < _nb1[i1].size() );
154 #endif
155 return _nb1[i1][_i2];
156 }
158 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
159 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
160 #ifdef DAI_DEBUG
161 assert( i2 < _nb2.size() );
162 assert( _i1 < _nb2[i2].size() );
163 #endif
164 return _nb2[i2][_i1];
165 }
166 /// Returns reference to the _i1'th neighbor of node i2 of type 2
167 Neighbor & nb2( size_t i2, size_t _i1 ) {
168 #ifdef DAI_DEBUG
169 assert( i2 < _nb2.size() );
170 assert( _i1 < _nb2[i2].size() );
171 #endif
172 return _nb2[i2][_i1];
173 }
175 /// Returns constant reference to all neighbors of node i1 of type 1
176 const Neighbors & nb1( size_t i1 ) const {
177 #ifdef DAI_DEBUG
178 assert( i1 < _nb1.size() );
179 #endif
180 return _nb1[i1];
181 }
182 /// Returns reference to all neighbors of node of i1 type 1
183 Neighbors & nb1( size_t i1 ) {
184 #ifdef DAI_DEBUG
185 assert( i1 < _nb1.size() );
186 #endif
187 return _nb1[i1];
188 }
190 /// Returns constant reference to all neighbors of node i2 of type 2
191 const Neighbors & nb2( size_t i2 ) const {
192 #ifdef DAI_DEBUG
193 assert( i2 < _nb2.size() );
194 #endif
195 return _nb2[i2];
196 }
197 /// Returns reference to all neighbors of node i2 of type 2
198 Neighbors & nb2( size_t i2 ) {
199 #ifdef DAI_DEBUG
200 assert( i2 < _nb2.size() );
201 #endif
202 return _nb2[i2];
203 }
205 /// Returns number of nodes of type 1
206 size_t nr1() const { return _nb1.size(); }
207 /// Returns number of nodes of type 2
208 size_t nr2() const { return _nb2.size(); }
210 /// Calculates the number of edges, time complexity: O(nr1())
211 size_t nrEdges() const {
212 size_t sum = 0;
213 for( size_t i1 = 0; i1 < nr1(); i1++ )
214 sum += nb1(i1).size();
215 return sum;
216 }
218 /// Adds a node of type 1 without neighbors.
219 void add1() { _nb1.push_back( Neighbors() ); }
221 /// Adds a node of type 2 without neighbors.
222 void add2() { _nb2.push_back( Neighbors() ); }
224 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
225 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
226 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
227 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
228 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
229 */
230 template <typename NodeInputIterator>
231 void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
232 Neighbors nbs1new;
233 nbs1new.reserve( sizeHint );
234 size_t iter = 0;
235 for( NodeInputIterator it = begin; it != end; ++it ) {
236 assert( *it < nr2() );
237 Neighbor nb1new( iter, *it, nb2(*it).size() );
238 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
239 nbs1new.push_back( nb1new );
240 nb2( *it ).push_back( nb2new );
241 }
242 _nb1.push_back( nbs1new );
243 }
245 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
246 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
247 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
248 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
249 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
250 */
251 template <typename NodeInputIterator>
252 void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
253 Neighbors nbs2new;
254 nbs2new.reserve( sizeHint );
255 size_t iter = 0;
256 for( NodeInputIterator it = begin; it != end; ++it ) {
257 assert( *it < nr1() );
258 Neighbor nb2new( iter, *it, nb1(*it).size() );
259 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
260 nbs2new.push_back( nb2new );
261 nb1( *it ).push_back( nb1new );
262 }
263 _nb2.push_back( nbs2new );
264 }
266 /// Removes node n1 of type 1 and all incident edges.
267 void erase1( size_t n1 );
269 /// Removes node n2 of type 2 and all incident edges.
270 void erase2( size_t n2 );
272 /// Adds an edge between node n1 of type 1 and node n2 of type 2.
273 /** If check == true, only adds the edge if it does not exist already.
274 */
275 void addEdge( size_t n1, size_t n2, bool check = true ) {
276 assert( n1 < nr1() );
277 assert( n2 < nr2() );
278 bool exists = false;
279 if( check ) {
280 // Check whether the edge already exists
281 foreach( const Neighbor &nb2, nb1(n1) )
282 if( nb2 == n2 ) {
283 exists = true;
284 break;
285 }
286 }
287 if( !exists ) { // Add edge
288 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
289 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
290 _nb1[n1].push_back( nb_1 );
291 _nb2[n2].push_back( nb_2 );
292 }
293 }
295 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
296 /** If include == true, includes n1 itself, otherwise excludes n1.
297 */
298 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
300 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
301 /** If include == true, includes n2 itself, otherwise excludes n2.
302 */
303 std::vector<size_t> delta2( size_t n2, bool include = false ) const;
305 /// Returns true if the graph is connected
306 bool isConnected() const;
308 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
309 bool isTree() const;
311 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
312 void printDot( std::ostream& os ) const;
314 private:
315 /// Checks internal consistency
316 void check() const;
317 };
320 template<typename EdgeInputIterator>
321 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
322 _nb1.clear();
323 _nb1.resize( nr1 );
324 _nb2.clear();
325 _nb2.resize( nr2 );
327 for( EdgeInputIterator e = begin; e != end; e++ ) {
328 #ifdef DAI_DEBUG
329 addEdge( e->first, e->second, true );
330 #else
331 addEdge( e->first, e->second, false );
332 #endif
333 }
334 }
337 } // end of namespace dai
340 /** \example example_bipgraph.cpp
341 * This example deals with the following bipartite graph:
342 * \dot
343 * graph example {
344 * ordering=out;
345 * subgraph cluster_type1 {
346 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
347 * 12 [label="2"];
348 * 11 [label="1"];
349 * 10 [label="0"];
350 * }
351 * subgraph cluster_type2 {
352 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
353 * 21 [label="1"];
354 * 20 [label="0"];
355 * }
356 * 10 -- 20;
357 * 11 -- 20;
358 * 12 -- 20;
359 * 11 -- 21;
360 * 12 -- 21;
361 * }
362 * \enddot
363 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
364 * 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).
365 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
366 * how to iterate over nodes and their neighbors.
367 *
368 * \section Output
369 * \verbinclude examples/example_bipgraph.out
370 *
371 * \section Source
372 */
375 #endif