COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/johanna/unionfind.h @ 354:0e8eb96c22ca

Last change on this file since 354:0e8eb96c22ca 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.