Two tiny improvements
[libdai.git] / include / dai / weightedgraph.h
1 /* Copyright (C) 2006-2008 Joris Mooij [joris dot mooij at tuebingen dot mpg dot de]
2 Radboud University Nijmegen, The Netherlands /
3 Max Planck Institute for Biological Cybernetics, Germany
4
5 This file is part of libDAI.
6
7 libDAI is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 libDAI is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with libDAI; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22
23 /** \file
24 * \brief Defines some utility functions for weighted graphs
25 * \todo Improve documentation
26 * \todo Improve general support for graphs and trees.
27 */
28
29
30 #ifndef __defined_libdai_weightedgraph_h
31 #define __defined_libdai_weightedgraph_h
32
33
34 #include <vector>
35 #include <map>
36 #include <iostream>
37 #include <set>
38 #include <cassert>
39 #include <limits>
40
41 #include <boost/graph/adjacency_list.hpp>
42 #include <boost/graph/prim_minimum_spanning_tree.hpp>
43
44
45 namespace dai {
46
47
48 /// Represents a directed edge pointing from n1 to n2
49 class DEdge {
50 public:
51 size_t n1; ///< First node index
52 size_t n2; ///< Second node index
53
54 /// Default constructor
55 DEdge() {}
56
57 /// Constructor
58 DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
59
60 /// Tests for equality
61 bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
62
63 /// Tests for inequality
64 bool operator!=( const DEdge &x ) const { return !(*this == x); }
65
66 /// Smaller-than operator (performs lexicographical comparison)
67 bool operator<( const DEdge &x ) const {
68 return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
69 }
70
71 /// Writes a DEdge to an output stream
72 friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
73 os << "(" << e.n1 << "," << e.n2 << ")";
74 return os;
75 }
76 };
77
78
79 /// Undirected edge between nodes n1 and n2
80 class UEdge {
81 public:
82 size_t n1; ///< First node index
83 size_t n2; ///< Second node index
84
85 /// Default constructor
86 UEdge() {}
87
88 /// Constructor
89 UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
90
91 /// Construct from DEdge
92 UEdge( const DEdge & e ) : n1(e.n1), n2(e.n2) {}
93
94 /// Tests for inequality (disregarding the ordering of n1 and n2)
95 bool operator==( const UEdge &x ) {
96 return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
97 }
98
99 /// Smaller-than operator
100 bool operator<( const UEdge &x ) const {
101 size_t s = n1, l = n2;
102 if( s > l )
103 std::swap( s, l );
104 size_t xs = x.n1, xl = x.n2;
105 if( xs > xl )
106 std::swap( xs, xl );
107 return( (s < xs) || ((s == xs) && (l < xl)) );
108 }
109
110 /// Writes a UEdge to an output stream
111 friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
112 if( e.n1 < e.n2 )
113 os << "{" << e.n1 << "," << e.n2 << "}";
114 else
115 os << "{" << e.n2 << "," << e.n1 << "}";
116 return os;
117 }
118 };
119
120
121 /// Vector of UEdge
122 typedef std::vector<UEdge> UEdgeVec;
123
124 /// Vector of DEdge
125 typedef std::vector<DEdge> DEdgeVec;
126
127 /// Represents an undirected weighted graph, with weights of type T
128 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
129
130 /// Represents an undirected graph
131 typedef std::set<UEdge> Graph;
132
133
134 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
135 /** Uses implementation in Boost Graph Library.
136 */
137 template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G ) {
138 DEdgeVec result;
139 if( G.size() > 0 ) {
140 using namespace boost;
141 using namespace std;
142 typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
143 typedef pair<size_t, size_t> E;
144
145 set<size_t> nodes;
146 vector<E> edges;
147 vector<double> weights;
148 edges.reserve( G.size() );
149 weights.reserve( G.size() );
150 for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
151 weights.push_back( e->second );
152 edges.push_back( E( e->first.n1, e->first.n2 ) );
153 nodes.insert( e->first.n1 );
154 nodes.insert( e->first.n2 );
155 }
156
157 boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
158 vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
159 prim_minimum_spanning_tree( g, &(p[0]) );
160
161 // Store tree edges in result
162 result.reserve( nodes.size() - 1 );
163 size_t root = 0;
164 for( size_t i = 0; i != p.size(); i++ )
165 if( p[i] != i )
166 result.push_back( DEdge( p[i], i ) );
167 else
168 root = i;
169
170 // We have to store the minimum spanning tree in the right
171 // order, such that for all (i1, j1), (i2, j2) in result,
172 // if j1 == i2 then (i1, j1) comes before (i2, j2) in result.
173 // We do this by reordering the contents of result, effectively
174 // growing the tree starting at the root. At each step,
175 // result[0..N-1] are the edges already added to the tree,
176 // whereas the other elements of result still have to be added.
177 // The elements of nodes are the vertices that still have to
178 // be added to the tree.
179
180 // Start with the root
181 nodes.erase( root );
182 size_t N = 0;
183
184 // Iteratively add edges and nodes to the growing tree
185 while( N != result.size() ) {
186 for( size_t e = N; e != result.size(); e++ ) {
187 bool e1_in_tree = !nodes.count( result[e].n1 );
188 if( e1_in_tree ) {
189 nodes.erase( result[e].n2 );
190 swap( result[N], result[e] );
191 N++;
192 break;
193 }
194 }
195 }
196 }
197
198 return result;
199 }
200
201
202 /// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
203 /** Uses implementation in Boost Graph Library.
204 */
205 template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> & Graph ) {
206 T maxweight = Graph.begin()->second;
207 for( typename WeightedGraph<T>::const_iterator it = Graph.begin(); it != Graph.end(); it++ )
208 if( it->second > maxweight )
209 maxweight = it->second;
210 // make a copy of the graph
211 WeightedGraph<T> gr( Graph );
212 // invoke MinSpanningTreePrims with negative weights
213 // (which have to be shifted to satisfy positivity criterion)
214 for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
215 it->second = maxweight - it->second;
216 return MinSpanningTreePrims( gr );
217 }
218
219
220 /// Constructs a rooted tree from a tree and a root
221 DEdgeVec GrowRootedTree( const Graph & T, size_t Root );
222
223
224 /// Constructs a random undirected graph of N nodes, where each node has connectivity d
225 UEdgeVec RandomDRegularGraph( size_t N, size_t d );
226
227
228 } // end of namespace dai
229
230
231 #endif