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
8 it under the terms of the GNU General Public License as published by
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 * \idea Cache second-order neighborhoods in BipartiteGraph.
56 */
57 class BipartiteGraph {
58 public:
59 /// Describes a neighboring node of some other node in a BipartiteGraph.
60 /** A Neighbor structure has three members: \a iter, \a node and \a dual. The \a
61 * node member is the most important member: it contains the index of the neighboring node. The \a iter
62 * member is useful for iterating over neighbors, and contains the index of this Neighbor entry in the
63 * corresponding BipartiteGraph::Neighbors variable. The \a dual member is useful to find the dual Neighbor
64 * element: a pair of neighboring nodes can be either specified as a node of type 1 and a neighbor of type
65 * 2, or as a node of type 2 and a neighbor of type 1; the \a dual member contains the index of the dual
66 * Neighbor element (see the example for another explanation of the dual member).
67 */
68 struct Neighbor {
69 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
70 size_t iter;
71 /// Contains the number of the neighboring node
72 size_t node;
73 /// Contains the "dual" iter
74 size_t dual;
76 /// Default constructor
77 Neighbor() {}
78 /// Constructor that sets the Neighbor members according to the parameters
79 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
81 /// Cast to size_t returns node member
82 operator size_t () const { return node; }
83 };
85 /// Describes the neighbors of some node.
86 typedef std::vector<Neighbor> Neighbors;
88 /// 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.
89 typedef std::pair<size_t,size_t> Edge;
91 private:
92 /// Contains for each node of type 1 a vector of its neighbors
93 std::vector<Neighbors> _nb1;
95 /// Contains for each node of type 2 a vector of its neighbors
96 std::vector<Neighbors> _nb2;
98 /// Used internally by isTree()
99 struct levelType {
100 std::vector<size_t> ind1; // indices of nodes of type 1
101 std::vector<size_t> ind2; // indices of nodes of type 2
102 };
104 /// Support for some backwards compatibility with old interface
105 /** Call indexEdges() first to initialize these members
106 */
107 bool _edge_indexed;
108 std::vector<Edge> _edges;
109 hash_map<Edge,size_t> _vv2e;
111 public:
112 /// Default constructor (creates an empty bipartite graph)
113 BipartiteGraph() : _nb1(), _nb2(), _edge_indexed(false) {}
115 /// Constructs BipartiteGraph from a range of edges.
116 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
117 * \param nr1 The number of nodes of type 1.
118 * \param nr2 The number of nodes of type 2.
119 * \param begin Points to the first edge.
120 * \param end Points just beyond the last edge.
121 */
122 template<typename EdgeInputIterator>
123 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ), _edge_indexed(false) {
124 construct( nr1, nr2, begin, end );
125 }
127 /// (Re)constructs BipartiteGraph from a range of edges.
128 /** \tparam EdgeInputIterator Iterator that iterates over instances of BipartiteGraph::Edge.
129 * \param nr1 The number of nodes of type 1.
130 * \param nr2 The number of nodes of type 2.
131 * \param begin Points to the first edge.
132 * \param end Points just beyond the last edge.
133 */
134 template<typename EdgeInputIterator>
135 void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
137 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
138 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
139 #ifdef DAI_DEBUG
140 assert( i1 < _nb1.size() );
141 assert( _i2 < _nb1[i1].size() );
142 #endif
143 return _nb1[i1][_i2];
144 }
145 /// Returns reference to the _i2'th neighbor of node i1 of type 1
146 Neighbor & nb1( size_t i1, size_t _i2 ) {
147 #ifdef DAI_DEBUG
148 assert( i1 < _nb1.size() );
149 assert( _i2 < _nb1[i1].size() );
150 #endif
151 return _nb1[i1][_i2];
152 }
154 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
155 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
156 #ifdef DAI_DEBUG
157 assert( i2 < _nb2.size() );
158 assert( _i1 < _nb2[i2].size() );
159 #endif
160 return _nb2[i2][_i1];
161 }
162 /// Returns reference to the _i1'th neighbor of node i2 of type 2
163 Neighbor & nb2( size_t i2, size_t _i1 ) {
164 #ifdef DAI_DEBUG
165 assert( i2 < _nb2.size() );
166 assert( _i1 < _nb2[i2].size() );
167 #endif
168 return _nb2[i2][_i1];
169 }
171 /// Returns constant reference to all neighbors of node i1 of type 1
172 const Neighbors & nb1( size_t i1 ) const {
173 #ifdef DAI_DEBUG
174 assert( i1 < _nb1.size() );
175 #endif
176 return _nb1[i1];
177 }
178 /// Returns reference to all neighbors of node of i1 type 1
179 Neighbors & nb1( size_t i1 ) {
180 #ifdef DAI_DEBUG
181 assert( i1 < _nb1.size() );
182 #endif
183 return _nb1[i1];
184 }
186 /// Returns constant reference to all neighbors of node i2 of type 2
187 const Neighbors & nb2( size_t i2 ) const {
188 #ifdef DAI_DEBUG
189 assert( i2 < _nb2.size() );
190 #endif
191 return _nb2[i2];
192 }
193 /// Returns reference to all neighbors of node i2 of type 2
194 Neighbors & nb2( size_t i2 ) {
195 #ifdef DAI_DEBUG
196 assert( i2 < _nb2.size() );
197 #endif
198 return _nb2[i2];
199 }
201 /// Returns number of nodes of type 1
202 size_t nr1() const { return _nb1.size(); }
203 /// Returns number of nodes of type 2
204 size_t nr2() const { return _nb2.size(); }
206 /// Calculates the number of edges, time complexity: O(nr1())
207 size_t nrEdges() const {
208 size_t sum = 0;
209 for( size_t i1 = 0; i1 < nr1(); i1++ )
210 sum += nb1(i1).size();
211 return sum;
212 }
214 /// Adds a node of type 1 without neighbors.
215 void add1() { _nb1.push_back( Neighbors() ); }
217 /// Adds a node of type 2 without neighbors.
218 void add2() { _nb2.push_back( Neighbors() ); }
220 /// Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
221 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
222 * \param begin Points to the first index of the nodes of type 2 that should become neighbors of the added node.
223 * \param end Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node.
224 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
225 */
226 template <typename NodeInputIterator>
227 void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
228 Neighbors nbs1new;
229 nbs1new.reserve( sizeHint );
230 size_t iter = 0;
231 for( NodeInputIterator it = begin; it != end; ++it ) {
232 assert( *it < nr2() );
233 Neighbor nb1new( iter, *it, nb2(*it).size() );
234 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
235 nbs1new.push_back( nb1new );
236 nb2( *it ).push_back( nb2new );
237 }
238 _nb1.push_back( nbs1new );
239 }
241 /// Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
242 /** \tparam NodeInputIterator Iterator that iterates over instances of size_t.
243 * \param begin Points to the first index of the nodes of type 1 that should become neighbors of the added node.
244 * \param end Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node.
245 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
246 */
247 template <typename NodeInputIterator>
248 void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
249 Neighbors nbs2new;
250 nbs2new.reserve( sizeHint );
251 size_t iter = 0;
252 for( NodeInputIterator it = begin; it != end; ++it ) {
253 assert( *it < nr1() );
254 Neighbor nb2new( iter, *it, nb1(*it).size() );
255 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
256 nbs2new.push_back( nb2new );
257 nb1( *it ).push_back( nb1new );
258 }
259 _nb2.push_back( nbs2new );
260 }
262 /// Removes node n1 of type 1 and all incident edges.
263 void erase1( size_t n1 );
265 /// Removes node n2 of type 2 and all incident edges.
266 void erase2( size_t n2 );
268 /// Adds an edge between node n1 of type 1 and node n2 of type 2.
269 /** If check == true, only adds the edge if it does not exist already.
270 */
271 void addEdge( size_t n1, size_t n2, bool check = true ) {
272 assert( n1 < nr1() );
273 assert( n2 < nr2() );
274 bool exists = false;
275 if( check ) {
276 // Check whether the edge already exists
277 foreach( const Neighbor &nb2, nb1(n1) )
278 if( nb2 == n2 ) {
279 exists = true;
280 break;
281 }
282 }
283 if( !exists ) { // Add edge
284 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
285 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
286 _nb1[n1].push_back( nb_1 );
287 _nb2[n2].push_back( nb_2 );
288 }
289 }
291 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
292 /** If include == true, includes n1 itself, otherwise excludes n1.
293 */
294 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
296 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
297 /** If include == true, includes n2 itself, otherwise excludes n2.
298 */
299 std::vector<size_t> delta2( size_t n2, bool include = false ) const;
301 /// Returns true if the graph is connected
302 /** \todo Should be optimized by invoking boost::graph library
303 */
304 bool isConnected() const;
306 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
307 bool isTree() const;
309 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
310 void printDot( std::ostream& os ) const;
312 // ----------------------------------------------------------------
313 // backwards compatibility layer
314 void indexEdges() {
315 _edges.clear();
316 _vv2e.clear();
317 size_t i=0;
318 foreach(const Neighbors &nb1s, _nb1) {
319 foreach(const Neighbor &n2, nb1s) {
320 Edge e(i, n2.node);
321 _edges.push_back(e);
322 }
323 i++;
324 }
325 sort(_edges.begin(), _edges.end()); // unnecessary?
327 i=0;
328 foreach(const Edge& e, _edges) {
329 _vv2e[e] = i++;
330 }
332 _edge_indexed = true;
333 }
335 const Edge& edge(size_t e) const {
336 assert(_edge_indexed);
337 return _edges[e];
338 }
340 const std::vector<Edge>& edges() const {
341 return _edges;
342 }
344 size_t VV2E(size_t n1, size_t n2) const {
345 assert(_edge_indexed);
346 Edge e(n1,n2);
347 hash_map<Edge,size_t>::const_iterator i = _vv2e.find(e);
348 assert(i != _vv2e.end());
349 return i->second;
350 }
352 size_t nr_edges() const {
353 assert(_edge_indexed);
354 return _edges.size();
355 }
357 private:
358 /// Checks internal consistency
359 void check() const;
360 };
363 template<typename EdgeInputIterator>
364 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
365 _nb1.clear();
366 _nb1.resize( nr1 );
367 _nb2.clear();
368 _nb2.resize( nr2 );
370 for( EdgeInputIterator e = begin; e != end; e++ ) {
371 #ifdef DAI_DEBUG
372 addEdge( e->first, e->second, true );
373 #else
374 addEdge( e->first, e->second, false );
375 #endif
376 }
377 }
380 } // end of namespace dai
383 /** \example example_bipgraph.cpp
384 * This example deals with the following bipartite graph:
385 * \dot
386 * graph example {
387 * ordering=out;
388 * subgraph cluster_type1 {
389 * node[shape=circle,width=0.4,fixedsize=true,style=filled];
390 * 12 [label="2"];
391 * 11 [label="1"];
392 * 10 [label="0"];
393 * }
394 * subgraph cluster_type2 {
395 * node[shape=polygon,regular=true,sides=4,width=0.4,fixedsize=true,style=filled];
396 * 21 [label="1"];
397 * 20 [label="0"];
398 * }
399 * 10 -- 20;
400 * 11 -- 20;
401 * 12 -- 20;
402 * 11 -- 21;
403 * 12 -- 21;
404 * }
405 * \enddot
406 * It has three nodes of type 1 (drawn as circles) and two nodes of type 2 (drawn as rectangles).
407 * 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).
408 * The example code shows how to construct a BipartiteGraph object representing this bipartite graph and
409 * how to iterate over nodes and their neighbors.
410 *
411 * \section Output
412 * \verbinclude examples/example_bipgraph.out
413 *
414 * \section Source
415 */
418 #endif