Fixed three minor issues
[libdai.git] / include / dai / weightedgraph.h
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 /** \file
13 * \brief Defines some utility functions for (weighted) undirected graphs, trees and rooted trees.
14 * \todo Improve general support for graphs and trees (in particular, a good tree implementation is needed).
15 */
16
17
18 #ifndef __defined_libdai_weightedgraph_h
19 #define __defined_libdai_weightedgraph_h
20
21
22 #include <vector>
23 #include <map>
24 #include <iostream>
25 #include <set>
26 #include <limits>
27 #include <climits> // Work-around for bug in boost graph library
28 #include <dai/util.h>
29 #include <dai/exceptions.h>
30 #include <dai/graph.h>
31
32 #include <boost/graph/adjacency_list.hpp>
33 #include <boost/graph/prim_minimum_spanning_tree.hpp>
34 #include <boost/graph/kruskal_min_spanning_tree.hpp>
35
36
37 namespace dai {
38
39
40 /// Represents a directed edge
41 class DEdge {
42 public:
43 /// First node index (source of edge)
44 union {
45 size_t first;
46 /// \deprecated Please use member dai::DEdge::first instead
47 size_t n1;
48 };
49
50 /// Second node index (target of edge)
51 union {
52 size_t second;
53 /// \deprecated Please use member dai::DEdge::second instead
54 size_t n2;
55 };
56
57 /// Default constructor
58 DEdge() : first(0), second(0) {}
59
60 /// Constructs a directed edge pointing from \a m1 to \a m2
61 DEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {}
62
63 /// Tests for equality
64 bool operator==( const DEdge &x ) const { return ((first == x.first) && (second == x.second)); }
65
66 /// Smaller-than operator (performs lexicographical comparison)
67 bool operator<( const DEdge &x ) const {
68 return( (first < x.first) || ((first == x.first) && (second < x.second)) );
69 }
70
71 /// Writes a directed edge to an output stream
72 friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
73 os << "(" << e.first << "->" << e.second << ")";
74 return os;
75 }
76 };
77
78
79 /// Represents an undirected edge
80 class UEdge {
81 public:
82 /// First node index
83 union {
84 size_t first;
85 /// \deprecated Please use member dai::UEdge::first instead
86 size_t n1;
87 };
88
89 /// Second node index
90 union {
91 size_t second;
92 /// \deprecated Please use member dai::UEdge::second instead
93 size_t n2;
94 };
95
96 /// Default constructor
97 UEdge() : first(0), second(0) {}
98
99 /// Constructs an undirected edge between \a m1 and \a m2
100 UEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {}
101
102 /// Construct from DEdge
103 UEdge( const DEdge &e ) : first(e.first), second(e.second) {}
104
105 /// Tests for inequality (disregarding the ordering of the nodes)
106 bool operator==( const UEdge &x ) {
107 return ((first == x.first) && (second == x.second)) || ((first == x.second) && (second == x.first));
108 }
109
110 /// Smaller-than operator
111 bool operator<( const UEdge &x ) const {
112 size_t s = std::min( first, second );
113 size_t l = std::max( first, second );
114 size_t xs = std::min( x.first, x.second );
115 size_t xl = std::max( x.first, x.second );
116 return( (s < xs) || ((s == xs) && (l < xl)) );
117 }
118
119 /// Writes an undirected edge to an output stream
120 friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
121 if( e.first < e.second )
122 os << "{" << e.first << "--" << e.second << "}";
123 else
124 os << "{" << e.second << "--" << e.first << "}";
125 return os;
126 }
127 };
128
129
130 /// Represents an undirected graph, implemented as a std::set of undirected edges
131 class GraphEL : public std::set<UEdge> {
132 public:
133 /// Default constructor
134 GraphEL() {}
135
136 /// Construct from range of objects that can be cast to UEdge
137 template <class InputIterator>
138 GraphEL( InputIterator begin, InputIterator end ) {
139 insert( begin, end );
140 }
141
142 /// Construct from GraphAL
143 GraphEL( const GraphAL& G ) {
144 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ )
145 foreach( const GraphAL::Neighbor n2, G.nb(n1) )
146 if( n1 < n2 )
147 insert( UEdge( n1, n2 ) );
148 }
149 };
150
151
152 /// Represents an undirected weighted graph, with weights of type \a T, implemented as a std::map mapping undirected edges to weights
153 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
154
155
156 /// Represents a rooted tree, implemented as a vector of directed edges
157 /** By convention, the edges are stored such that they point away from
158 * the root and such that edges nearer to the root come before edges
159 * farther away from the root.
160 */
161 class RootedTree : public std::vector<DEdge> {
162 public:
163 /// Default constructor
164 RootedTree() {}
165
166 /// Constructs a rooted tree from a tree and a root
167 /** \pre T has no cycles and contains node \a Root
168 */
169 RootedTree( const GraphEL &T, size_t Root );
170 };
171
172
173 /// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G.
174 /** \param G Weighted graph that should have non-negative weights.
175 * \param usePrim If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E))).
176 * \note Uses implementation from Boost Graph Library.
177 * \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
178 */
179 template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool usePrim ) {
180 RootedTree result;
181 if( G.size() > 0 ) {
182 using namespace boost;
183 using namespace std;
184 typedef adjacency_list< vecS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph;
185
186 set<size_t> nodes;
187 vector<UEdge> edges;
188 vector<double> weights;
189 edges.reserve( G.size() );
190 weights.reserve( G.size() );
191 for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
192 weights.push_back( e->second );
193 edges.push_back( e->first );
194 nodes.insert( e->first.first );
195 nodes.insert( e->first.second );
196 }
197
198 size_t N = nodes.size();
199 for( set<size_t>::const_iterator it = nodes.begin(); it != nodes.end(); it++ )
200 if( *it >= N )
201 DAI_THROWE(RUNTIME_ERROR,"Vertices must be in range [0..N) where N is the number of vertices.");
202
203 boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
204 size_t root = *(nodes.begin());
205 GraphEL tree;
206 if( usePrim ) {
207 // Prim's algorithm
208 vector< graph_traits< boostGraph >::vertex_descriptor > p(N);
209 prim_minimum_spanning_tree( g, &(p[0]) );
210
211 // Store tree edges in result
212 for( size_t i = 0; i != p.size(); i++ ) {
213 if( p[i] != i )
214 tree.insert( UEdge( p[i], i ) );
215 }
216 } else {
217 // Kruskal's algorithm
218 vector< graph_traits< boostGraph >::edge_descriptor > t;
219 t.reserve( N - 1 );
220 kruskal_minimum_spanning_tree( g, std::back_inserter(t) );
221
222 // Store tree edges in result
223 for( size_t i = 0; i != t.size(); i++ ) {
224 size_t v1 = source( t[i], g );
225 size_t v2 = target( t[i], g );
226 if( v1 != v2 )
227 tree.insert( UEdge( v1, v2 ) );
228 }
229 }
230
231 // Direct edges in order to obtain a rooted tree
232 result = RootedTree( tree, root );
233 }
234 return result;
235 }
236
237
238 /// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G.
239 /** \param G Weighted graph that should have non-negative weights.
240 * \param usePrim If true, use Prim's algorithm (complexity O(E log(V))), otherwise, use Kruskal's algorithm (complexity O(E log(E))).
241 * \note Uses implementation from Boost Graph Library.
242 * \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
243 */
244 template<typename T> RootedTree MaxSpanningTree( const WeightedGraph<T> &G, bool usePrim ) {
245 if( G.size() == 0 )
246 return RootedTree();
247 else {
248 T maxweight = G.begin()->second;
249 for( typename WeightedGraph<T>::const_iterator it = G.begin(); it != G.end(); it++ )
250 if( it->second > maxweight )
251 maxweight = it->second;
252 // make a copy of the graph
253 WeightedGraph<T> gr( G );
254 // invoke MinSpanningTree with negative weights
255 // (which have to be shifted to satisfy positivity criterion)
256 for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
257 it->second = maxweight - it->second;
258 return MinSpanningTree( gr, usePrim );
259 }
260 }
261
262
263 /// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G using Prim's algorithm.
264 /** \param G Weighted graph that should have non-negative weights.
265 * \note Uses implementation from Boost Graph Library.
266 * \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
267 * \deprecated Please use dai::MinSpanningTree(const WeightedGraph&, bool) instead
268 */
269 template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G ) {
270 return MinSpanningTree( G, true );
271 }
272
273
274 /// Constructs a minimum spanning tree from the (non-negatively) weighted graph \a G using Prim's algorithm.
275 /** \param G Weighted graph that should have non-negative weights.
276 * \note Uses implementation from Boost Graph Library.
277 * \note The vertices of \a G must be in the range [0,N) where N is the number of vertices of \a G.
278 * \deprecated Please use dai::MinSpanningTree(const WeightedGraph&, bool) instead
279 */
280 template<typename T> RootedTree MaxSpanningTree( const WeightedGraph<T> &G ) {
281 return MaxSpanningTree( G, true );
282 }
283
284
285 /// Constructs a random undirected graph of \a N nodes, where each node has connectivity \a d
286 /** Algorithm 1 in [\ref StW99].
287 * Draws a random graph of size \a N and uniform degree \a d
288 * from an almost uniform probability distribution over these graphs
289 * (which becomes uniform in the limit that \a d is small and \a N goes
290 * to infinity).
291 * \deprecated Please use dai::createGraphRegular(size_t, size_t) instead
292 */
293 GraphEL RandomDRegularGraph( size_t N, size_t d );
294
295
296 } // end of namespace dai
297
298
299 #endif