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