1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/johanna/kruskal.h	Wed Mar 03 19:16:48 2004 +0000
     1.3 @@ -0,0 +1,60 @@
     1.4 +// -*- c++ -*- //
     1.5 +#ifndef HUGO_KRUSKAL_H
     1.6 +#define HUGO_KRUSKAL_H
     1.7 +
     1.8 +#include "unionfind.h"
     1.9 +#include <algorithm>
    1.10 +
    1.11 +namespace hugo {
    1.12 +
    1.13 +  template <typename EdgeCostPair> static
    1.14 +  bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
    1.15 +    return a.second < b.second;
    1.16 +  }
    1.17 +
    1.18 +
    1.19 +  template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
    1.20 +
    1.21 +  typename EdgeDoubleMap::ValueType 
    1.22 +  MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap, 
    1.23 +		     EdgeBoolMap& treemap) 
    1.24 +  {
    1.25 +    
    1.26 +    typedef typename EdgeDoubleMap::ValueType EDouble;
    1.27 +    typedef typename Graph::EachEdgeIt EachEdgeIt;
    1.28 +    typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
    1.29 +
    1.30 +
    1.31 +    typedef std::vector<EdgeCostPair> EdgeCostVector;
    1.32 +    EdgeCostVector rank;
    1.33 +
    1.34 +    for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
    1.35 +      rank.push_back(make_pair(e, costmap.get(e)));
    1.36 +    }
    1.37 +
    1.38 +    
    1.39 +    std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
    1.40 +
    1.41 +    typedef typename Graph::NodeMap<int> NodeIntMap;
    1.42 +    typedef typename Graph::NodeIt NodeIt;
    1.43 +    NodeIntMap comp_map(G, -1);
    1.44 +    UnionFind<NodeIt,NodeIntMap> uf(comp_map); 
    1.45 +
    1.46 +    EDouble tot_cost = 0;
    1.47 +    for (typename EdgeCostVector::iterator p = rank.begin(); 
    1.48 +	 p!=rank.end(); ++p ) {
    1.49 +      if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
    1.50 +	treemap.set(p->first, true);
    1.51 +	tot_cost += p->second;
    1.52 +      }
    1.53 +      else {
    1.54 +	treemap.set(p->first, false);
    1.55 +      }
    1.56 +    }
    1.57 +    return tot_cost;
    1.58 +  }
    1.59 +
    1.60 +
    1.61 +} //namespace hugo
    1.62 +
    1.63 +#endif //HUGO_KRUSKAL_H