author | alpar |
Thu, 31 Mar 2005 13:30:27 +0000 | |
changeset 1282 | 81e89e2b90d1 |
parent 250 | 81a3d0abe5f3 |
permissions | -rw-r--r-- |
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 |
|
alpar@921 | 10 |
namespace lemon { |
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 |
|
alpar@921 | 59 |
}//namespacc lemon |
athos@250 | 60 |
|
athos@250 | 61 |
#endif |