forked from jgraph/mxgraph
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmxUnionFind.java
More file actions
156 lines (138 loc) · 3.17 KB
/
mxUnionFind.java
File metadata and controls
156 lines (138 loc) · 3.17 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/**
* Copyright (c) 2007, Gaudenz Alder
*/
package com.mxgraph.analysis;
import java.util.Hashtable;
import java.util.Map;
/**
* Implements a union find structure that uses union by rank and path
* compression. The union by rank guarantees worst case find time of O(log N),
* while Tarjan shows that in combination with path compression (halving) the
* average time for an arbitrary sequence of m >= n operations is
* O(m*alpha(m,n)), where alpha is the inverse of the Ackermann function,
* defined as follows:
* <code>alpha(m,n) = min{i >= 1 | A(i, floor(m/n)) > log n} for m >= n >= 1</code>
* Which yields almost constant time for each individual operation.
*/
public class mxUnionFind
{
/**
* Maps from elements to nodes
*/
protected Map<Object, Node> nodes = new Hashtable<Object, Node>();
/**
* Constructs a union find structure and initializes it with the specified
* elements.
*
* @param elements
*/
public mxUnionFind(Object[] elements)
{
for (int i = 0; i < elements.length; i++)
{
nodes.put(elements[i], new Node());
}
}
/**
* Returns the node that represents element.
*/
public Node getNode(Object element)
{
return nodes.get(element);
}
/**
* Returns the set that contains <code>node</code>. This implementation
* provides path compression by halving.
*/
public Node find(Node node)
{
while (node.getParent().getParent() != node.getParent())
{
Node t = node.getParent().getParent();
node.setParent(t);
node = t;
}
return node.getParent();
}
/**
* Unifies the sets <code>a</code> and <code>b</code> in constant time
* using a union by rank on the tree size.
*/
public void union(Node a, Node b)
{
Node set1 = find(a);
Node set2 = find(b);
if (set1 != set2)
{
// Limits the worst case runtime of a find to O(log N)
if (set1.getSize() < set2.getSize())
{
set2.setParent(set1);
set1.setSize(set1.getSize() + set2.getSize());
}
else
{
set1.setParent(set2);
set2.setSize(set1.getSize() + set2.getSize());
}
}
}
/**
* Returns true if element a and element b are not in the same set. This
* uses getNode and then find to determine the elements set.
*
* @param a The first element to compare.
* @param b The second element to compare.
* @return Returns true if a and b are in the same set.
*
* @see #getNode(Object)
*/
public boolean differ(Object a, Object b)
{
Node set1 = find(getNode(a));
Node set2 = find(getNode(b));
return set1 != set2;
}
/**
* A class that defines the identity of a set.
*/
public class Node
{
/**
* Reference to the parent node. Root nodes point to themselves.
*/
protected Node parent = this;
/**
* The size of the tree. Initial value is 1.
*/
protected int size = 1;
/**
* @return Returns the parent node
*/
public Node getParent()
{
return parent;
}
/**
* @param parent The parent node to set.
*/
public void setParent(Node parent)
{
this.parent = parent;
}
/**
* @return Returns the size.
*/
public int getSize()
{
return size;
}
/**
* @param size The size to set.
*/
public void setSize(int size)
{
this.size = size;
}
}
}