# source:lemon-0.x/src/work/johanna/kruskal.h@194:a1680b3c516c

Last change on this file since 194:a1680b3c516c was 150:4b5210aa0239, checked in by beckerjc, 20 years ago

Unió-HolVan? struktúra,
Kruskal algoritmus,
hozzávaló kis tesztfájl és Makefile.

File size: 1.5 KB
Line
1// -*- c++ -*- //
2#ifndef HUGO_KRUSKAL_H
3#define HUGO_KRUSKAL_H
4
5#include "unionfind.h"
6#include <algorithm>
7
8namespace hugo {
9
10  template <typename EdgeCostPair> static
11  bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
12    return a.second < b.second;
13  }
14
15
16  template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
17
18  typename EdgeDoubleMap::ValueType
19  MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap,
20                     EdgeBoolMap& treemap)
21  {
22
23    typedef typename EdgeDoubleMap::ValueType EDouble;
24    typedef typename Graph::EachEdgeIt EachEdgeIt;
25    typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
26
27
28    typedef std::vector<EdgeCostPair> EdgeCostVector;
29    EdgeCostVector rank;
30
31    for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
32      rank.push_back(make_pair(e, costmap.get(e)));
33    }
34
35
36    std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
37
38    typedef typename Graph::NodeMap<int> NodeIntMap;
39    typedef typename Graph::NodeIt NodeIt;
40    NodeIntMap comp_map(G, -1);
41    UnionFind<NodeIt,NodeIntMap> uf(comp_map);
42
43    EDouble tot_cost = 0;
44    for (typename EdgeCostVector::iterator p = rank.begin();
45         p!=rank.end(); ++p ) {
46      if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
47        treemap.set(p->first, true);
48        tot_cost += p->second;
49      }
50      else {
51        treemap.set(p->first, false);
52      }
53    }