COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/kruskal.h @ 921:818510fa3d99

Last change on this file since 921:818510fa3d99 was 921:818510fa3d99, checked in by Alpar Juttner, 15 years ago

hugo -> lemon

File size: 1.2 KB
Line 
1/*
2Kruskal's algorithm to find a spanning tree of minimum weight
3If 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
10namespace lemon {
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 lemon
60
61#endif
Note: See TracBrowser for help on using the repository browser.