36c98fe4c3431e0a156fe93c9dcec4c5e94aa560
[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-2009 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.
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
29 #include <boost/graph/adjacency_list.hpp>
30 #include <boost/graph/prim_minimum_spanning_tree.hpp>
31
32
33 namespace dai {
34
35
36 /// Represents a directed edge
37 class DEdge {
38 public:
39 /// First node index (source of edge)
40 size_t n1;
41
42 /// Second node index (sink of edge)
43 size_t n2;
44
45 /// Default constructor
46 DEdge() {}
47
48 /// Constructs a directed edge pointing from \a m1 to \a m2
49 DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
50
51 /// Tests for equality
52 bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
53
54 /// Tests for inequality
55 bool operator!=( const DEdge &x ) const { return !(*this == x); }
56
57 /// Smaller-than operator (performs lexicographical comparison)
58 bool operator<( const DEdge &x ) const {
59 return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
60 }
61
62 /// Writes a directed edge to an output stream
63 friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
64 os << "(" << e.n1 << "," << e.n2 << ")";
65 return os;
66 }
67 };
68
69
70 /// Represents an undirected edge
71 class UEdge {
72 public:
73 /// First node index
74 size_t n1;
75 /// Second node index
76 size_t n2;
77
78 /// Default constructor
79 UEdge() {}
80
81 /// Constructs an undirected edge between \a m1 and \a m2
82 UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
83
84 /// Construct from DEdge
85 UEdge( const DEdge &e ) : n1(e.n1), n2(e.n2) {}
86
87 /// Tests for inequality (disregarding the ordering of the nodes)
88 bool operator==( const UEdge &x ) {
89 return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
90 }
91
92 /// Smaller-than operator
93 bool operator<( const UEdge &x ) const {
94 size_t s = n1, l = n2;
95 if( s > l )
96 std::swap( s, l );
97 size_t xs = x.n1, xl = x.n2;
98 if( xs > xl )
99 std::swap( xs, xl );
100 return( (s < xs) || ((s == xs) && (l < xl)) );
101 }
102
103 /// Writes an undirected edge to an output stream
104 friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
105 if( e.n1 < e.n2 )
106 os << "{" << e.n1 << "," << e.n2 << "}";
107 else
108 os << "{" << e.n2 << "," << e.n1 << "}";
109 return os;
110 }
111 };
112
113
114 /// Represents an undirected graph, implemented as a std::set of undirected edges
115 class Graph : public std::set<UEdge> {
116 public:
117 /// Default constructor
118 Graph() {}
119
120 /// Construct from range of objects that can be cast to DEdge
121 template <class InputIterator>
122 Graph( InputIterator begin, InputIterator end ) {
123 insert( begin, end );
124 }
125 };
126
127
128 /// Represents an undirected weighted graph, with weights of type \a T, implemented as a std::map mapping undirected edges to weights
129 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
130
131
132 /// Represents a rooted tree, implemented as a vector of directed edges
133 /** By convention, the edges are stored such that they point away from
134 * the root and such that edges nearer to the root come before edges
135 * farther away from the root.
136 */
137 class RootedTree : public std::vector<DEdge> {
138 public:
139 /// Default constructor
140 RootedTree() {}
141
142 /// Constructs a rooted tree from a tree and a root
143 /** \pre T has no cycles and contains node \a Root
144 */
145 RootedTree( const Graph &T, size_t Root );
146 };
147
148
149 // OBSOLETE
150 /// Vector of UEdge
151 /** \deprecated Please use Graph instead
152 */
153 typedef std::vector<UEdge> UEdgeVec;
154 // OBSOLETE
155 /// Vector of DEdge
156 /** \deprecated Please use RootedTree instead
157 */
158 typedef std::vector<DEdge> DEdgeVec;
159
160 // OBSOLETE
161 /// Constructs a rooted tree from a tree and a root
162 /** \pre T has no cycles and contains node \a Root
163 * \deprecated Please use RootedTree::RootedTree(const Graph &, size_t) instead
164 */
165 DEdgeVec GrowRootedTree( const Graph &T, size_t Root );
166
167 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph \a G.
168 /** Uses implementation in Boost Graph Library.
169 */
170 template<typename T> RootedTree MinSpanningTreePrims( const WeightedGraph<T> &G ) {
171 RootedTree result;
172 if( G.size() > 0 ) {
173 using namespace boost;
174 using namespace std;
175 typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
176 typedef pair<size_t, size_t> E;
177
178 set<size_t> nodes;
179 vector<E> edges;
180 vector<double> weights;
181 edges.reserve( G.size() );
182 weights.reserve( G.size() );
183 for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
184 weights.push_back( e->second );
185 edges.push_back( E( e->first.n1, e->first.n2 ) );
186 nodes.insert( e->first.n1 );
187 nodes.insert( e->first.n2 );
188 }
189
190 boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
191 vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
192 prim_minimum_spanning_tree( g, &(p[0]) );
193
194 // Store tree edges in result
195 Graph tree;
196 size_t root = 0;
197 for( size_t i = 0; i != p.size(); i++ )
198 if( p[i] != i )
199 tree.insert( UEdge( p[i], i ) );
200 else
201 root = i;
202 // Order them to obtain a rooted tree
203 result = RootedTree( tree, root );
204 }
205 return result;
206 }
207
208
209 /// Use Prim's algorithm to construct a maximal spanning tree from the (positively) weighted graph \a G.
210 /** Uses implementation in Boost Graph Library.
211 */
212 template<typename T> RootedTree MaxSpanningTreePrims( const WeightedGraph<T> &G ) {
213 if( G.size() == 0 )
214 return RootedTree();
215 else {
216 T maxweight = G.begin()->second;
217 for( typename WeightedGraph<T>::const_iterator it = G.begin(); it != G.end(); it++ )
218 if( it->second > maxweight )
219 maxweight = it->second;
220 // make a copy of the graph
221 WeightedGraph<T> gr( G );
222 // invoke MinSpanningTreePrims with negative weights
223 // (which have to be shifted to satisfy positivity criterion)
224 for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
225 it->second = maxweight - it->second;
226 return MinSpanningTreePrims( gr );
227 }
228 }
229
230
231 /// Constructs a random undirected graph of \a N nodes, where each node has connectivity \a d
232 /** Algorithm 1 in [\ref StW99].
233 * Draws a random graph of size \a N and uniform degree \a d
234 * from an almost uniform probability distribution over these graphs
235 * (which becomes uniform in the limit that \a d is small and \a N goes
236 * to infinity).
237 */
238 Graph RandomDRegularGraph( size_t N, size_t d );
239
240
241 } // end of namespace dai
242
243
244 #endif