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 keep track of elements partitioned into disjoint subsets
18 # var s = new DisjointSet[Int]
21 # assert not s.in_same_subset(1,2)
23 # assert s.in_same_subset(1,2)
25 # `in_same_subset` is transitive, reflexive and symmetric
28 # assert not s.in_same_subset(1,3)
30 # assert s.in_same_subset(1,3)
32 # Unlike theoretical Disjoint-set data structures, the underling implementation is opaque
33 # making the traditional `find` method unavailable for clients.
34 # The methods `in_same_subset`, `to_partitions`, and their variations are offered instead.
36 super SimpleCollection[E
]
39 # The node in the hiearchical structure for each element
40 private var nodes
= new HashMap[E
, DisjointSetNode]
43 init from
(other
: DisjointSet[E
])
45 # Associate a root node in other to the associated root node in self
46 var map
= new HashMap[DisjointSetNode, DisjointSetNode]
47 for e
, v
in other
.nodes
do
48 # Create the associated node
49 var n2
= new DisjointSetNode
52 # Get the root node in other and the associated one in self
54 var p2
= map
.get_or_null
(p
)
56 # if no associated root node, then a new subset is created
58 number_of_subsets
+= 1
60 # else attach the new node to the subset of the root node
68 # var s = new DisjointSet[Int]
69 # s.add_all([1,2,3,4,5])
70 # s.union_all([1,4,5])
72 # assert s2.number_of_subsets == 3
73 # assert s2.all_in_same_subset([1,4,5]) == true
74 # assert s2.in_same_subset(1,2) == false
75 redef fun clone
do return new DisjointSet[E
].from
(self)
77 # The number of subsets in the partition
79 # var s = new DisjointSet[Int]
80 # s.add_all([1,2,3,4,5])
81 # assert s.number_of_subsets == 5
82 # s.union_all([1,4,5])
83 # assert s.number_of_subsets == 3
85 # assert s.number_of_subsets == 3
86 var number_of_subsets
: Int = 0
88 # Get the root node of an element
90 private fun find
(e
:E
): DisjointSetNode
92 assert nodes
.has_key
(e
)
94 if ne
.parent
== ne
then return ne
100 # Get the root node of a node
101 # Use *path compression* to flatten the structure
102 # ENSURE: `result.parent == result`
103 private fun nfind
(ne
: DisjointSetNode): DisjointSetNode
106 if nf
== ne
then return ne
112 # Is the element in the structure
114 # var s = new DisjointSet[Int]
115 # assert not s.has(1)
118 # assert not s.has(2)
120 return nodes
.has_key
(e
)
123 redef fun iterator
do return nodes
.keys
.iterator
125 # Add a new element in the structure.
126 # Initially it is in its own disjoint subset
130 if nodes
.has_key
(e
) then return
131 var ne
= new DisjointSetNode
133 number_of_subsets
+= 1
136 # Are two elements in the same subset?
137 fun in_same_subset
(e
,f
:E
): Bool
139 return e
== f
or find
(e
) == find
(f
)
142 # Are all elements of `es` in the same subset?
144 # var s = new DisjointSet[Int]
145 # s.add_all([1,2,3,4,5,6])
146 # s.union_all([1,2,3])
147 # assert not s.all_in_same_subset([2,3,4])
148 # s.union_all([1,4,5])
149 # assert s.all_in_same_subset([2,3,4])
150 fun all_in_same_subset
(es
: Collection[E
]): Bool
152 if es
.is_empty
then return true
153 var nf
= find
(es
.first
)
156 if ne
!= nf
then return false
161 # Construct the current partitionning
163 # var s = new DisjointSet[Int]
164 # s.add_all([1,2,3,4,5,6])
168 # var p = s.to_partitions
169 # assert p.length == 3
170 fun to_partitions
: Collection[Set[E
]]
172 return to_subpartition
(self)
175 # Construct a partitioning on `es`, a subset of elements
177 # var s = new DisjointSet[Int]
178 # s.add_all([1,2,3,4,5,6])
182 # var p = s.to_subpartition([1,2,4])
183 # assert p.length == 2
184 fun to_subpartition
(es
: Collection[E
]): Collection[Set[E
]]
186 var map
= new HashMap[DisjointSetNode, Set[E
]]
189 var set
= map
.get_or_null
(ne
)
199 # Combine the subsets of `e` and `f`
200 # ENSURE: `in_same_subset(e,f)`
205 if ne
== nf
then return
207 # merge them using *union by rank*
208 # attach the smaller tree to the root of the deeper tree
218 # The only case where the deep is increased is when both are equals
222 number_of_subsets
-= 1
225 # Combine the subsets of all elements of `es`
226 # ENSURE: `all_in_same_subset(cs)`
227 fun union_all
(es
:Collection[E
])
229 if es
.is_empty
then return
231 for e
in es
do union
(e
,f
)
235 # A node in the hierarchical representation of subsets
236 private class DisjointSetNode
237 # If parent == self then the node is a root
238 var parent
: DisjointSetNode = self
240 # The rank to keep the structure balanced.
241 # The term rank is used instead of depth since
242 # path compression is used, see `DisjointSet::nfind`