COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/unionfind.h @ 392:b8d635e1672d

Last change on this file since 392:b8d635e1672d was 349:42c660f58702, checked in by beckerjc, 17 years ago

Kruskal lenyegeben kesz.
Kell meg dokumentalni, meg meg egy par jol hasznalhato wrapper fv.
Es valamit meg kene csinalni azzal, hogy nem const ref. a kimeno boolmap,

viszont sokszor "on-the-fly" akarjuk megkonstrualni (es ilyenkor persze a
const-os mapet is lehet set-elni...)

File size: 1.4 KB
Line 
1// -*- c++ -*- //
2#ifndef HUGO_UNION_FIND_H
3#define HUGO_UNION_FIND_H
4
5#include <vector>
6#include <utility>
7
8namespace hugo {
9
10  template <typename T, typename TIntMap>
11  class UnionFind {
12   
13  public:
14    typedef T ElementType;
15    typedef std::pair<int,int> PairType;
16
17  private:
18    std::vector<PairType> data;
19    TIntMap& map;
20
21  public:
22    UnionFind(TIntMap& m) : map(m) {}
23
24
25    int whichComponent(T a)
26    {
27      int comp0 = map[a];
28      if (comp0 < 0) {
29        return insertNewElement(a);
30      }
31      int comp = comp0;
32      int next;
33      while ( (next = data[comp].first) != comp) {
34        comp = next;
35      }
36      while ( (next = data[comp0].first) != comp) {
37        data[comp0].first = comp;
38        comp0 = next;
39      }
40
41      return comp;
42    }
43
44    int insertNewElement(T a)
45    {
46      int n = data.size();
47      data.push_back(make_pair(n, 1));
48      map.set(a,n);
49      return n;
50    }
51
52    bool joinComponents(T a, T b)
53    {
54      int ca = whichComponent(a);
55      int cb = whichComponent(b);
56
57      if ( ca == cb )
58        return false;
59
60      if ( data[ca].second > data[cb].second ) {
61        data[cb].first = ca;
62        data[ca].second += data[cb].second;
63      }
64      else {
65        data[ca].first = cb;
66        data[cb].second += data[ca].second;
67      }
68      return true;
69    }
70
71    int componentSize(T a)
72    {
73      int ca = whichComponent(a);
74      return data[ca].second;
75    }
76
77  };
78
79} //namespace hugo
80
81#endif //HUGO_UNION_FIND_H
Note: See TracBrowser for help on using the repository browser.