Merge branch 'master' of git@git.tuebingen.mpg.de:libdai
[libdai.git] / include / dai / bipgraph.h
1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
3
4 This file is part of libDAI.
5
6 libDAI is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 libDAI is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with libDAI; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21
22 #ifndef __defined_libdai_bipgraph_h
23 #define __defined_libdai_bipgraph_h
24
25
26 #include <ostream>
27 #include <vector>
28 #include <cassert>
29 #include <algorithm>
30 #include <dai/util.h>
31
32
33 namespace dai {
34
35
36 /// A BipartiteGraph represents the neighborhood structure of nodes in a bipartite graph.
37 /** A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between
38 * nodes of different type. Nodes are indexed by an unsigned integer, edges are indexed as
39 * a pair of unsigned integers (where the pair (a,b) means the b'th neighbor of the a'th node).
40 * The BipartiteGraph stores neighborhood structures as vectors of vectors of Neighbor entries.
41 */
42 class BipartiteGraph {
43 public:
44 /// A Neighbor describes a neighboring node of some other node.
45 /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
46 * \code
47 * foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
48 * size_t _n2 = n2.iter;
49 * size_t _n1 = n2.dual;
50 * // n2 == n2.node;
51 * // The _n2'th neighbor of n1 is n2, and the _n1'th neighbor of n2 is n1:
52 * // nb1(n1)[_n2] == n2, nb2(n2)[_n1] == n1
53 * }
54 * \endcode
55 */
56 struct Neighbor {
57 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
58 unsigned iter;
59 /// Contains the number of the neighboring node
60 unsigned node;
61 /// Contains the "dual" iter
62 unsigned dual;
63 /// Cast to unsigned returns node
64 operator unsigned () const { return node; }
65 /// Default constructor
66 Neighbor() {}
67 /// Constructor
68 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
69 };
70
71 /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
72 typedef std::vector<Neighbor> Neighbors;
73
74 /// Edge is used as index of an edge: an Edge(a,b) corresponds to the edge between the a'th node and its b'th neighbor.
75 typedef std::pair<size_t,size_t> Edge;
76
77 private:
78 /// _nb1 contains for each node of type 1 a vector of its neighbors
79 std::vector<Neighbors> _nb1;
80 /// _nb2 contains for each node of type 2 a vector of its neighbors
81 std::vector<Neighbors> _nb2;
82
83 /// Used internally by isTree()
84 struct levelType {
85 std::vector<size_t> ind1; // indices of vertices of type 1
86 std::vector<size_t> ind2; // indices of vertices of type 2
87 };
88
89 public:
90 /// Default constructor
91 BipartiteGraph() : _nb1(), _nb2() {}
92
93 /// Copy constructor
94 BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
95
96 /// Assignment operator
97 BipartiteGraph & operator=( const BipartiteGraph & x ) {
98 if( this != &x ) {
99 _nb1 = x._nb1;
100 _nb2 = x._nb2;
101 }
102 return *this;
103 }
104
105 /// Create bipartite graph from a range of edges.
106 /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
107 * The value_type of an EdgeInputIterator should be Edge.
108 */
109 template<typename EdgeInputIterator>
110 void create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
111
112 /// Construct bipartite graph from a range of edges.
113 /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
114 * The value_type of an EdgeInputIterator should be Edge.
115 */
116 template<typename EdgeInputIterator>
117 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
118 create( nr1, nr2, begin, end );
119 }
120
121 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
122 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
123 #ifdef DAI_DEBUG
124 assert( i1 < _nb1.size() );
125 assert( _i2 < _nb1[i1].size() );
126 #endif
127 return _nb1[i1][_i2];
128 }
129 /// Returns reference to the _i2'th neighbor of node i1 of type 1
130 Neighbor & nb1( size_t i1, size_t _i2 ) {
131 #ifdef DAI_DEBUG
132 assert( i1 < _nb1.size() );
133 assert( _i2 < _nb1[i1].size() );
134 #endif
135 return _nb1[i1][_i2];
136 }
137
138 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
139 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
140 #ifdef DAI_DEBUG
141 assert( i2 < _nb2.size() );
142 assert( _i1 < _nb2[i2].size() );
143 #endif
144 return _nb2[i2][_i1];
145 }
146 /// Returns reference to the _i1'th neighbor of node i2 of type 2
147 Neighbor & nb2( size_t i2, size_t _i1 ) {
148 #ifdef DAI_DEBUG
149 assert( i2 < _nb2.size() );
150 assert( _i1 < _nb2[i2].size() );
151 #endif
152 return _nb2[i2][_i1];
153 }
154
155 /// Returns constant reference to all neighbors of node i1 of type 1
156 const Neighbors & nb1( size_t i1 ) const {
157 #ifdef DAI_DEBUG
158 assert( i1 < _nb1.size() );
159 #endif
160 return _nb1[i1];
161 }
162 /// Returns reference to all neighbors of node of i1 type 1
163 Neighbors & nb1( size_t i1 ) {
164 #ifdef DAI_DEBUG
165 assert( i1 < _nb1.size() );
166 #endif
167 return _nb1[i1];
168 }
169
170 /// Returns constant reference to all neighbors of node i2 of type 2
171 const Neighbors & nb2( size_t i2 ) const {
172 #ifdef DAI_DEBUG
173 assert( i2 < _nb2.size() );
174 #endif
175 return _nb2[i2];
176 }
177 /// Returns reference to all neighbors of node i2 of type 2
178 Neighbors & nb2( size_t i2 ) {
179 #ifdef DAI_DEBUG
180 assert( i2 < _nb2.size() );
181 #endif
182 return _nb2[i2];
183 }
184
185 /// Returns number of nodes of type 1
186 size_t nr1() const { return _nb1.size(); }
187 /// Returns number of nodes of type 2
188 size_t nr2() const { return _nb2.size(); }
189
190 /// Calculates the number of edges
191 size_t nrEdges() const {
192 size_t sum = 0;
193 for( size_t i1 = 0; i1 < nr1(); i1++ )
194 sum += nb1(i1).size();
195 return sum;
196 }
197
198 /// Add node of type 1 without neighbors.
199 void add1() { _nb1.push_back( Neighbors() ); }
200
201 /// Add node of type 2 without neighbors.
202 void add2() { _nb2.push_back( Neighbors() ); }
203
204 /// Add node of type 1 with neighbors specified by a range.
205 /** The value_type of an NodeInputIterator should be a size_t, corresponding to
206 * the indices of nodes of type 2 that should become neighbors of the added node.
207 * For improved efficiency, the size of the range may be specified by sizeHint.
208 */
209 template <typename NodeInputIterator>
210 void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
211 Neighbors nbs1new;
212 nbs1new.reserve( sizeHint );
213 size_t iter = 0;
214 for( NodeInputIterator it = begin; it != end; ++it ) {
215 assert( *it < nr2() );
216 Neighbor nb1new( iter, *it, nb2(*it).size() );
217 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
218 nbs1new.push_back( nb1new );
219 nb2( *it ).push_back( nb2new );
220 }
221 _nb1.push_back( nbs1new );
222 }
223
224 /// Add node of type 2 with neighbors specified by a range.
225 /** The value_type of an NodeInputIterator should be a size_t, corresponding to
226 * the indices of nodes of type 1 that should become neighbors of the added node.
227 * For improved efficiency, the size of the range may be specified by sizeHint.
228 */
229 template <typename NodeInputIterator>
230 void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
231 Neighbors nbs2new;
232 nbs2new.reserve( sizeHint );
233 size_t iter = 0;
234 for( NodeInputIterator it = begin; it != end; ++it ) {
235 assert( *it < nr1() );
236 Neighbor nb2new( iter, *it, nb1(*it).size() );
237 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
238 nbs2new.push_back( nb2new );
239 nb1( *it ).push_back( nb1new );
240 }
241 _nb2.push_back( nbs2new );
242 }
243
244 /// Remove node n1 of type 1 and all incident edges.
245 void erase1( size_t n1 );
246
247 /// Remove node n2 of type 2 and all incident edges.
248 void erase2( size_t n2 );
249
250 /// Add edge between node n1 of type 1 and node n2 of type 2.
251 /** If check == true, only adds the edge if it does not exist already.
252 */
253 void addEdge( size_t n1, size_t n2, bool check = true ) {
254 assert( n1 < nr1() );
255 assert( n2 < nr2() );
256 bool exists = false;
257 if( check ) {
258 // Check whether the edge already exists
259 foreach( const Neighbor &nb2, nb1(n1) )
260 if( nb2 == n2 ) {
261 exists = true;
262 break;
263 }
264 }
265 if( !exists ) { // Add edge
266 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
267 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
268 _nb1[n1].push_back( nb_1 );
269 _nb2[n2].push_back( nb_2 );
270 }
271 }
272
273 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
274 /** If include == true, include n1 itself, otherwise exclude n1.
275 */
276 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
277
278 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
279 /** If include == true, include n2 itself, otherwise exclude n2.
280 */
281 std::vector<size_t> delta2( size_t n2, bool include = false ) const;
282
283 /// Returns true if the graph is connected
284 bool isConnected() const;
285
286 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
287 /** This is equivalent to whether for each pair of vertices in the graph, there exists
288 * a unique path in the graph that starts at the first and ends at the second vertex.
289 */
290 bool isTree() const;
291
292 /// Stream to output stream os in graphviz .dot syntax
293 void display( std::ostream& os ) const;
294
295 /// Checks internal consistency
296 void check() const;
297 };
298
299
300 template<typename EdgeInputIterator>
301 void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
302 _nb1.clear();
303 _nb1.resize( nr1 );
304 _nb2.clear();
305 _nb2.resize( nr2 );
306
307 for( EdgeInputIterator e = begin; e != end; e++ ) {
308 #ifdef DAI_DEBUG
309 addEdge( e->first, e->second, true );
310 #else
311 addEdge( e->first, e->second, false );
312 #endif
313 }
314 }
315
316
317 } // end of namespace dai
318
319
320 #endif