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, edges are indexed as
44 * a pair of unsigned integers, where the pair (a,b) means the b'th neighbor of the a'th node.
45 *
46 * The BipartiteGraph stores for each node of type 1 a vector of Neighbor structures, where
47 * each Neighbor corresponds to a neighboring node of type 2. In addition, each node of type 2
48 * stores a vector of Neighbor structures describing its neighboring nodes of type 1.
49 */
50 class BipartiteGraph {
51 public:
52 /// Describes a neighboring node of some other node in a BipartiteGraph.
53 /** Iterating over all neighbors of the n1'th node of type 1 can be done in the following way:
54 * \code
55 * size_t n1 = ...;
56 * foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
57 * size_t _n2 = n2.iter;
58 * size_t _n1 = n2.dual;
59 * std::cout << "The " << _n2 << "'th neighbor of the " << n1 << "'th node of type 1 is: the " << n2 << "'th node of type 2" << endl;
60 *
61 * // The _n2'th neighbor of n1 is n2:
62 * assert( nb1(n1)[_n2] == n2 );
63 * // The _n1'th neighbor of n2 is n1:
64 * assert( nb2(n2)[_n1] == n1 );
65 * // n2 can be used as an abbreviation of n2.node:
66 * assert( static_cast<size_t>(n2) == n2.node );
67 * }
68 * \endcode
69 */
70 struct Neighbor {
71 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
72 size_t iter;
73 /// Contains the number of the neighboring node
74 size_t node;
75 /// Contains the "dual" iter
76 size_t dual;
78 /// Default constructor
79 Neighbor() {}
80 /// Constructor that sets the Neighbor members accordingly to the parameters
81 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
83 /// Cast to size_t returns member node
84 operator size_t () const { return node; }
85 };
87 /// Describes the neighbors of some node.
88 typedef std::vector<Neighbor> Neighbors;
90 /// Used as index of an edge: an Edge(a,b) corresponds to the edge between the a'th node and its b'th neighbor (it depends on the context whether the first node (with index a) is of type 1 or of type 2).
91 typedef std::pair<size_t,size_t> Edge;
93 private:
94 /// Contains for each node of type 1 a vector of its neighbors
95 std::vector<Neighbors> _nb1;
97 /// Contains for each node of type 2 a vector of its neighbors
98 std::vector<Neighbors> _nb2;
100 /// Used internally by isTree()
101 struct levelType {
102 std::vector<size_t> ind1; // indices of nodes of type 1
103 std::vector<size_t> ind2; // indices of nodes of type 2
104 };
106 public:
107 /// Default constructor
108 BipartiteGraph() : _nb1(), _nb2() {}
110 /// Copy constructor
111 BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
113 /// Assignment operator
114 BipartiteGraph & operator=( const BipartiteGraph & x ) {
115 if( this != &x ) {
116 _nb1 = x._nb1;
117 _nb2 = x._nb2;
118 }
119 return *this;
120 }
122 /// Constructs BipartiteGraph from a range of edges.
123 /** \tparam EdgeInputIterator Iterator with value_type Edge.
124 * \param nr1 The number of nodes of type 1.
125 * \param nr2 The number of nodes of type 2.
126 * \param begin Points to the first Edge.
127 * \param end Points just beyond the last Edge.
128 */
129 template<typename EdgeInputIterator>
130 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
131 construct( nr1, nr2, begin, end );
132 }
134 /// (Re)constructs BipartiteGraph from a range of edges.
135 /** \tparam EdgeInputIterator Iterator with value_type Edge.
136 * \param nr1 The number of nodes of type 1.
137 * \param nr2 The number of nodes of type 2.
138 * \param begin Points to the first Edge.
139 * \param end Points just beyond the last Edge.
140 */
141 template<typename EdgeInputIterator>
142 void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
144 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
145 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
146 #ifdef DAI_DEBUG
147 assert( i1 < _nb1.size() );
148 assert( _i2 < _nb1[i1].size() );
149 #endif
150 return _nb1[i1][_i2];
151 }
152 /// Returns reference to the _i2'th neighbor of node i1 of type 1
153 Neighbor & nb1( size_t i1, size_t _i2 ) {
154 #ifdef DAI_DEBUG
155 assert( i1 < _nb1.size() );
156 assert( _i2 < _nb1[i1].size() );
157 #endif
158 return _nb1[i1][_i2];
159 }
161 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
162 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
163 #ifdef DAI_DEBUG
164 assert( i2 < _nb2.size() );
165 assert( _i1 < _nb2[i2].size() );
166 #endif
167 return _nb2[i2][_i1];
168 }
169 /// Returns reference to the _i1'th neighbor of node i2 of type 2
170 Neighbor & nb2( size_t i2, size_t _i1 ) {
171 #ifdef DAI_DEBUG
172 assert( i2 < _nb2.size() );
173 assert( _i1 < _nb2[i2].size() );
174 #endif
175 return _nb2[i2][_i1];
176 }
178 /// Returns constant reference to all neighbors of node i1 of type 1
179 const Neighbors & nb1( size_t i1 ) const {
180 #ifdef DAI_DEBUG
181 assert( i1 < _nb1.size() );
182 #endif
183 return _nb1[i1];
184 }
185 /// Returns reference to all neighbors of node of i1 type 1
186 Neighbors & nb1( size_t i1 ) {
187 #ifdef DAI_DEBUG
188 assert( i1 < _nb1.size() );
189 #endif
190 return _nb1[i1];
191 }
193 /// Returns constant reference to all neighbors of node i2 of type 2
194 const Neighbors & nb2( size_t i2 ) const {
195 #ifdef DAI_DEBUG
196 assert( i2 < _nb2.size() );
197 #endif
198 return _nb2[i2];
199 }
200 /// Returns reference to all neighbors of node i2 of type 2
201 Neighbors & nb2( size_t i2 ) {
202 #ifdef DAI_DEBUG
203 assert( i2 < _nb2.size() );
204 #endif
205 return _nb2[i2];
206 }
208 /// Returns number of nodes of type 1
209 size_t nr1() const { return _nb1.size(); }
210 /// Returns number of nodes of type 2
211 size_t nr2() const { return _nb2.size(); }
213 /// Calculates the number of edges, using O(nr1()) time
214 size_t nrEdges() const {
215 size_t sum = 0;
216 for( size_t i1 = 0; i1 < nr1(); i1++ )
217 sum += nb1(i1).size();
218 return sum;
219 }
221 /// Adds a node of type 1 without neighbors.
222 void add1() { _nb1.push_back( Neighbors() ); }
224 /// Adds a node of type 2 without neighbors.
225 void add2() { _nb2.push_back( Neighbors() ); }
227 /// Adds a node of type 1, with neighbors specified by a range of indices of nodes of type 2.
228 /** \tparam NodeInputIterator Iterator with value_type size_t, corresponding to
229 * the indices of nodes of type 2 that should become neighbors of the added node.
230 * \param begin Points to the index of the first neighbor.
231 * \param end Points just beyond the index of the last neighbor.
232 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
233 */
234 template <typename NodeInputIterator>
235 void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
236 Neighbors nbs1new;
237 nbs1new.reserve( sizeHint );
238 size_t iter = 0;
239 for( NodeInputIterator it = begin; it != end; ++it ) {
240 assert( *it < nr2() );
241 Neighbor nb1new( iter, *it, nb2(*it).size() );
242 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
243 nbs1new.push_back( nb1new );
244 nb2( *it ).push_back( nb2new );
245 }
246 _nb1.push_back( nbs1new );
247 }
249 /// Adds a node of type 2, with neighbors specified by a range of indices of nodes of type 1.
250 /** \tparam NodeInputIterator Iterator with value_type size_t, corresponding to
251 * the indices of nodes of type 1 that should become neighbors of the added node.
252 * \param begin Points to the index of the first neighbor.
253 * \param end Points just beyond the index of the last neighbor.
254 * \param sizeHint For improved efficiency, the size of the range may be specified by sizeHint.
255 */
256 template <typename NodeInputIterator>
257 void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
258 Neighbors nbs2new;
259 nbs2new.reserve( sizeHint );
260 size_t iter = 0;
261 for( NodeInputIterator it = begin; it != end; ++it ) {
262 assert( *it < nr1() );
263 Neighbor nb2new( iter, *it, nb1(*it).size() );
264 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
265 nbs2new.push_back( nb2new );
266 nb1( *it ).push_back( nb1new );
267 }
268 _nb2.push_back( nbs2new );
269 }
271 /// Removes node n1 of type 1 and all incident edges.
272 void erase1( size_t n1 );
274 /// Removes node n2 of type 2 and all incident edges.
275 void erase2( size_t n2 );
277 /// Adds an edge between node n1 of type 1 and node n2 of type 2.
278 /** If check == true, only adds the edge if it does not exist already.
279 */
280 void addEdge( size_t n1, size_t n2, bool check = true ) {
281 assert( n1 < nr1() );
282 assert( n2 < nr2() );
283 bool exists = false;
284 if( check ) {
285 // Check whether the edge already exists
286 foreach( const Neighbor &nb2, nb1(n1) )
287 if( nb2 == n2 ) {
288 exists = true;
289 break;
290 }
291 }
292 if( !exists ) { // Add edge
293 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
294 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
295 _nb1[n1].push_back( nb_1 );
296 _nb2[n2].push_back( nb_2 );
297 }
298 }
300 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
301 /** If include == true, includes n1 itself, otherwise excludes n1.
302 */
303 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
305 /// Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
306 /** If include == true, includes n2 itself, otherwise excludes n2.
307 */
308 std::vector<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 /** This is equivalent to whether for each pair of nodes in the graph, there exists
315 * a unique path in the graph that starts at the first and ends at the second node.
316 */
317 bool isTree() const;
319 /// Writes this BipartiteGraph to an output stream in GraphViz .dot syntax
320 void printDot( std::ostream& os ) const;
322 private:
323 /// Checks internal consistency
324 void check() const;
325 };
328 template<typename EdgeInputIterator>
329 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
330 _nb1.clear();
331 _nb1.resize( nr1 );
332 _nb2.clear();
333 _nb2.resize( nr2 );
335 for( EdgeInputIterator e = begin; e != end; e++ ) {
336 #ifdef DAI_DEBUG
337 addEdge( e->first, e->second, true );
338 #else
339 addEdge( e->first, e->second, false );
340 #endif
341 }
342 }
345 } // end of namespace dai
348 #endif