1
|
/*
|
2
|
Copyright (c) 2003-2008 Niels Kokholm and Peter Sestoft
|
3
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
4
|
of this software and associated documentation files (the "Software"), to deal
|
5
|
in the Software without restriction, including without limitation the rights
|
6
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
7
|
copies of the Software, and to permit persons to whom the Software is
|
8
|
furnished to do so, subject to the following conditions:
|
9
|
|
10
|
The above copyright notice and this permission notice shall be included in
|
11
|
all copies or substantial portions of the Software.
|
12
|
|
13
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
14
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
15
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
16
|
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
17
|
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
18
|
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
19
|
SOFTWARE.
|
20
|
*/
|
21
|
|
22
|
// C5 example: union find structure 2007-11-23
|
23
|
|
24
|
// Compile with
|
25
|
// csc /r:C5.dll UnionFind.cs
|
26
|
|
27
|
/*
|
28
|
|
29
|
The union-find algorithm (Tarjan 1983) is a fast way to build and
|
30
|
maintain a partition of a set into disjoint subsets. It supports the
|
31
|
following operations on a collection of objects:
|
32
|
|
33
|
* Create a new one-element subset consisting of a single object.
|
34
|
|
35
|
* Union (join) two subsets into one.
|
36
|
|
37
|
* Find the canonical representative of the subset containing a given
|
38
|
object.
|
39
|
|
40
|
Idea: A subset of values of type T, disjoint from other such subsets ,
|
41
|
is represented by an object Subset<T>. A HashDictionary<T, Subset<T>>
|
42
|
maps each value to its subset.
|
43
|
|
44
|
*/
|
45
|
|
46
|
|
47
|
using System;
|
48
|
using System.Text; // Encoding
|
49
|
using C5;
|
50
|
using SCG = System.Collections.Generic;
|
51
|
|
52
|
namespace UnionFind {
|
53
|
class MyTest {
|
54
|
public static void Main(String[] args) {
|
55
|
Eqclass<int> x = Eqclass<int>.Make(3),
|
56
|
y = Eqclass<int>.Make(4),
|
57
|
z = Eqclass<int>.Make(5);
|
58
|
x.Union(y);
|
59
|
y.Union(z);
|
60
|
Console.WriteLine(x.Find().Item);
|
61
|
Console.WriteLine(y.Find().Item);
|
62
|
Console.WriteLine(z.Find().Item);
|
63
|
}
|
64
|
}
|
65
|
|
66
|
|
67
|
// Problem: The link and rank fields are never used at the same
|
68
|
// time. Hence it is tempting to make Eqclass<T> abstract and then
|
69
|
// have two subclasses, one being canonical and containing only a
|
70
|
// rank, the other being a non-canonical and containing only a link.
|
71
|
// However, every subset is born as a Canonical and then may turns
|
72
|
// into a NonCanonical because of Union operations, and this switch
|
73
|
// of class while retaining object identity is not possible (Find
|
74
|
// operations just update the link field; the object remains
|
75
|
// NonCanonical).
|
76
|
|
77
|
// The right thing is to leave Eqclass<T> alone and introduce another
|
78
|
// class hierarchy Node, Canonical : Node, NonCanonical : Node, and
|
79
|
// let Eqclass<T> have a field of type Node that can be updated from
|
80
|
// Canonical to NonCanonical. But this wastes the space that would
|
81
|
// be saved by the subclassing idea.
|
82
|
|
83
|
// Note: Also, this would inadvertently allow two Eqclass<T> objects
|
84
|
// to share a common Node. Java and C# confuse things by tying
|
85
|
// variants (subclasses) together with references (classes). Since
|
86
|
// the languages admit (side) effects, sharing is observable and
|
87
|
// sharability should be decoupled from specialization.
|
88
|
|
89
|
public class Eqclass<T> {
|
90
|
private static HashDictionary<T,Eqclass<T>> dict
|
91
|
= new HashDictionary<T,Eqclass<T>>();
|
92
|
private readonly T item;
|
93
|
private Eqclass<T> link = null;
|
94
|
private int rank = 0;
|
95
|
|
96
|
private Eqclass(T item) {
|
97
|
this.item = item;
|
98
|
}
|
99
|
|
100
|
public static Eqclass<T> Make(T item) {
|
101
|
Eqclass<T> result;
|
102
|
if (!dict.Find(item, out result))
|
103
|
dict[item] = result = new Eqclass<T>(item);
|
104
|
return result;
|
105
|
}
|
106
|
|
107
|
public void Union(Eqclass<T> that) {
|
108
|
Eqclass<T> thatRep = that.Find(), thisRep = this.Find();
|
109
|
if (thatRep != thisRep) {
|
110
|
if (thatRep.rank == thisRep.rank) {
|
111
|
thisRep.link = thatRep;
|
112
|
thatRep.rank++;
|
113
|
} else if (thatRep.rank > thisRep.rank)
|
114
|
thisRep.link = thatRep;
|
115
|
else
|
116
|
thatRep.link = thisRep;
|
117
|
}
|
118
|
}
|
119
|
|
120
|
// Find, with path halving: avoids recursion
|
121
|
|
122
|
public Eqclass<T> Find() {
|
123
|
if (link == null)
|
124
|
return this;
|
125
|
else if (link.link == null)
|
126
|
return link;
|
127
|
else {
|
128
|
// Grandparent, parent, and link
|
129
|
Eqclass<T> pp = this, p = link, plink = p.link;
|
130
|
while (plink != null) {
|
131
|
// Invariant: pp -> p -> plink
|
132
|
pp.link = plink;
|
133
|
pp = p;
|
134
|
p = plink;
|
135
|
plink = p.link;
|
136
|
}
|
137
|
return p;
|
138
|
}
|
139
|
}
|
140
|
|
141
|
public T Item {
|
142
|
get { return item; }
|
143
|
}
|
144
|
}
|
145
|
}
|