While exploring the implementation of AIKruskal I looked at the class AIDisjointSetNode.
The union operation currently attaches one root to another:
root1 := aDSNode find.
root2 := self find.
root1 = root2 ifTrue: [ ^ self ].
root1 parent: root2
The find method already performs path compression, but union does not appear to use rank or size heuristics.
It might be interesting to experiment with adding a rank field and implementing union-by-rank, then benchmarking its effect on algorithms such as Kruskal.
While exploring the implementation of AIKruskal I looked at the class AIDisjointSetNode.
The union operation currently attaches one root to another:
The find method already performs path compression, but union does not appear to use rank or size heuristics.
It might be interesting to experiment with adding a rank field and implementing union-by-rank, then benchmarking its effect on algorithms such as Kruskal.