equal
deleted
inserted
replaced
|
1 /* |
|
2 Kruskal's algorithm to find a spanning tree of minimum weight |
|
3 If the graph is not connected, it gives a forest. |
|
4 */ |
|
5 #ifndef KRUSKAL_H |
|
6 #define KRUSKAL_H |
|
7 |
|
8 #include <union_find.h> |
|
9 |
|
10 namespace hugo { |
|
11 |
|
12 template <typename graph_type, typename T> |
|
13 class Kruskal { |
|
14 |
|
15 |
|
16 //Hasznos typedef-ek |
|
17 typedef typename graph_type::NodeIt NodeIt; |
|
18 typedef typename graph_type::EdgeIt EdgeIt; |
|
19 typedef typename graph_type::EachNodeIt EachNodeIt; |
|
20 typedef typename graph_type::EachEdgeIt EachEdgeIt; |
|
21 typedef typename graph_type::SymEdgeIt SymEdgeIt; |
|
22 |
|
23 //input |
|
24 graph_type& G; |
|
25 typename graph_type::EdgeMap<T> &weight; |
|
26 |
|
27 //Auxilliary variables |
|
28 typename graph_type::NodeMap<int> component(flowG); |
|
29 |
|
30 Kruskal( |
|
31 graph_type& _G, |
|
32 typename graph_type::EdgeMap<T> & _weight) |
|
33 : G(_G), |
|
34 weight(_weight), |
|
35 component(-1) |
|
36 { |
|
37 } |
|
38 |
|
39 /*Originally by Misi.*/ |
|
40 struct Edge_comp |
|
41 { |
|
42 NodeMap<graph_type, T> &d; |
|
43 Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} |
|
44 |
|
45 bool operator()(const NodeIt& u, const NodeIt& v) const |
|
46 { return d.get(u) < d.get(v); } |
|
47 }; |
|
48 |
|
49 |
|
50 //Runs the algorithm |
|
51 void run() { |
|
52 |
|
53 |
|
54 |
|
55 } |
|
56 |
|
57 } |
|
58 |
|
59 }//namespacc hugo |
|
60 |
|
61 #endif |