1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # This file is free software, which comes along with NIT. This software is
4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
5 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
6 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
7 # is kept unaltered, and a notification of the changes is added.
8 # You are allowed to redistribute it and sell it, alone or is a part of
11 # union–find algorithm using an efficient disjoint-set data structure
14 import hash_collection
16 # Data structure to keeps track of elements partitioned into disjoint subsets
17 # var s = new DisjointSet[Int]
20 # assert not s.in_same_subset(1,2)
22 # assert s.in_same_subset(1,2)
24 # `in_same_subset` is transitive, reflexive and symetric
27 # assert not s.in_same_subset(1,3)
29 # assert s.in_same_subset(1,3)
31 # Unkike theorical Disjoint-set data structures, the underling implementation is opaque
32 # that makes the traditionnal `find` method unavailable for clients.
33 # The methods `in_same_subset`, `to_partitions`, and their variations are offered instead.
35 super SimpleCollection[E
]
38 # The node in the hiearchical structure for each element
39 private var nodes
= new HashMap[E
, DisjointSetNode]
42 init from
(other
: DisjointSet[E
])
44 # Associate a root node in other to the associated root node in self
45 var map
= new HashMap[DisjointSetNode, DisjointSetNode]
46 for e
, v
in other
.nodes
do
47 # Create the associated node
48 var n2
= new DisjointSetNode
51 # Get the root node in other and the associated one in self
53 var p2
= map
.get_or_null
(p
)
55 # if no associated root node, then a new subset is created
57 number_of_subsets
+= 1
59 # else attach the new node to the subset of the root node
67 # var s = new DisjointSet[Int]
68 # s.add_all([1,2,3,4,5])
69 # s.union_all([1,4,5])
71 # assert s2.number_of_subsets == 3
72 # assert s2.all_in_same_subset([1,4,5]) == true
73 # assert s2.in_same_subset(1,2) == false
74 redef fun clone
do return new DisjointSet[E
].from
(self)
76 # The number of subsets in the partition
78 # var s = new DisjointSet[Int]
79 # s.add_all([1,2,3,4,5])
80 # assert s.number_of_subsets == 5
81 # s.union_all([1,4,5])
82 # assert s.number_of_subsets == 3
84 # assert s.number_of_subsets == 3
85 var number_of_subsets
: Int = 0
87 # Get the root node of an element
89 private fun find
(e
:E
): DisjointSetNode
91 assert nodes
.has_key
(e
)
93 if ne
.parent
== ne
then return ne
99 # Get the root node of a node
100 # Use *path compression* to flatten the structure
101 # ENSURE: `result.parent == result`
102 private fun nfind
(ne
: DisjointSetNode): DisjointSetNode
105 if nf
== ne
then return ne
111 # Is the element in the structure
113 # var s = new DisjointSet[Int]
114 # assert not s.has(1)
117 # assert not s.has(2)
119 return nodes
.has_key
(e
)
122 redef fun iterator
do return nodes
.keys
.iterator
124 # Add a new element in the structure.
125 # Initially it is in its own disjoint subset
129 if nodes
.has_key
(e
) then return
130 var ne
= new DisjointSetNode
132 number_of_subsets
+= 1
135 # Are two elements in the same subset?
136 fun in_same_subset
(e
,f
:E
): Bool
138 return e
== f
or find
(e
) == find
(f
)
141 # Are all elements of `es` in the same subset?
142 # var s = new DisjointSet[Int]
143 # s.add_all([1,2,3,4,5,6])
144 # s.union_all([1,2,3])
145 # assert not s.all_in_same_subset([2,3,4])
146 # s.union_all([1,4,5])
147 # assert s.all_in_same_subset([2,3,4])
148 fun all_in_same_subset
(es
: Collection[E
]): Bool
150 if es
.is_empty
then return true
151 var nf
= find
(es
.first
)
154 if ne
!= nf
then return false
159 # Construct the current partitionning
161 # var s = new DisjointSet[Int]
162 # s.add_all([1,2,3,4,5,6])
166 # var p = s.to_partitions
167 # assert p.length == 3
168 fun to_partitions
: Collection[Set[E
]]
170 return to_subpartition
(self)
173 # Construct a partitionning on `es`, a subset of elements
175 # var s = new DisjointSet[Int]
176 # s.add_all([1,2,3,4,5,6])
180 # var p = s.to_subpartition([1,2,4])
181 # assert p.length == 2
182 fun to_subpartition
(es
: Collection[E
]): Collection[Set[E
]]
184 var map
= new HashMap[DisjointSetNode, Set[E
]]
187 var set
= map
.get_or_null
(ne
)
197 # Combine the subsets of `e` and `f`
198 # ENSURE: `in_same_subset(e,f)`
203 if ne
== nf
then return
205 # merge them using *union by rank*
206 # attach the smaller tree to the root of the deeper tree
216 # The only case where the deep is increased is when both are equals
220 number_of_subsets
-= 1
223 # Combine the subsets of all elements of `es`
224 # ENSURE: `all_in_same_subset(cs)`
225 fun union_all
(es
:Collection[E
])
227 if es
.is_empty
then return
229 for e
in es
do union
(e
,f
)
233 # A node in the hierarchical representation of subsets
234 private class DisjointSetNode
235 # If parent == self then the node is a root
236 var parent
: DisjointSetNode = self
238 # The rank to no desequilibrate the structure.
239 # The term rank is used instead of depth since
240 # path compression is used, see `DisjointSet::nfind`