libDAI
weightedgraph.h
Go to the documentation of this file.
1 /* This file is part of libDAI - http://www.libdai.org/
2  *
3  * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4  *
5  * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6  */
7 
8 
15 #ifndef __defined_libdai_weightedgraph_h
16 #define __defined_libdai_weightedgraph_h
17 
18 
19 #include <vector>
20 #include <map>
21 #include <iostream>
22 #include <set>
23 #include <limits>
24 #include <climits> // Work-around for bug in boost graph library
25 
26 #include <boost/graph/adjacency_list.hpp>
27 #include <boost/graph/prim_minimum_spanning_tree.hpp>
28 #include <boost/graph/kruskal_min_spanning_tree.hpp>
29 
30 #include <dai/util.h>
31 #include <dai/exceptions.h>
32 #include <dai/graph.h>
33 
34 
35 namespace dai {
36 
37 
39 class DEdge {
40  public:
42  size_t first;
43 
45  size_t second;
46 
48  DEdge() : first(0), second(0) {}
49 
51  DEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {}
52 
54  bool operator==( const DEdge &x ) const { return ((first == x.first) && (second == x.second)); }
55 
57  bool operator<( const DEdge &x ) const {
58  return( (first < x.first) || ((first == x.first) && (second < x.second)) );
59  }
60 
62  friend std::ostream & operator << (std::ostream & os, const DEdge & e) {
63  os << "(" << e.first << "->" << e.second << ")";
64  return os;
65  }
66 };
67 
68 
70 class UEdge {
71  public:
73  size_t first;
74 
76  size_t second;
77 
79  UEdge() : first(0), second(0) {}
80 
82  UEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {}
83 
85  UEdge( const DEdge &e ) : first(e.first), second(e.second) {}
86 
88  bool operator==( const UEdge &x ) {
89  return ((first == x.first) && (second == x.second)) || ((first == x.second) && (second == x.first));
90  }
91 
93  bool operator<( const UEdge &x ) const {
94  size_t s = std::min( first, second );
95  size_t l = std::max( first, second );
96  size_t xs = std::min( x.first, x.second );
97  size_t xl = std::max( x.first, x.second );
98  return( (s < xs) || ((s == xs) && (l < xl)) );
99  }
100 
102  friend std::ostream & operator << (std::ostream & os, const UEdge & e) {
103  if( e.first < e.second )
104  os << "{" << e.first << "--" << e.second << "}";
105  else
106  os << "{" << e.second << "--" << e.first << "}";
107  return os;
108  }
109 };
110 
111 
113 class GraphEL : public std::set<UEdge> {
114  public:
116  GraphEL() {}
117 
119  template <class InputIterator>
120  GraphEL( InputIterator begin, InputIterator end ) {
121  insert( begin, end );
122  }
123 
125  GraphEL( const GraphAL& G ) {
126  for( size_t n1 = 0; n1 < G.nrNodes(); n1++ )
127  bforeach( const Neighbor n2, G.nb(n1) )
128  if( n1 < n2 )
129  insert( UEdge( n1, n2 ) );
130  }
131 };
132 
133 
135 template<class T> class WeightedGraph : public std::map<UEdge, T> {};
136 
137 
139 
143 class RootedTree : public std::vector<DEdge> {
144  public:
147 
149 
151  RootedTree( const GraphEL &T, size_t Root );
152 };
153 
154 
156 
161 template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool usePrim ) {
162  RootedTree result;
163  if( G.size() > 0 ) {
164  using namespace boost;
165  using namespace std;
166  typedef adjacency_list< vecS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph;
167 
168  set<size_t> nodes;
169  vector<UEdge> edges;
170  vector<double> weights;
171  edges.reserve( G.size() );
172  weights.reserve( G.size() );
173  for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) {
174  weights.push_back( e->second );
175  edges.push_back( e->first );
176  nodes.insert( e->first.first );
177  nodes.insert( e->first.second );
178  }
179 
180  size_t N = nodes.size();
181  for( set<size_t>::const_iterator it = nodes.begin(); it != nodes.end(); it++ )
182  if( *it >= N )
183  DAI_THROWE(RUNTIME_ERROR,"Vertices must be in range [0..N) where N is the number of vertices.");
184 
185  boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() );
186  size_t root = *(nodes.begin());
187  GraphEL tree;
188  if( usePrim ) {
189  // Prim's algorithm
190  vector< graph_traits< boostGraph >::vertex_descriptor > p(N);
191  prim_minimum_spanning_tree( g, &(p[0]) );
192 
193  // Store tree edges in result
194  for( size_t i = 0; i != p.size(); i++ ) {
195  if( p[i] != i )
196  tree.insert( UEdge( p[i], i ) );
197  }
198  } else {
199  // Kruskal's algorithm
200  vector< graph_traits< boostGraph >::edge_descriptor > t;
201  t.reserve( N - 1 );
202  kruskal_minimum_spanning_tree( g, std::back_inserter(t) );
203 
204  // Store tree edges in result
205  for( size_t i = 0; i != t.size(); i++ ) {
206  size_t v1 = source( t[i], g );
207  size_t v2 = target( t[i], g );
208  if( v1 != v2 )
209  tree.insert( UEdge( v1, v2 ) );
210  }
211  }
212 
213  // Direct edges in order to obtain a rooted tree
214  result = RootedTree( tree, root );
215  }
216  return result;
217 }
218 
219 
221 
226 template<typename T> RootedTree MaxSpanningTree( const WeightedGraph<T> &G, bool usePrim ) {
227  if( G.size() == 0 )
228  return RootedTree();
229  else {
230  T maxweight = G.begin()->second;
231  for( typename WeightedGraph<T>::const_iterator it = G.begin(); it != G.end(); it++ )
232  if( it->second > maxweight )
233  maxweight = it->second;
234  // make a copy of the graph
235  WeightedGraph<T> gr( G );
236  // invoke MinSpanningTree with negative weights
237  // (which have to be shifted to satisfy positivity criterion)
238  for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ )
239  it->second = maxweight - it->second;
240  return MinSpanningTree( gr, usePrim );
241  }
242 }
243 
244 
245 } // end of namespace dai
246 
247 
248 #endif