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
23 #ifndef __defined_libdai_bipgraph_h
24 #define __defined_libdai_bipgraph_h
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.
44 class BipartiteGraph
{
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:
49 * foreach( const BipartiteGraph::Neighbor &n2, nb1(n1) ) {
50 * size_t _n2 = n2.iter;
51 * size_t _n1 = n2.dual;
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
59 /// Corresponds to the index of this Neighbor entry in the vector of neighbors
61 /// Contains the number of the neighboring node
63 /// Contains the "dual" iter
65 /// Cast to unsigned returns node member
66 operator unsigned () const { return node
; }
67 /// Default constructor
70 Neighbor( size_t iter
, size_t node
, size_t dual
) : iter(iter
), node(node
), dual(dual
) {}
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
;
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()
87 std::vector
<size_t> ind1
; // indices of vertices of type 1
88 std::vector
<size_t> ind2
; // indices of vertices of type 2
92 /// Default constructor
93 BipartiteGraph() : _nb1(), _nb2() {}
96 BipartiteGraph( const BipartiteGraph
& x
) : _nb1(x
._nb1
), _nb2(x
._nb2
) {}
98 /// Assignment operator
99 BipartiteGraph
& operator=( const BipartiteGraph
& x
) {
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.
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.
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
);
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 {
126 assert( i1
< _nb1
.size() );
127 assert( _i2
< _nb1
[i1
].size() );
129 return _nb1
[i1
][_i2
];
131 /// Returns reference to the _i2'th neighbor of node i1 of type 1
132 Neighbor
& nb1( size_t i1
, size_t _i2
) {
134 assert( i1
< _nb1
.size() );
135 assert( _i2
< _nb1
[i1
].size() );
137 return _nb1
[i1
][_i2
];
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 {
143 assert( i2
< _nb2
.size() );
144 assert( _i1
< _nb2
[i2
].size() );
146 return _nb2
[i2
][_i1
];
148 /// Returns reference to the _i1'th neighbor of node i2 of type 2
149 Neighbor
& nb2( size_t i2
, size_t _i1
) {
151 assert( i2
< _nb2
.size() );
152 assert( _i1
< _nb2
[i2
].size() );
154 return _nb2
[i2
][_i1
];
157 /// Returns constant reference to all neighbors of node i1 of type 1
158 const Neighbors
& nb1( size_t i1
) const {
160 assert( i1
< _nb1
.size() );
164 /// Returns reference to all neighbors of node of i1 type 1
165 Neighbors
& nb1( size_t i1
) {
167 assert( i1
< _nb1
.size() );
172 /// Returns constant reference to all neighbors of node i2 of type 2
173 const Neighbors
& nb2( size_t i2
) const {
175 assert( i2
< _nb2
.size() );
179 /// Returns reference to all neighbors of node i2 of type 2
180 Neighbors
& nb2( size_t i2
) {
182 assert( i2
< _nb2
.size() );
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 {
195 for( size_t i1
= 0; i1
< nr1(); i1
++ )
196 sum
+= nb1(i1
).size();
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.
211 template <typename NodeInputIterator
>
212 void add1( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
214 nbs1new
.reserve( sizeHint
);
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
);
223 _nb1
.push_back( nbs1new
);
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.
231 template <typename NodeInputIterator
>
232 void add2( NodeInputIterator begin
, NodeInputIterator end
, size_t sizeHint
= 0 ) {
234 nbs2new
.reserve( sizeHint
);
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
);
243 _nb2
.push_back( nbs2new
);
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.
255 void addEdge( size_t n1
, size_t n2
, bool check
= true ) {
256 assert( n1
< nr1() );
257 assert( n2
< nr2() );
260 // Check whether the edge already exists
261 foreach( const Neighbor
&nb2
, nb1(n1
) )
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
);
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.
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.
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.
294 /// Stream to output stream os in graphviz .dot syntax
295 void printDot( std::ostream
& os
) const;
297 /// Checks internal consistency
302 template<typename EdgeInputIterator
>
303 void BipartiteGraph::construct( size_t nr1
, size_t nr2
, EdgeInputIterator begin
, EdgeInputIterator end
) {
309 for( EdgeInputIterator e
= begin
; e
!= end
; e
++ ) {
311 addEdge( e
->first
, e
->second
, true );
313 addEdge( e
->first
, e
->second
, false );
319 } // end of namespace dai