athos@250: /*
athos@250: Kruskal's algorithm to find a spanning tree of minimum weight
athos@250: If the graph is not connected, it gives a forest. 
athos@250: */
athos@250: #ifndef KRUSKAL_H
athos@250: #define KRUSKAL_H
athos@250: 
athos@250: #include <union_find.h>
athos@250: 
athos@250: namespace hugo {
athos@250:   
athos@250:   template <typename graph_type, typename T>
athos@250:     class Kruskal {
athos@250: 
athos@250:     
athos@250:     //Hasznos typedef-ek
athos@250:     typedef typename graph_type::NodeIt NodeIt;
athos@250:     typedef typename graph_type::EdgeIt EdgeIt;
athos@250:     typedef typename graph_type::EachNodeIt EachNodeIt;
athos@250:     typedef typename graph_type::EachEdgeIt EachEdgeIt;
athos@250:     typedef typename graph_type::SymEdgeIt SymEdgeIt;
athos@250: 
athos@250:     //input
athos@250:     graph_type& G;
athos@250:     typename graph_type::EdgeMap<T> &weight;
athos@250: 
athos@250:     //Auxilliary variables
athos@250:     typename graph_type::NodeMap<int> component(flowG);
athos@250: 
athos@250:     Kruskal(
athos@250: 	    graph_type& _G, 
athos@250: 	    typename graph_type::EdgeMap<T> & _weight)
athos@250:       : G(_G),
athos@250:       weight(_weight),
athos@250:       component(-1)
athos@250:       { 
athos@250:       }
athos@250: 
athos@250:       /*Originally by Misi.*/
athos@250:       struct Edge_comp
athos@250:       {
athos@250: 	NodeMap<graph_type, T> &d;
athos@250: 	Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 
athos@250: 	
athos@250: 	bool operator()(const NodeIt& u, const NodeIt& v) const 
athos@250: 	{ return d.get(u) < d.get(v); }
athos@250:       };
athos@250: 
athos@250: 
athos@250:       //Runs the algorithm
athos@250:       void run() {
athos@250: 	
athos@250: 
athos@250: 	
athos@250:       }
athos@250:      
athos@250:   }
athos@250: 
athos@250: }//namespacc hugo
athos@250: 
athos@250: #endif