Partial adoption of contributions by Giuseppe:
[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 <vector>
27 #include <algorithm>
28 #include <boost/numeric/ublas/vector_sparse.hpp>
29
30
31 namespace dai {
32
33
34 /// A BipartiteGraph represents a graph with two types of nodes
35 template <class T1, class T2> class BipartiteGraph {
36 public:
37 typedef std::pair<size_t,size_t> _edge_t;
38 typedef std::vector<size_t> _nb_t;
39 typedef _nb_t::const_iterator _nb_cit;
40
41
42 private:
43 /// Vertices of first type
44 std::vector<T1> _V1;
45
46 /// Vertices of second type
47 std::vector<T2> _V2;
48
49 /// Edges, which are pairs (v1,v2) with v1 in _V1 and v2 in _V2
50 std::vector<_edge_t> _E12;
51
52 /// Conversion matrix that computes which index of _E12 corresponds to a vertex index pair (v1,v2)
53 std::vector<boost::numeric::ublas::mapped_vector<size_t> > _E12ind;
54
55 /// Neighbour indices of vertices of first type
56 std::vector<_nb_t> _nb1;
57
58 /// Neighbour indices of vertices of second type
59 std::vector<_nb_t> _nb2;
60
61
62 public:
63 /// Default constructor
64 BipartiteGraph<T1,T2> () {};
65
66 /// Copy constructor
67 BipartiteGraph<T1,T2> ( const BipartiteGraph<T1,T2> & x ) : _V1(x._V1), _V2(x._V2), _E12(x._E12), _E12ind(x._E12ind), _nb1(x._nb1), _nb2(x._nb2) {};
68
69 /// Assignment operator
70 BipartiteGraph<T1,T2> & operator=(const BipartiteGraph<T1,T2> & x) {
71 if( this != &x ) {
72 _V1 = x._V1;
73 _V2 = x._V2;
74 _E12 = x._E12;
75 _E12ind = x._E12ind;
76 _nb1 = x._nb1;
77 _nb2 = x._nb2;
78 }
79 return *this;
80 }
81
82 /// Provides read access to node of first type
83 const T1 & V1( size_t i1 ) const { return _V1[i1]; }
84 /// Provides full access to node of first type
85 T1 & V1( size_t i1 ) { return _V1[i1]; }
86 /// Provides read access to all nodes of first type
87 const std::vector<T1> & V1s() const { return _V1; }
88 /// Provides full access to all nodes of first type
89 std::vector<T1> & V1s() { return _V1; }
90
91 /// Provides read access to node of second type
92 const T2 & V2( size_t i2 ) const { return _V2[i2]; }
93 /// Provides full access to node of second type
94 T2 & V2( size_t i2 ) { return _V2[i2]; }
95 /// Provides read access to all nodes of second type
96 const std::vector<T2> & V2s() const { return _V2; }
97 /// Provides full access to all nodes of second type
98 std::vector<T2> & V2s() { return _V2; }
99
100 /// Provides read access to edge
101 const _edge_t & edge(size_t ind) const { return _E12[ind]; }
102 /// Provides full access to edge
103 _edge_t & edge(size_t ind) { return _E12[ind]; }
104 /// Provides read access to all edges
105 const std::vector<_edge_t> & edges() const { return _E12; }
106 /// Provides full access to all edges
107 std::vector<_edge_t> & edges() { return _E12; }
108 /// Returns number of edges
109 size_t nr_edges() const { return _E12.size(); }
110
111 /// Provides read access to neighbours of node of first type
112 const _nb_t & nb1( size_t i1 ) const { return _nb1[i1]; }
113 /// Provides full access to neighbours of node of first type
114 _nb_t & nb1( size_t i1 ) { return _nb1[i1]; }
115
116 /// Provides read access to neighbours of node of second type
117 const _nb_t & nb2( size_t i2 ) const { return _nb2[i2]; }
118 /// Provides full access to neighbours of node of second type
119 _nb_t & nb2( size_t i2 ) { return _nb2[i2]; }
120
121 /// Converts the pair of indices (i1,i2) to the corresponding edge index
122 size_t VV2E( const size_t i1, const size_t i2 ) const { return _E12ind[i1](i2); }
123
124
125 /// Regenerates internal structures (_E12ind, _nb1 and _nb2) based upon _V1, _V2 and _E12
126 void Regenerate() {
127 // Calculate _nb1 and _nb2
128
129 // Start with empty vectors
130 _nb1.clear();
131 _nb1.resize(_V1.size());
132 // Start with empty vectors
133 _nb2.clear();
134 _nb2.resize(_V2.size());
135 // Each edge yields a neighbour pair
136 for( std::vector<_edge_t>::const_iterator e = _E12.begin(); e != _E12.end(); e++ ) {
137 _nb1[e->first].push_back(e->second);
138 _nb2[e->second].push_back(e->first);
139 }
140 // Remove duplicates from _nb1
141 for( size_t i1 = 0; i1 < _V1.size(); i1++ ) {
142 _nb_t::iterator new_end = unique(_nb1[i1].begin(), _nb1[i1].end());
143 _nb1[i1].erase( new_end, _nb1[i1].end() );
144 }
145 // Remove duplicates from _nb2
146 for( size_t i2 = 0; i2 < _V2.size(); i2++ ) {
147 _nb_t::iterator new_end = unique(_nb2[i2].begin(), _nb2[i2].end());
148 _nb2[i2].erase( new_end, _nb2[i2].end() );
149 }
150
151 // Calculate _E12ind
152 _E12ind = std::vector<boost::numeric::ublas::mapped_vector<size_t> >(_V1.size(), boost::numeric::ublas::mapped_vector<size_t>(_V2.size()) );
153 for( size_t k = 0; k < _E12.size(); k++ )
154 _E12ind[_E12[k].first](_E12[k].second) = k;
155
156 }
157 };
158
159
160 } // end of namespace dai
161
162
163 #endif