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