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