COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/union_find.h @ 987:87f7c54892df

Last change on this file since 987:87f7c54892df was 987:87f7c54892df, checked in by Alpar Juttner, 19 years ago

Naming changes:

File size: 1.8 KB
Line 
1// -*- C++ -*- //
2/*
3Union-Find structure
4
5* Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
6* minden szobajovo kulcs ertekre, -1 -es ertekkel!
7 
8*/
9#ifndef UNION_FIND_H
10#define UNION_FIND_H
11
12#include <vector>
13//#include <map>
14
15
16namespace lemon {
17 
18  template <typename Key, typename KeyIntMap>
19    class UnionFind {
20    KeyIntMap& pointmap;
21    struct VectorElementType {
22      int boss;
23      int count;
24      VectorElementType(int _boss, int _count){
25        boss = _boss;
26        count = _count;
27      }
28    };
29    std::vector<VectorElementType> container;
30    public:
31     
32    UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){
33     
34    }
35   
36    //Give a component of one point to the structure
37    int addPoint(Key u){
38      int _index = container.size();
39      VectorElementType buf(_index,1);
40      container.push_back(buf);
41      return _index;
42    }
43
44   
45    //Finds the big boss of u
46    int find(Key u){
47      if (pointmap.get(u)==-1){
48        int whoami = addPoint(u);
49        pointmap.set(u, whoami);
50        return whoami;
51      }
52      else{
53        int emp = pointmap.get(u);
54        int boss = container[emp].boss;
55        while(emp != boss){
56          emp = boss;
57          boss = container[emp].boss;
58        }
59        return boss;
60      }
61    }
62
63    //Finds u and v in the structures and merges the comopnents, if not equal
64    bool findAndMerge(Key u,Key v){
65      int bu = find(u);
66      int bv = find(v);
67      if (bu != bv){
68        unio(bu,bv);
69        return true;
70      }
71      else{
72        return false;
73      }
74    }
75
76    //Merges a into b
77    void mergeInto(int a, int b){
78      container[a].boss = b;
79      container[b].count +=  container[a].count;
80    }
81   
82    //Makes the union
83    void unio(int b1, int b2){
84      if (container[b1].count>container[b2].count){
85        mergeInto(b2,b1);
86      }
87      else{
88        mergeInto(b1,b2);
89      }
90    }//unio
91  };
92 
93}//namespace lemon
94#endif
Note: See TracBrowser for help on using the repository browser.