COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/kruskal.h @ 218:5964f1c64ca1

Last change on this file since 218:5964f1c64ca1 was 218:5964f1c64ca1, checked in by beckerjc, 18 years ago

unionfind: componentSize tagfv

kruskal: osztalyositva; lehet beadni sajat elorendezett el-koltseg vektort

nem tul elegans megoldas...

File size: 1.8 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
11  template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
12  class MinCostTreeKruskal
13  {
14
15    typedef typename Graph::EdgeIt EdgeIt;
16    typedef typename Graph::Edge Edge;
17
18  public:
19    typedef typename EdgeCostMap::ValueType EdgeCost;
20    typedef std::pair<Edge, EdgeCost> EdgeCostPair;
21    typedef std::vector<EdgeCostPair> EdgeCostVector;
22   
23  private:
24    Graph const &G;
25    EdgeCostMap const &costmap;
26    EdgeBoolMap& treemap;
27   
28    //template <typename EdgeCostPair>
29    class comparePair {
30    public:
31      bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) {
32        return a.second < b.second;
33      }
34    };
35
36  public:
37
38
39    MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap,
40                       EdgeBoolMap& _treemap) : G(_G), costmap(_costmap),
41                                                treemap(_treemap) {}
42 
43
44    EdgeCost run()
45    {
46     EdgeCostVector rank;
47     for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
48        rank.push_back(make_pair(e, costmap.get(e)));
49      }
50     
51      std::sort(rank.begin(), rank.end(), comparePair());
52
53      return run(rank);
54   
55    }
56
57    EdgeCost run(EdgeCostVector const &rank)
58    {
59      typedef typename Graph::NodeMap<int> NodeIntMap;
60      typedef typename Graph::Node Node;
61      NodeIntMap comp_map(G, -1);
62      UnionFind<Node,NodeIntMap> uf(comp_map);
63     
64      EdgeCost tot_cost = 0;
65      for (typename EdgeCostVector::const_iterator p = rank.begin();
66           p!=rank.end(); ++p ) {
67        if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
68          treemap.set(p->first, true);
69          tot_cost += p->second;
70        }
71        else {
72          treemap.set(p->first, false);
73        }
74      }
75      return tot_cost;
76
77    }
78
79  };
80
81
82} //namespace hugo
83
84#endif //HUGO_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.