Disjoint-set data structure

The main entry point is DisjointSet() which chooses the appropriate type to return. For more on the data structure, see DisjointSet().

This module defines a class for mutable partitioning of a set, which cannot be used as a key of a dictionary, a vertex of a graph, etc. For immutable partitioning see SetPartition.

AUTHORS:

  • Sébastien Labbé (2008) - Initial version.

  • Sébastien Labbé (2009-11-24) - Pickling support

  • Sébastien Labbé (2010-01) - Inclusion into sage (Issue #6775).

  • Giorgos Mousa (2024-04-22): Optimize

EXAMPLES:

Disjoint set of integers from 0 to n - 1:

sage: s = DisjointSet(6)
sage: s
{{0}, {1}, {2}, {3}, {4}, {5}}
sage: s.union(2, 4)
sage: s.union(1, 3)
sage: s.union(5, 1)
sage: s
{{0}, {1, 3, 5}, {2, 4}}
sage: s.find(3)
1
sage: s.find(5)
1
sage: list(map(s.find, range(6)))
[0, 1, 2, 1, 2, 1]

>>> from sage.all import *
>>> s = DisjointSet(Integer(6))
>>> s
{{0}, {1}, {2}, {3}, {4}, {5}}
>>> s.union(Integer(2), Integer(4))
>>> s.union(Integer(1), Integer(3))
>>> s.union(Integer(5), Integer(1))
>>> s
{{0}, {1, 3, 5}, {2, 4}}
>>> s.find(Integer(3))
1
>>> s.find(Integer(5))
1
>>> list(map(s.find, range(Integer(6))))
[0, 1, 2, 1, 2, 1]

Disjoint set of hashables objects:

sage: d = DisjointSet('abcde')
sage: d
{{'a'}, {'b'}, {'c'}, {'d'}, {'e'}}
sage: d.union('a', 'b')
sage: d.union('b', 'c')
sage: d.union('c', 'd')
sage: d
{{'a', 'b', 'c', 'd'}, {'e'}}
sage: d.find('c')
'a'

>>> from sage.all import *
>>> d = DisjointSet('abcde')
>>> d
{{'a'}, {'b'}, {'c'}, {'d'}, {'e'}}
>>> d.union('a', 'b')
>>> d.union('b', 'c')
>>> d.union('c', 'd')
>>> d
{{'a', 'b', 'c', 'd'}, {'e'}}
>>> d.find('c')
'a'
sage.sets.disjoint_set.DisjointSet(arg)[source]

Construct a disjoint set where each element of arg is in its own set. If arg is an integer, then the disjoint set returned is made of the integers from 0 to arg - 1.

A disjoint-set data structure (sometimes called union-find data structure) is a data structure that keeps track of a partitioning of a set into a number of separate, nonoverlapping sets. It performs two operations:

  • find() – Determine which set a particular element is in.

  • union() – Combine or merge two sets into a single set.

REFERENCES:

INPUT:

  • arg – nonnegative integer or an iterable of hashable objects

EXAMPLES:

From a nonnegative integer:

sage: DisjointSet(5)
{{0}, {1}, {2}, {3}, {4}}

>>> from sage.all import *
>>> DisjointSet(Integer(5))
{{0}, {1}, {2}, {3}, {4}}

From an iterable:

sage: DisjointSet('abcde')
{{'a'}, {'b'}, {'c'}, {'d'}, {'e'}}
sage: DisjointSet(range(6))
{{0}, {1}, {2}, {3}, {4}, {5}}
sage: DisjointSet(['yi', 45, 'cheval'])
{{'cheval'}, {'yi'}, {45}}

>>> from sage.all import *
>>> DisjointSet('abcde')
{{'a'}, {'b'}, {'c'}, {'d'}, {'e'}}
>>> DisjointSet(range(Integer(6)))
{{0}, {1}, {2}, {3}, {4}, {5}}
>>> DisjointSet(['yi', Integer(45), 'cheval'])
{{'cheval'}, {'yi'}, {45}}

From a set partition (see Issue #38693):

sage: SP = SetPartition(DisjointSet(5))
sage: DisjointSet(SP)
{{0}, {1}, {2}, {3}, {4}}
sage: DisjointSet(SP) == DisjointSet(5)
True

>>> from sage.all import *
>>> SP = SetPartition(DisjointSet(Integer(5)))
>>> DisjointSet(SP)
{{0}, {1}, {2}, {3}, {4}}
>>> DisjointSet(SP) == DisjointSet(Integer(5))
True
class sage.sets.disjoint_set.DisjointSet_class[source]

Bases: SageObject

Common class and methods for DisjointSet_of_integers and DisjointSet_of_hashables.

cardinality()[source]

Return the number of elements in self, not the number of subsets.

EXAMPLES:

sage: d = DisjointSet(5)
sage: d.cardinality()
5
sage: d.union(2, 4)
sage: d.cardinality()
5
sage: d = DisjointSet(range(5))
sage: d.cardinality()
5
sage: d.union(2, 4)
sage: d.cardinality()
5

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> d.cardinality()
5
>>> d.union(Integer(2), Integer(4))
>>> d.cardinality()
5
>>> d = DisjointSet(range(Integer(5)))
>>> d.cardinality()
5
>>> d.union(Integer(2), Integer(4))
>>> d.cardinality()
5
number_of_subsets()[source]

Return the number of subsets in self.

EXAMPLES:

sage: d = DisjointSet(5)
sage: d.number_of_subsets()
5
sage: d.union(2, 4)
sage: d.number_of_subsets()
4
sage: d = DisjointSet(range(5))
sage: d.number_of_subsets()
5
sage: d.union(2, 4)
sage: d.number_of_subsets()
4

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> d.number_of_subsets()
5
>>> d.union(Integer(2), Integer(4))
>>> d.number_of_subsets()
4
>>> d = DisjointSet(range(Integer(5)))
>>> d.number_of_subsets()
5
>>> d.union(Integer(2), Integer(4))
>>> d.number_of_subsets()
4
class sage.sets.disjoint_set.DisjointSet_of_hashables[source]

Bases: DisjointSet_class

Disjoint set of hashables.

EXAMPLES:

sage: d = DisjointSet('abcde')
sage: d
{{'a'}, {'b'}, {'c'}, {'d'}, {'e'}}
sage: d.union('a', 'c')
sage: d
{{'a', 'c'}, {'b'}, {'d'}, {'e'}}
sage: d.find('a')
'a'

>>> from sage.all import *
>>> d = DisjointSet('abcde')
>>> d
{{'a'}, {'b'}, {'c'}, {'d'}, {'e'}}
>>> d.union('a', 'c')
>>> d
{{'a', 'c'}, {'b'}, {'d'}, {'e'}}
>>> d.find('a')
'a'
element_to_root_dict()[source]

Return the dictionary where the keys are the elements of self and the values are their representative inside a list.

EXAMPLES:

sage: d = DisjointSet(range(5))
sage: d.union(2, 3)
sage: d.union(4, 1)
sage: e = d.element_to_root_dict()
sage: sorted(e.items())
[(0, 0), (1, 4), (2, 2), (3, 2), (4, 4)]
sage: WordMorphism(e)                                                       # needs sage.combinat
WordMorphism: 0->0, 1->4, 2->2, 3->2, 4->4

>>> from sage.all import *
>>> d = DisjointSet(range(Integer(5)))
>>> d.union(Integer(2), Integer(3))
>>> d.union(Integer(4), Integer(1))
>>> e = d.element_to_root_dict()
>>> sorted(e.items())
[(0, 0), (1, 4), (2, 2), (3, 2), (4, 4)]
>>> WordMorphism(e)                                                       # needs sage.combinat
WordMorphism: 0->0, 1->4, 2->2, 3->2, 4->4
find(e)[source]

Return the representative of the set that e currently belongs to.

INPUT:

  • e – element in self

EXAMPLES:

sage: e = DisjointSet(range(5))
sage: e.union(4, 2)
sage: e
{{0}, {1}, {2, 4}, {3}}
sage: e.find(2)
4
sage: e.find(4)
4
sage: e.union(1,3)
sage: e
{{0}, {1, 3}, {2, 4}}
sage: e.find(1)
1
sage: e.find(3)
1
sage: e.union(3, 2)
sage: e
{{0}, {1, 2, 3, 4}}
sage: [e.find(i) for i in range(5)]
[0, 1, 1, 1, 1]
sage: e.find(5)
Traceback (most recent call last):
...
KeyError: 5

>>> from sage.all import *
>>> e = DisjointSet(range(Integer(5)))
>>> e.union(Integer(4), Integer(2))
>>> e
{{0}, {1}, {2, 4}, {3}}
>>> e.find(Integer(2))
4
>>> e.find(Integer(4))
4
>>> e.union(Integer(1),Integer(3))
>>> e
{{0}, {1, 3}, {2, 4}}
>>> e.find(Integer(1))
1
>>> e.find(Integer(3))
1
>>> e.union(Integer(3), Integer(2))
>>> e
{{0}, {1, 2, 3, 4}}
>>> [e.find(i) for i in range(Integer(5))]
[0, 1, 1, 1, 1]
>>> e.find(Integer(5))
Traceback (most recent call last):
...
KeyError: 5
make_set(new_elt=None)[source]

Add a new element into a new set containing only the new element.

According to Wikipedia article Disjoint-set_data_structure#Making_new_sets the make_set operation adds a new element into a new set containing only the new element. The new set is added at the end of self.

INPUT:

  • new_elt – (optional) element to add. If \(None\), then an integer is added.

EXAMPLES:

sage: e = DisjointSet('abcde')
sage: e.union('d', 'c')
sage: e.union('c', 'e')
sage: e.make_set('f')
sage: e
{{'a'}, {'b'}, {'c', 'd', 'e'}, {'f'}}
sage: e.union('f', 'b')
sage: e
{{'a'}, {'b', 'f'}, {'c', 'd', 'e'}}
sage: e.make_set('e'); e
{{'a'}, {'b', 'f'}, {'c', 'd', 'e'}}
sage: e.make_set(); e
{{'a'}, {'b', 'f'}, {'c', 'd', 'e'}, {6}}

>>> from sage.all import *
>>> e = DisjointSet('abcde')
>>> e.union('d', 'c')
>>> e.union('c', 'e')
>>> e.make_set('f')
>>> e
{{'a'}, {'b'}, {'c', 'd', 'e'}, {'f'}}
>>> e.union('f', 'b')
>>> e
{{'a'}, {'b', 'f'}, {'c', 'd', 'e'}}
>>> e.make_set('e'); e
{{'a'}, {'b', 'f'}, {'c', 'd', 'e'}}
>>> e.make_set(); e
{{'a'}, {'b', 'f'}, {'c', 'd', 'e'}, {6}}
root_to_elements_dict()[source]

Return the dictionary where the keys are the roots of self and the values are the elements in the same set.

EXAMPLES:

sage: d = DisjointSet(range(5))
sage: d.union(2, 3)
sage: d.union(4, 1)
sage: e = d.root_to_elements_dict()
sage: sorted(e.items())
[(0, [0]), (2, [2, 3]), (4, [1, 4])]

>>> from sage.all import *
>>> d = DisjointSet(range(Integer(5)))
>>> d.union(Integer(2), Integer(3))
>>> d.union(Integer(4), Integer(1))
>>> e = d.root_to_elements_dict()
>>> sorted(e.items())
[(0, [0]), (2, [2, 3]), (4, [1, 4])]
to_digraph()[source]

Return the current digraph of self where \((a, b)\) is an oriented edge if \(b\) is the parent of \(a\).

EXAMPLES:

sage: d = DisjointSet(range(5))
sage: d.union(2, 3)
sage: d.union(4, 1)
sage: d.union(3, 4)
sage: d
{{0}, {1, 2, 3, 4}}
sage: g = d.to_digraph()
sage: g                                                                     # needs sage.graphs
Looped digraph on 5 vertices
sage: g.edges(sort=True)                                                    # needs sage.graphs
[(0, 0, None), (1, 2, None), (2, 2, None), (3, 2, None), (4, 2, None)]

>>> from sage.all import *
>>> d = DisjointSet(range(Integer(5)))
>>> d.union(Integer(2), Integer(3))
>>> d.union(Integer(4), Integer(1))
>>> d.union(Integer(3), Integer(4))
>>> d
{{0}, {1, 2, 3, 4}}
>>> g = d.to_digraph()
>>> g                                                                     # needs sage.graphs
Looped digraph on 5 vertices
>>> g.edges(sort=True)                                                    # needs sage.graphs
[(0, 0, None), (1, 2, None), (2, 2, None), (3, 2, None), (4, 2, None)]

The result depends on the ordering of the union:

sage: d = DisjointSet(range(5))
sage: d.union(1, 2)
sage: d.union(1, 3)
sage: d.union(1, 4)
sage: d
{{0}, {1, 2, 3, 4}}
sage: d.to_digraph().edges(sort=True)                                       # needs sage.graphs
[(0, 0, None), (1, 1, None), (2, 1, None), (3, 1, None), (4, 1, None)]

>>> from sage.all import *
>>> d = DisjointSet(range(Integer(5)))
>>> d.union(Integer(1), Integer(2))
>>> d.union(Integer(1), Integer(3))
>>> d.union(Integer(1), Integer(4))
>>> d
{{0}, {1, 2, 3, 4}}
>>> d.to_digraph().edges(sort=True)                                       # needs sage.graphs
[(0, 0, None), (1, 1, None), (2, 1, None), (3, 1, None), (4, 1, None)]
union(e, f)[source]

Combine the set of e and the set of f into one.

All elements in those two sets will share the same representative that can be retrieved using find().

INPUT:

  • e – element in self

  • f – element in self

EXAMPLES:

sage: e = DisjointSet('abcde')
sage: e
{{'a'}, {'b'}, {'c'}, {'d'}, {'e'}}
sage: e.union('a', 'b')
sage: e
{{'a', 'b'}, {'c'}, {'d'}, {'e'}}
sage: e.union('c', 'e')
sage: e
{{'a', 'b'}, {'c', 'e'}, {'d'}}
sage: e.union('b', 'e')
sage: e
{{'a', 'b', 'c', 'e'}, {'d'}}
sage: e.union('a', 2**10)
Traceback (most recent call last):
...
KeyError: 1024

>>> from sage.all import *
>>> e = DisjointSet('abcde')
>>> e
{{'a'}, {'b'}, {'c'}, {'d'}, {'e'}}
>>> e.union('a', 'b')
>>> e
{{'a', 'b'}, {'c'}, {'d'}, {'e'}}
>>> e.union('c', 'e')
>>> e
{{'a', 'b'}, {'c', 'e'}, {'d'}}
>>> e.union('b', 'e')
>>> e
{{'a', 'b', 'c', 'e'}, {'d'}}
>>> e.union('a', Integer(2)**Integer(10))
Traceback (most recent call last):
...
KeyError: 1024
class sage.sets.disjoint_set.DisjointSet_of_integers[source]

Bases: DisjointSet_class

Disjoint set of integers from 0 to n-1.

EXAMPLES:

sage: d = DisjointSet(5)
sage: d
{{0}, {1}, {2}, {3}, {4}}
sage: d.union(2, 4)
sage: d.union(0, 2)
sage: d
{{0, 2, 4}, {1}, {3}}
sage: d.find(2)
2

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> d
{{0}, {1}, {2}, {3}, {4}}
>>> d.union(Integer(2), Integer(4))
>>> d.union(Integer(0), Integer(2))
>>> d
{{0, 2, 4}, {1}, {3}}
>>> d.find(Integer(2))
2
element_to_root_dict()[source]

Return the dictionary where the keys are the elements of self and the values are their representative inside a list.

EXAMPLES:

sage: d = DisjointSet(5)
sage: d.union(2, 3)
sage: d.union(4, 1)
sage: e = d.element_to_root_dict()
sage: e
{0: 0, 1: 4, 2: 2, 3: 2, 4: 4}
sage: WordMorphism(e)                                                       # needs sage.combinat
WordMorphism: 0->0, 1->4, 2->2, 3->2, 4->4

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> d.union(Integer(2), Integer(3))
>>> d.union(Integer(4), Integer(1))
>>> e = d.element_to_root_dict()
>>> e
{0: 0, 1: 4, 2: 2, 3: 2, 4: 4}
>>> WordMorphism(e)                                                       # needs sage.combinat
WordMorphism: 0->0, 1->4, 2->2, 3->2, 4->4
find(i)[source]

Return the representative of the set that i currently belongs to.

INPUT:

  • i – element in self

EXAMPLES:

sage: e = DisjointSet(5)
sage: e.union(4, 2)
sage: e
{{0}, {1}, {2, 4}, {3}}
sage: e.find(2)
4
sage: e.find(4)
4
sage: e.union(1, 3)
sage: e
{{0}, {1, 3}, {2, 4}}
sage: e.find(1)
1
sage: e.find(3)
1
sage: e.union(3, 2)
sage: e
{{0}, {1, 2, 3, 4}}
sage: [e.find(i) for i in range(5)]
[0, 1, 1, 1, 1]
sage: e.find(2**10)
Traceback (most recent call last):
...
ValueError: i must be between 0 and 4 (1024 given)

>>> from sage.all import *
>>> e = DisjointSet(Integer(5))
>>> e.union(Integer(4), Integer(2))
>>> e
{{0}, {1}, {2, 4}, {3}}
>>> e.find(Integer(2))
4
>>> e.find(Integer(4))
4
>>> e.union(Integer(1), Integer(3))
>>> e
{{0}, {1, 3}, {2, 4}}
>>> e.find(Integer(1))
1
>>> e.find(Integer(3))
1
>>> e.union(Integer(3), Integer(2))
>>> e
{{0}, {1, 2, 3, 4}}
>>> [e.find(i) for i in range(Integer(5))]
[0, 1, 1, 1, 1]
>>> e.find(Integer(2)**Integer(10))
Traceback (most recent call last):
...
ValueError: i must be between 0 and 4 (1024 given)

Note

This method performs input checks. To avoid them you may directly use OP_find().

make_set()[source]

Add a new element into a new set containing only the new element.

According to Wikipedia article Disjoint-set_data_structure#Making_new_sets the make_set operation adds a new element into a new set containing only the new element. The new set is added at the end of self.

EXAMPLES:

sage: d = DisjointSet(5)
sage: d.union(1, 2)
sage: d.union(0, 1)
sage: d.make_set()
sage: d
{{0, 1, 2}, {3}, {4}, {5}}
sage: d.find(1)
1

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> d.union(Integer(1), Integer(2))
>>> d.union(Integer(0), Integer(1))
>>> d.make_set()
>>> d
{{0, 1, 2}, {3}, {4}, {5}}
>>> d.find(Integer(1))
1
root_to_elements_dict()[source]

Return the dictionary where the keys are the roots of self and the values are the elements in the same set as the root.

EXAMPLES:

sage: d = DisjointSet(5)
sage: sorted(d.root_to_elements_dict().items())
[(0, [0]), (1, [1]), (2, [2]), (3, [3]), (4, [4])]
sage: d.union(2, 3)
sage: sorted(d.root_to_elements_dict().items())
[(0, [0]), (1, [1]), (2, [2, 3]), (4, [4])]
sage: d.union(3, 0)
sage: sorted(d.root_to_elements_dict().items())
[(1, [1]), (2, [0, 2, 3]), (4, [4])]
sage: d
{{0, 2, 3}, {1}, {4}}

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> sorted(d.root_to_elements_dict().items())
[(0, [0]), (1, [1]), (2, [2]), (3, [3]), (4, [4])]
>>> d.union(Integer(2), Integer(3))
>>> sorted(d.root_to_elements_dict().items())
[(0, [0]), (1, [1]), (2, [2, 3]), (4, [4])]
>>> d.union(Integer(3), Integer(0))
>>> sorted(d.root_to_elements_dict().items())
[(1, [1]), (2, [0, 2, 3]), (4, [4])]
>>> d
{{0, 2, 3}, {1}, {4}}
to_digraph()[source]

Return the current digraph of self where \((a, b)\) is an oriented edge if \(b\) is the parent of \(a\).

EXAMPLES:

sage: d = DisjointSet(5)
sage: d.union(2, 3)
sage: d.union(4, 1)
sage: d.union(3, 4)
sage: d
{{0}, {1, 2, 3, 4}}
sage: g = d.to_digraph(); g                                                 # needs sage.graphs
Looped digraph on 5 vertices
sage: g.edges(sort=True)                                                    # needs sage.graphs
[(0, 0, None), (1, 2, None), (2, 2, None), (3, 2, None), (4, 2, None)]

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> d.union(Integer(2), Integer(3))
>>> d.union(Integer(4), Integer(1))
>>> d.union(Integer(3), Integer(4))
>>> d
{{0}, {1, 2, 3, 4}}
>>> g = d.to_digraph(); g                                                 # needs sage.graphs
Looped digraph on 5 vertices
>>> g.edges(sort=True)                                                    # needs sage.graphs
[(0, 0, None), (1, 2, None), (2, 2, None), (3, 2, None), (4, 2, None)]

The result depends on the ordering of the union:

sage: d = DisjointSet(5)
sage: d.union(1, 2)
sage: d.union(1, 3)
sage: d.union(1, 4)
sage: d
{{0}, {1, 2, 3, 4}}
sage: d.to_digraph().edges(sort=True)                                       # needs sage.graphs
[(0, 0, None), (1, 1, None), (2, 1, None), (3, 1, None), (4, 1, None)]

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> d.union(Integer(1), Integer(2))
>>> d.union(Integer(1), Integer(3))
>>> d.union(Integer(1), Integer(4))
>>> d
{{0}, {1, 2, 3, 4}}
>>> d.to_digraph().edges(sort=True)                                       # needs sage.graphs
[(0, 0, None), (1, 1, None), (2, 1, None), (3, 1, None), (4, 1, None)]
union(i, j)[source]

Combine the set of i and the set of j into one.

All elements in those two sets will share the same representative that can be retrieved using find().

INPUT:

  • i – element in self

  • j – element in self

EXAMPLES:

sage: d = DisjointSet(5)
sage: d
{{0}, {1}, {2}, {3}, {4}}
sage: d.union(0, 1)
sage: d
{{0, 1}, {2}, {3}, {4}}
sage: d.union(2, 4)
sage: d
{{0, 1}, {2, 4}, {3}}
sage: d.union(1, 4)
sage: d
{{0, 1, 2, 4}, {3}}
sage: d.union(1, 5)
Traceback (most recent call last):
...
ValueError: j must be between 0 and 4 (5 given)

>>> from sage.all import *
>>> d = DisjointSet(Integer(5))
>>> d
{{0}, {1}, {2}, {3}, {4}}
>>> d.union(Integer(0), Integer(1))
>>> d
{{0, 1}, {2}, {3}, {4}}
>>> d.union(Integer(2), Integer(4))
>>> d
{{0, 1}, {2, 4}, {3}}
>>> d.union(Integer(1), Integer(4))
>>> d
{{0, 1, 2, 4}, {3}}
>>> d.union(Integer(1), Integer(5))
Traceback (most recent call last):
...
ValueError: j must be between 0 and 4 (5 given)

Note

This method performs input checks. To avoid them you may directly use OP_join().