source: lemon-0.x/src/work/athos/kruskal.h @ 1211:73912ba03d83

/*
Kruskal's algorithm to find a spanning tree of minimum weight
If the graph is not connected, it gives a forest. 
*/
#ifndef KRUSKAL_H
#define KRUSKAL_H

#include <union_find.h>

namespace lemon {
  
  template <typename graph_type, typename T>
    class Kruskal {

    
    //Hasznos typedef-ek
    typedef typename graph_type::NodeIt NodeIt;
    typedef typename graph_type::EdgeIt EdgeIt;
    typedef typename graph_type::EachNodeIt EachNodeIt;
    typedef typename graph_type::EachEdgeIt EachEdgeIt;
    typedef typename graph_type::SymEdgeIt SymEdgeIt;

    //input
    graph_type& G;
    typename graph_type::EdgeMap<T> &weight;

    //Auxilliary variables
    typename graph_type::NodeMap<int> component(flowG);

    Kruskal(
            graph_type& _G, 
            typename graph_type::EdgeMap<T> & _weight)
      : G(_G),
      weight(_weight),
      component(-1)
      { 
      }

      /*Originally by Misi.*/
      struct Edge_comp
      {
        NodeMap<graph_type, T> &d;
        Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 
        
        bool operator()(const NodeIt& u, const NodeIt& v) const 
        { return d.get(u) < d.get(v); }
      };


      //Runs the algorithm
      void run() {
        

        
      }
     
  }

}//namespacc lemon

#endif