libDAI
|
00001 /* This file is part of libDAI - http://www.libdai.org/ 00002 * 00003 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved. 00004 * 00005 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file. 00006 */ 00007 00008 00015 #ifndef __defined_libdai_weightedgraph_h 00016 #define __defined_libdai_weightedgraph_h 00017 00018 00019 #include <vector> 00020 #include <map> 00021 #include <iostream> 00022 #include <set> 00023 #include <limits> 00024 #include <climits> // Work-around for bug in boost graph library 00025 #include <dai/util.h> 00026 #include <dai/exceptions.h> 00027 #include <dai/graph.h> 00028 00029 #include <boost/graph/adjacency_list.hpp> 00030 #include <boost/graph/prim_minimum_spanning_tree.hpp> 00031 #include <boost/graph/kruskal_min_spanning_tree.hpp> 00032 00033 00034 namespace dai { 00035 00036 00038 class DEdge { 00039 public: 00041 size_t first; 00042 00044 size_t second; 00045 00047 DEdge() : first(0), second(0) {} 00048 00050 DEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {} 00051 00053 bool operator==( const DEdge &x ) const { return ((first == x.first) && (second == x.second)); } 00054 00056 bool operator<( const DEdge &x ) const { 00057 return( (first < x.first) || ((first == x.first) && (second < x.second)) ); 00058 } 00059 00061 friend std::ostream & operator << (std::ostream & os, const DEdge & e) { 00062 os << "(" << e.first << "->" << e.second << ")"; 00063 return os; 00064 } 00065 }; 00066 00067 00069 class UEdge { 00070 public: 00072 size_t first; 00073 00075 size_t second; 00076 00078 UEdge() : first(0), second(0) {} 00079 00081 UEdge( size_t m1, size_t m2 ) : first(m1), second(m2) {} 00082 00084 UEdge( const DEdge &e ) : first(e.first), second(e.second) {} 00085 00087 bool operator==( const UEdge &x ) { 00088 return ((first == x.first) && (second == x.second)) || ((first == x.second) && (second == x.first)); 00089 } 00090 00092 bool operator<( const UEdge &x ) const { 00093 size_t s = std::min( first, second ); 00094 size_t l = std::max( first, second ); 00095 size_t xs = std::min( x.first, x.second ); 00096 size_t xl = std::max( x.first, x.second ); 00097 return( (s < xs) || ((s == xs) && (l < xl)) ); 00098 } 00099 00101 friend std::ostream & operator << (std::ostream & os, const UEdge & e) { 00102 if( e.first < e.second ) 00103 os << "{" << e.first << "--" << e.second << "}"; 00104 else 00105 os << "{" << e.second << "--" << e.first << "}"; 00106 return os; 00107 } 00108 }; 00109 00110 00112 class GraphEL : public std::set<UEdge> { 00113 public: 00115 GraphEL() {} 00116 00118 template <class InputIterator> 00119 GraphEL( InputIterator begin, InputIterator end ) { 00120 insert( begin, end ); 00121 } 00122 00124 GraphEL( const GraphAL& G ) { 00125 for( size_t n1 = 0; n1 < G.nrNodes(); n1++ ) 00126 foreach( const Neighbor n2, G.nb(n1) ) 00127 if( n1 < n2 ) 00128 insert( UEdge( n1, n2 ) ); 00129 } 00130 }; 00131 00132 00134 template<class T> class WeightedGraph : public std::map<UEdge, T> {}; 00135 00136 00138 00142 class RootedTree : public std::vector<DEdge> { 00143 public: 00145 RootedTree() {} 00146 00148 00150 RootedTree( const GraphEL &T, size_t Root ); 00151 }; 00152 00153 00155 00160 template<typename T> RootedTree MinSpanningTree( const WeightedGraph<T> &G, bool usePrim ) { 00161 RootedTree result; 00162 if( G.size() > 0 ) { 00163 using namespace boost; 00164 using namespace std; 00165 typedef adjacency_list< vecS, vecS, undirectedS, no_property, property<edge_weight_t, double> > boostGraph; 00166 00167 set<size_t> nodes; 00168 vector<UEdge> edges; 00169 vector<double> weights; 00170 edges.reserve( G.size() ); 00171 weights.reserve( G.size() ); 00172 for( typename WeightedGraph<T>::const_iterator e = G.begin(); e != G.end(); e++ ) { 00173 weights.push_back( e->second ); 00174 edges.push_back( e->first ); 00175 nodes.insert( e->first.first ); 00176 nodes.insert( e->first.second ); 00177 } 00178 00179 size_t N = nodes.size(); 00180 for( set<size_t>::const_iterator it = nodes.begin(); it != nodes.end(); it++ ) 00181 if( *it >= N ) 00182 DAI_THROWE(RUNTIME_ERROR,"Vertices must be in range [0..N) where N is the number of vertices."); 00183 00184 boostGraph g( edges.begin(), edges.end(), weights.begin(), nodes.size() ); 00185 size_t root = *(nodes.begin()); 00186 GraphEL tree; 00187 if( usePrim ) { 00188 // Prim's algorithm 00189 vector< graph_traits< boostGraph >::vertex_descriptor > p(N); 00190 prim_minimum_spanning_tree( g, &(p[0]) ); 00191 00192 // Store tree edges in result 00193 for( size_t i = 0; i != p.size(); i++ ) { 00194 if( p[i] != i ) 00195 tree.insert( UEdge( p[i], i ) ); 00196 } 00197 } else { 00198 // Kruskal's algorithm 00199 vector< graph_traits< boostGraph >::edge_descriptor > t; 00200 t.reserve( N - 1 ); 00201 kruskal_minimum_spanning_tree( g, std::back_inserter(t) ); 00202 00203 // Store tree edges in result 00204 for( size_t i = 0; i != t.size(); i++ ) { 00205 size_t v1 = source( t[i], g ); 00206 size_t v2 = target( t[i], g ); 00207 if( v1 != v2 ) 00208 tree.insert( UEdge( v1, v2 ) ); 00209 } 00210 } 00211 00212 // Direct edges in order to obtain a rooted tree 00213 result = RootedTree( tree, root ); 00214 } 00215 return result; 00216 } 00217 00218 00220 00225 template<typename T> RootedTree MaxSpanningTree( const WeightedGraph<T> &G, bool usePrim ) { 00226 if( G.size() == 0 ) 00227 return RootedTree(); 00228 else { 00229 T maxweight = G.begin()->second; 00230 for( typename WeightedGraph<T>::const_iterator it = G.begin(); it != G.end(); it++ ) 00231 if( it->second > maxweight ) 00232 maxweight = it->second; 00233 // make a copy of the graph 00234 WeightedGraph<T> gr( G ); 00235 // invoke MinSpanningTree with negative weights 00236 // (which have to be shifted to satisfy positivity criterion) 00237 for( typename WeightedGraph<T>::iterator it = gr.begin(); it != gr.end(); it++ ) 00238 it->second = maxweight - it->second; 00239 return MinSpanningTree( gr, usePrim ); 00240 } 00241 } 00242 00243 00244 } // end of namespace dai 00245 00246 00247 #endif