source:lemon-0.x/src/work/athos/kruskal.h@510:72143568cadc

Last change on this file since 510:72143568cadc was 250:81a3d0abe5f3, checked in by athos, 18 years ago

Hozzáadtam pár dolgot, mielőtt áttérünk az svn-re.

File size: 1.2 KB
RevLine
[250]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 hugo {
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 hugo
60
61#endif
Note: See TracBrowser for help on using the repository browser.