Merged mf.* from SVN head (which implements damping)...
[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 * each node has a vector of Neighbor entries, which is also known as a Neighbors type.
42 */
43 class BipartiteGraph {
44 public:
45 /// A Neighbor describes a neighboring node of some other node in a BipartiteGraph.
46 /** Iterating over all neighbors of node n1 of type 1 can be done in the following way:
47 * \code
48 * foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
49 * size_t _n2 = n2.iter;
50 * size_t _n1 = n2.dual;
51 * // n2 == n2.node;
52 * // The _n2'th neighbor of n1 is n2, and the _n1'th neighbor of n2 is n1:
53 * // nb1(n1)[_n2] == n2, nb2(n2)[_n1] == n1
54 * }
55 * \endcode
56 */
57 struct Neighbor {
58 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
59 unsigned iter;
60 /// Contains the number of the neighboring node
61 unsigned node;
62 /// Contains the "dual" iter
63 unsigned dual;
64 /// Cast to unsigned returns node member
65 operator unsigned () const { return node; }
66 /// Default constructor
67 Neighbor() {}
68 /// Constructor
69 Neighbor( size_t iter, size_t node, size_t dual ) : iter(iter), node(node), dual(dual) {}
70 };
71
72 /// Neighbors is a vector of Neighbor entries; each node has an associated Neighbors variable, which describes its neighbors.
73 typedef std::vector<Neighbor> Neighbors;
74
75 /// 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. It depends on the context whether the first node (with index a) is of type 1 or of type 2.
76 typedef std::pair<size_t,size_t> Edge;
77
78 private:
79 /// _nb1 contains for each node of type 1 a vector of its neighbors
80 std::vector<Neighbors> _nb1;
81 /// _nb2 contains for each node of type 2 a vector of its neighbors
82 std::vector<Neighbors> _nb2;
83
84 /// Used internally by isTree()
85 struct levelType {
86 std::vector<size_t> ind1; // indices of vertices of type 1
87 std::vector<size_t> ind2; // indices of vertices of type 2
88 };
89
90 public:
91 /// Default constructor
92 BipartiteGraph() : _nb1(), _nb2() {}
93
94 /// Copy constructor
95 BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
96
97 /// Assignment operator
98 BipartiteGraph & operator=( const BipartiteGraph & x ) {
99 if( this != &x ) {
100 _nb1 = x._nb1;
101 _nb2 = x._nb2;
102 }
103 return *this;
104 }
105
106 /// Create bipartite graph from a range of edges.
107 /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
108 * The value_type of an EdgeInputIterator should be Edge.
109 */
110 template<typename EdgeInputIterator>
111 void construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
112
113 /// Construct bipartite graph from a range of edges.
114 /** nr1 is the number of nodes of type 1, nr2 the number of nodes of type 2.
115 * The value_type of an EdgeInputIterator should be Edge.
116 */
117 template<typename EdgeInputIterator>
118 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
119 construct( nr1, nr2, begin, end );
120 }
121
122 /// Returns constant reference to the _i2'th neighbor of node i1 of type 1
123 const Neighbor & nb1( size_t i1, size_t _i2 ) const {
124 #ifdef DAI_DEBUG
125 assert( i1 < _nb1.size() );
126 assert( _i2 < _nb1[i1].size() );
127 #endif
128 return _nb1[i1][_i2];
129 }
130 /// Returns reference to the _i2'th neighbor of node i1 of type 1
131 Neighbor & nb1( size_t i1, size_t _i2 ) {
132 #ifdef DAI_DEBUG
133 assert( i1 < _nb1.size() );
134 assert( _i2 < _nb1[i1].size() );
135 #endif
136 return _nb1[i1][_i2];
137 }
138
139 /// Returns constant reference to the _i1'th neighbor of node i2 of type 2
140 const Neighbor & nb2( size_t i2, size_t _i1 ) const {
141 #ifdef DAI_DEBUG
142 assert( i2 < _nb2.size() );
143 assert( _i1 < _nb2[i2].size() );
144 #endif
145 return _nb2[i2][_i1];
146 }
147 /// Returns reference to the _i1'th neighbor of node i2 of type 2
148 Neighbor & nb2( size_t i2, size_t _i1 ) {
149 #ifdef DAI_DEBUG
150 assert( i2 < _nb2.size() );
151 assert( _i1 < _nb2[i2].size() );
152 #endif
153 return _nb2[i2][_i1];
154 }
155
156 /// Returns constant reference to all neighbors of node i1 of type 1
157 const Neighbors & nb1( size_t i1 ) const {
158 #ifdef DAI_DEBUG
159 assert( i1 < _nb1.size() );
160 #endif
161 return _nb1[i1];
162 }
163 /// Returns reference to all neighbors of node of i1 type 1
164 Neighbors & nb1( size_t i1 ) {
165 #ifdef DAI_DEBUG
166 assert( i1 < _nb1.size() );
167 #endif
168 return _nb1[i1];
169 }
170
171 /// Returns constant reference to all neighbors of node i2 of type 2
172 const Neighbors & nb2( size_t i2 ) const {
173 #ifdef DAI_DEBUG
174 assert( i2 < _nb2.size() );
175 #endif
176 return _nb2[i2];
177 }
178 /// Returns reference to all neighbors of node i2 of type 2
179 Neighbors & nb2( size_t i2 ) {
180 #ifdef DAI_DEBUG
181 assert( i2 < _nb2.size() );
182 #endif
183 return _nb2[i2];
184 }
185
186 /// Returns number of nodes of type 1
187 size_t nr1() const { return _nb1.size(); }
188 /// Returns number of nodes of type 2
189 size_t nr2() const { return _nb2.size(); }
190
191 /// Calculates the number of edges, using O(nr1()) time
192 size_t nrEdges() const {
193 size_t sum = 0;
194 for( size_t i1 = 0; i1 < nr1(); i1++ )
195 sum += nb1(i1).size();
196 return sum;
197 }
198
199 /// Add node of type 1 without neighbors.
200 void add1() { _nb1.push_back( Neighbors() ); }
201
202 /// Add node of type 2 without neighbors.
203 void add2() { _nb2.push_back( Neighbors() ); }
204
205 /// Add node of type 1 with neighbors specified by a range.
206 /** The value_type of an NodeInputIterator should be a size_t, corresponding to
207 * the indices of nodes of type 2 that should become neighbors of the added node.
208 * For improved efficiency, the size of the range may be specified by sizeHint.
209 */
210 template <typename NodeInputIterator>
211 void add1( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
212 Neighbors nbs1new;
213 nbs1new.reserve( sizeHint );
214 size_t iter = 0;
215 for( NodeInputIterator it = begin; it != end; ++it ) {
216 assert( *it < nr2() );
217 Neighbor nb1new( iter, *it, nb2(*it).size() );
218 Neighbor nb2new( nb2(*it).size(), nr1(), iter++ );
219 nbs1new.push_back( nb1new );
220 nb2( *it ).push_back( nb2new );
221 }
222 _nb1.push_back( nbs1new );
223 }
224
225 /// Add node of type 2 with neighbors specified by a range.
226 /** The value_type of an NodeInputIterator should be a size_t, corresponding to
227 * the indices of nodes of type 1 that should become neighbors of the added node.
228 * For improved efficiency, the size of the range may be specified by sizeHint.
229 */
230 template <typename NodeInputIterator>
231 void add2( NodeInputIterator begin, NodeInputIterator end, size_t sizeHint = 0 ) {
232 Neighbors nbs2new;
233 nbs2new.reserve( sizeHint );
234 size_t iter = 0;
235 for( NodeInputIterator it = begin; it != end; ++it ) {
236 assert( *it < nr1() );
237 Neighbor nb2new( iter, *it, nb1(*it).size() );
238 Neighbor nb1new( nb1(*it).size(), nr2(), iter++ );
239 nbs2new.push_back( nb2new );
240 nb1( *it ).push_back( nb1new );
241 }
242 _nb2.push_back( nbs2new );
243 }
244
245 /// Remove node n1 of type 1 and all incident edges.
246 void erase1( size_t n1 );
247
248 /// Remove node n2 of type 2 and all incident edges.
249 void erase2( size_t n2 );
250
251 /// Add edge between node n1 of type 1 and node n2 of type 2.
252 /** If check == true, only adds the edge if it does not exist already.
253 */
254 void addEdge( size_t n1, size_t n2, bool check = true ) {
255 assert( n1 < nr1() );
256 assert( n2 < nr2() );
257 bool exists = false;
258 if( check ) {
259 // Check whether the edge already exists
260 foreach( const Neighbor &nb2, nb1(n1) )
261 if( nb2 == n2 ) {
262 exists = true;
263 break;
264 }
265 }
266 if( !exists ) { // Add edge
267 Neighbor nb_1( _nb1[n1].size(), n2, _nb2[n2].size() );
268 Neighbor nb_2( nb_1.dual, n1, nb_1.iter );
269 _nb1[n1].push_back( nb_1 );
270 _nb2[n2].push_back( nb_2 );
271 }
272 }
273
274 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
275 /** If include == true, include n1 itself, otherwise exclude n1.
276 */
277 std::vector<size_t> delta1( size_t n1, bool include = false ) const;
278
279 /// Calculate second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
280 /** If include == true, include n2 itself, otherwise exclude n2.
281 */
282 std::vector<size_t> delta2( size_t n2, bool include = false ) const;
283
284 /// Returns true if the graph is connected
285 bool isConnected() const;
286
287 /// Returns true if the graph is a tree, i.e., if it is singly connected and connected.
288 /** This is equivalent to whether for each pair of vertices in the graph, there exists
289 * a unique path in the graph that starts at the first and ends at the second vertex.
290 */
291 bool isTree() const;
292
293 /// Stream to output stream os in graphviz .dot syntax
294 void printDot( std::ostream& os ) const;
295
296 /// Checks internal consistency
297 void check() const;
298 };
299
300
301 template<typename EdgeInputIterator>
302 void BipartiteGraph::construct( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
303 _nb1.clear();
304 _nb1.resize( nr1 );
305 _nb2.clear();
306 _nb2.resize( nr2 );
307
308 for( EdgeInputIterator e = begin; e != end; e++ ) {
309 #ifdef DAI_DEBUG
310 addEdge( e->first, e->second, true );
311 #else
312 addEdge( e->first, e->second, false );
313 #endif
314 }
315 }
316
317
318 } // end of namespace dai
319
320
321 #endif