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 # Data structure to keeps track of elements partitioned into disjoint subsets
15 # var s = new DisjointSet[Int]
18 # assert not s.in_same_subset(1,2)
20 # assert s.in_same_subset(1,2)
22 # `in_same_subset` is transitive, reflexive and symetric
25 # assert not s.in_same_subset(1,3)
27 # assert s.in_same_subset(1,3)
29 # Unkike theorical Disjoint-set data structures, the underling implementation is opaque
30 # that makes the traditionnal `find` method unavailable for clients.
31 # The methods `in_same_subset`, `to_partitions`, and their variations are offered instead.
32 class DisjointSet[E
: Object]
33 super SimpleCollection[E
]
35 # The node in the hiearchical structure for each element
36 private var nodes
= new HashMap[E
, DisjointSetNode]
38 # Get the root node of an element
40 private fun find
(e
:E
): DisjointSetNode
42 assert nodes
.has_key
(e
)
44 if ne
.parent
== ne
then return ne
50 # Get the root node of a node
51 # Use *path compression* to flatten the structure
52 # ENSURE: `result.parent == result`
53 private fun nfind
(ne
: DisjointSetNode): DisjointSetNode
56 if nf
== ne
then return ne
62 # Is the element in the structure
64 # var s = new DisjointSet[Int]
69 redef fun has
(e
: E
): Bool
71 return nodes
.has_key
(e
)
74 redef fun iterator
do return nodes
.keys
.iterator
76 # Add a new element in the structure.
77 # Initially it is in its own disjoint subset
82 if nodes
.has_key
(e
) then return
83 var ne
= new DisjointSetNode
87 # Are two elements in the same subset?
88 fun in_same_subset
(e
,f
:E
): Bool
90 return e
== f
or find
(e
) == find
(f
)
93 # Are all elements of `es` in the same subset?
94 # var s = new DisjointSet[Int]
95 # s.add_all([1,2,3,4,5,6])
96 # s.union_all([1,2,3])
97 # assert not s.all_in_same_subset([2,3,4])
98 # s.union_all([1,4,5])
99 # assert s.all_in_same_subset([2,3,4])
100 fun all_in_same_subset
(es
: Collection[E
]): Bool
102 if es
.is_empty
then return true
103 var nf
= find
(es
.first
)
106 if ne
!= nf
then return false
111 # Construct the current partitionning
113 # var s = new DisjointSet[Int]
114 # s.add_all([1,2,3,4,5,6])
118 # var p = s.to_partitions
119 # assert p.length == 3
120 fun to_partitions
: Collection[Set[E
]]
122 return to_subpartition
(self)
125 # Construct a partitionning on `es`, a subset of elements
127 # var s = new DisjointSet[Int]
128 # s.add_all([1,2,3,4,5,6])
132 # var p = s.to_subpartition([1,2,4])
133 # assert p.length == 2
134 fun to_subpartition
(es
: Collection[E
]): Collection[Set[E
]]
136 var map
= new HashMap[DisjointSetNode, Set[E
]]
139 var set
= map
.get_or_null
(ne
)
149 # Combine the subsets of `e` and `f`
150 # ENSURE: `in_same_subset(e,f)`
155 if ne
== nf
then return
157 # merge them using *union by rank*
158 # attach the smaller tree to the root of the deeper tree
168 # The only case where the deep is increased is when both are equals
174 # Combine the subsets of all elements of `es`
175 # ENSURE: `all_in_same_subset(cs)`
176 fun union_all
(es
:Collection[E
])
178 if es
.is_empty
then return
180 for e
in es
do union
(e
,f
)
184 # A node in the hierarchical representation of subsets
185 private class DisjointSetNode
186 # If parent == self then the node is a root
187 var parent
: DisjointSetNode = self
189 # The rank to no desequilibrate the structure.
190 # The term rank is used instead of depth since
191 # path compression is used, see `DisjointSet::nfind`