1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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 */
12 /** \file
13 * \brief Defines some utility functions for weighted graphs
14 * \todo Improve documentation
15 * \todo Improve general support for graphs and trees.
16 */
19 #ifndef __defined_libdai_weightedgraph_h
20 #define __defined_libdai_weightedgraph_h
23 #include <vector>
24 #include <map>
25 #include <iostream>
26 #include <set>
27 #include <cassert>
28 #include <limits>
29 #include <climits> // Work-around for bug in boost graph library
32 #include <boost/graph/prim_minimum_spanning_tree.hpp>
35 namespace dai {
38 /// Represents a directed edge pointing from n1 to n2
39 class DEdge {
40 public:
41 size_t n1; ///< First node index
42 size_t n2; ///< Second node index
44 /// Default constructor
45 DEdge() {}
47 /// Constructor
48 DEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
50 /// Tests for equality
51 bool operator==( const DEdge &x ) const { return ((n1 == x.n1) && (n2 == x.n2)); }
53 /// Tests for inequality
54 bool operator!=( const DEdge &x ) const { return !(*this == x); }
56 /// Smaller-than operator (performs lexicographical comparison)
57 bool operator<( const DEdge &x ) const {
58 return( (n1 < x.n1) || ((n1 == x.n1) && (n2 < x.n2)) );
59 }
61 /// Writes a DEdge to an output stream
62 friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
63 os << "(" << e.n1 << "," << e.n2 << ")";
64 return os;
65 }
66 };
69 /// Undirected edge between nodes n1 and n2
70 class UEdge {
71 public:
72 size_t n1; ///< First node index
73 size_t n2; ///< Second node index
75 /// Default constructor
76 UEdge() {}
78 /// Constructor
79 UEdge( size_t m1, size_t m2 ) : n1(m1), n2(m2) {}
81 /// Construct from DEdge
82 UEdge( const DEdge & e ) : n1(e.n1), n2(e.n2) {}
84 /// Tests for inequality (disregarding the ordering of n1 and n2)
85 bool operator==( const UEdge &x ) {
86 return ((n1 == x.n1) && (n2 == x.n2)) || ((n1 == x.n2) && (n2 == x.n1));
87 }
89 /// Smaller-than operator
90 bool operator<( const UEdge &x ) const {
91 size_t s = n1, l = n2;
92 if( s > l )
93 std::swap( s, l );
94 size_t xs = x.n1, xl = x.n2;
95 if( xs > xl )
96 std::swap( xs, xl );
97 return( (s < xs) || ((s == xs) && (l < xl)) );
98 }
100 /// Writes a UEdge to an output stream
101 friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
102 if( e.n1 < e.n2 )
103 os << "{" << e.n1 << "," << e.n2 << "}";
104 else
105 os << "{" << e.n2 << "," << e.n1 << "}";
106 return os;
107 }
108 };
111 /// Vector of UEdge
112 typedef std::vector<UEdge> UEdgeVec;
114 /// Vector of DEdge
115 typedef std::vector<DEdge> DEdgeVec;
117 /// Represents an undirected weighted graph, with weights of type T
118 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
120 /// Represents an undirected graph
121 typedef std::set<UEdge> Graph;
124 /// Uses Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
125 /** Uses implementation in Boost Graph Library.
126 */
127 template<typename T> DEdgeVec MinSpanningTreePrims( const WeightedGraph<T> &G ) {
128 DEdgeVec result;
129 if( G.size() > 0 ) {
130 using namespace boost;
131 using namespace std;
132 typedef adjacency_list< vecS, vecS, undirectedS, property<vertex_distance_t, int>, property<edge_weight_t, double> > boostGraph;
133 typedef pair<size_t, size_t> E;
135 set<size_t> nodes;
136 vector<E> edges;
137 vector<double> weights;
138 edges.reserve( G.size() );
139 weights.reserve( G.size() );
140 for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
141 weights.push_back( e->second );
142 edges.push_back( E( e->first.n1, e->first.n2 ) );
143 nodes.insert( e->first.n1 );
144 nodes.insert( e->first.n2 );
145 }
147 boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
148 vector< graph_traits< boostGraph >::vertex_descriptor > p( num_vertices(g) );
149 prim_minimum_spanning_tree( g, &(p) );
151 // Store tree edges in result
152 result.reserve( nodes.size() - 1 );
153 size_t root = 0;
154 for( size_t i = 0; i != p.size(); i++ )
155 if( p[i] != i )
156 result.push_back( DEdge( p[i], i ) );
157 else
158 root = i;
160 // We have to store the minimum spanning tree in the right
161 // order, such that for all (i1, j1), (i2, j2) in result,
162 // if j1 == i2 then (i1, j1) comes before (i2, j2) in result.
163 // We do this by reordering the contents of result, effectively
164 // growing the tree starting at the root. At each step,
165 // result[0..N-1] are the edges already added to the tree,
166 // whereas the other elements of result still have to be added.
167 // The elements of nodes are the vertices that still have to
168 // be added to the tree.
171 nodes.erase( root );
172 size_t N = 0;
174 // Iteratively add edges and nodes to the growing tree
175 while( N != result.size() ) {
176 for( size_t e = N; e != result.size(); e++ ) {
177 bool e1_in_tree = !nodes.count( result[e].n1 );
178 if( e1_in_tree ) {
179 nodes.erase( result[e].n2 );
180 swap( result[N], result[e] );
181 N++;
182 break;
183 }
184 }
185 }
186 }
188 return result;
189 }
192 /// Use Prim's algorithm to construct a minimal spanning tree from the (positively) weighted graph G.
193 /** Uses implementation in Boost Graph Library.
194 */
195 template<typename T> DEdgeVec MaxSpanningTreePrims( const WeightedGraph<T> & Graph ) {
196 if( Graph.size() == 0 )
197 return DEdgeVec();
198 else {
199 T maxweight = Graph.begin()->second;
200 for( typename WeightedGraph<T>::const_iterator it = Graph.begin(); it != Graph.end(); it++ )
201 if( it->second > maxweight )
202 maxweight = it->second;
203 // make a copy of the graph
204 WeightedGraph<T> gr( Graph );
205 // invoke MinSpanningTreePrims with negative weights
206 // (which have to be shifted to satisfy positivity criterion)
207 for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
208 it->second = maxweight - it->second;
209 return MinSpanningTreePrims( gr );
210 }
211 }
214 /// Constructs a rooted tree from a tree and a root
215 DEdgeVec GrowRootedTree( const Graph & T, size_t Root );
218 /// Constructs a random undirected graph of N nodes, where each node has connectivity d
219 UEdgeVec RandomDRegularGraph( size_t N, size_t d );
222 } // end of namespace dai
225 #endif