libDAI
include/dai/weightedgraph.h
Go to the documentation of this file.
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