1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
4 This file is part of libDAI.
6 libDAI is free software; you can redistribute it and/or modify
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
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.
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 */
22 #ifndef __defined_libdai_bipgraph_h
23 #define __defined_libdai_bipgraph_h
26 #include <vector>
27 #include <algorithm>
28 #include <dai/util.h>
31 namespace dai {
34 /// A BipartiteGraph represents a bipartite graph, with two types of nodes (both are numbered
35 /// as 0,1,2,...), with edges only between nodes of different type. The edges are stored as
36 /// lists of adjacent nodes for each node.
37 class BipartiteGraph {
38 public:
39 /// A Neighbor describes a neighboring node of some other node.
40 /** Iterating over all neighbors of some node i can be done in the following way:
41 * \code
42 * foreach( const BipartiteGraph::Neighbor &I, nb1(i) ) {
43 * size_t _I = I.iter;
44 * size_t _i = I.dual;
45 * // I == I.node;
46 * // The _I'th neighbor of i is I, and the _i'th neighbor of I is i:
47 * // nb1(i)[_I] == I, nb2(I)[_i] == i
48 * }
49 * \endcode
50 */
51 struct Neighbor {
52 /// iter corresponds to the index of this Neighbor entry in the list of neighbors
53 unsigned iter;
54 /// node contains the number of the neighboring node
55 unsigned node;
56 /// dual contains the "dual" iter
57 unsigned dual;
58 /// cast to unsigned returns node
59 operator unsigned () const { return node; };
60 };
62 /// Neighbors is a vector of Neigbor entries
63 typedef std::vector<Neighbor> Neighbors;
65 private:
66 /// _nb1 contains for each node of the first kind a list of its neighbors
67 std::vector<Neighbors> _nb1;
68 /// _nb2 contains for each node of the second kind a list of its neighbors
69 std::vector<Neighbors> _nb2;
71 public:
72 /// Default constructor
73 BipartiteGraph() : _nb1(), _nb2() {}
75 /// Copy constructor
76 BipartiteGraph( const BipartiteGraph & x ) : _nb1(x._nb1), _nb2(x._nb2) {}
78 /// Assignment operator
79 BipartiteGraph & operator=( const BipartiteGraph & x ) {
80 if( this != &x ) {
81 _nb1 = x._nb1;
82 _nb2 = x._nb2;
83 }
84 return *this;
85 }
87 /// Create bipartite graph from a range of edges, encoded as pairs of node numbers
88 /// (more precisely, a std::pair<unsigned, unsigned> where the first integer corresponds
89 /// to the node of the first type, and the second integer corresponds to the node of the
90 /// second type). nr1 is the number of nodes of the first type, nr2 the number of nodes
91 /// of the second type.
92 template<typename EdgeInputIterator>
93 void create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end );
95 /// Construct bipartite graph from a range of edges, encoded as pairs of node numbers
96 /// (more precisely, a std::pair<unsigned, unsigned> where the first integer corresponds
97 /// to the node of the first type, and the second integer corresponds to the node of the
98 /// second type). nr1 is the number of nodes of the first type, nr2 the number of nodes
99 /// of the second type.
100 template<typename EdgeInputIterator>
101 BipartiteGraph( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) : _nb1( nr1 ), _nb2( nr2 ) {
102 create( nr1, nr2, begin, end );
103 }
105 /// Returns constant reference to the _i2'th neighbor of node i1 of first type
106 const Neighbor & nb1( size_t i1, size_t _i2 ) const { return _nb1[i1][_i2]; }
107 /// Returns reference to the _i2'th neighbor of node i1 of first type
108 Neighbor & nb1( size_t i1, size_t _i2 ) { return _nb1[i1][_i2]; }
110 /// Returns constant reference to the _i1'th neighbor of node i2 of second type
111 const Neighbor & nb2( size_t i2, size_t _i1 ) const { return _nb2[i2][_i1]; }
112 /// Returns reference to the _i1'th neighbor of node i2 of second type
113 Neighbor & nb2( size_t i2, size_t _i1 ) { return _nb2[i2][_i1]; }
115 /// Returns constant reference to all neighbors of node of first type
116 const Neighbors & nb1( size_t i1 ) const { return _nb1[i1]; }
117 /// Returns reference to all neighbors of node of first type
118 Neighbors & nb1( size_t i1 ) { return _nb1[i1]; }
120 /// Returns constant reference to all neighbors of node of second type
121 const Neighbors & nb2( size_t i2 ) const { return _nb2[i2]; }
122 /// Returns reference to all neighbors of node of second type
123 Neighbors & nb2( size_t i2 ) { return _nb2[i2]; }
125 /// Returns number of nodes of first type
126 size_t nr1() const { return _nb1.size(); }
127 /// Returns number of nodes of second type
128 size_t nr2() const { return _nb2.size(); }
130 /// Calculates the number of edges
131 size_t nrEdges() const {
132 size_t sum = 0;
133 for( size_t i1 = 0; i1 < nr1(); i1++ )
134 sum += nb1(i1).size();
135 return sum;
136 }
138 /// Returns true if the graph is connected
139 /// FIXME: this should be optimized
140 bool isConnected() const {
141 if( nr1() == 0 ) {
142 return true;
143 } else {
144 std::vector<bool> incomponent1( nr1(), false );
145 std::vector<bool> incomponent2( nr2(), false );
147 incomponent1[0] = true;
148 bool found_new_nodes;
149 do {
150 found_new_nodes = false;
152 // For all nodes of second type, check if they are connected with the (growing) component
153 for( size_t n2 = 0; n2 < nr2(); n2++ )
154 if( !incomponent2[n2] ) {
155 foreach( const Neighbor &n1, nb2(n2) ) {
156 if( incomponent1[n1] ) {
157 found_new_nodes = true;
158 incomponent2[n2] = true;
159 break;
160 }
161 }
162 }
164 // For all nodes of first type, check if they are connected with the (growing) component
165 for( size_t n1 = 0; n1 < nr1(); n1++ )
166 if( !incomponent1[n1] ) {
167 foreach( const Neighbor &n2, nb1(n1) ) {
168 if( incomponent2[n2] ) {
169 found_new_nodes = true;
170 incomponent1[n1] = true;
171 break;
172 }
173 }
174 }
175 } while( found_new_nodes );
177 // Check if there are remaining nodes (not in the component)
178 bool all_connected = true;
179 for( size_t n1 = 0; (n1 < nr1()) && all_connected; n1++ )
180 if( !incomponent1[n1] )
181 all_connected = false;
182 for( size_t n2 = 0; (n2 < nr2()) && all_connected; n2++ )
183 if( !incomponent2[n2] )
184 all_connected = false;
186 return all_connected;
187 }
188 }
190 };
193 template<typename EdgeInputIterator>
194 void BipartiteGraph::create( size_t nr1, size_t nr2, EdgeInputIterator begin, EdgeInputIterator end ) {
195 _nb1.clear();
196 _nb1.resize( nr1 );
197 _nb2.clear();
198 _nb2.resize( nr2 );
200 for( EdgeInputIterator e = begin; e != end; e++ ) {
201 // Each edge yields a neighbor pair
202 Neighbor nb_1;
203 nb_1.iter = _nb1[e->first].size();
204 nb_1.node = e->second;
205 nb_1.dual = _nb2[e->second].size();
207 Neighbor nb_2;
208 nb_2.iter = nb_1.dual;
209 nb_2.node = e->first;
210 nb_2.dual = nb_1.iter;
212 _nb1[e->first].push_back( nb_1 );
213 _nb2[e->second].push_back( nb_2 );
214 }
215 }
218 } // end of namespace dai
221 #endif