Disjoint-set data structure
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:
AUTHORS:
- Sebastien Labbe (2008) - Initial version.
- Sebastien Labbe (2009-11-24) - Pickling support
- Sebastien Labbe (2010-01) - Inclusion into sage (#6775).
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: map(s.find, range(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'
Construction of the DisjointSet where each element of arg is in its own set. If arg is an integer, then the DisjointSet returned is made of the integers from 0 to arg-1.
INPUT:
EXAMPLES:
From a non-negative integer:
sage: DisjointSet(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}}
TESTS:
sage: DisjointSet(0)
{}
sage: DisjointSet('')
{}
sage: DisjointSet([])
{}
The argument must be a non negative integer:
sage: DisjointSet(-1)
Traceback (most recent call last):
...
ValueError: arg (=-1) must be a non negative integer
or an iterable:
sage: DisjointSet(4.3)
Traceback (most recent call last):
...
TypeError: 'sage.rings.real_mpfr.RealLiteral' object is not iterable
Moreover, the iterable must consist of hashable:
sage: DisjointSet([{}, {}])
Traceback (most recent call last):
...
TypeError: unhashable type: 'dict'
Bases: sage.structure.sage_object.SageObject
Common class and methods for DisjointSet_of_integers and DisjointSet_of_hashables.
Returns the number of elements in the disjoint set.
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
Returns the number of subsets in the disjoint set.
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
Bases: sage.sets.disjoint_set.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'
TESTS:
sage: a = DisjointSet('abcdef')
sage: a == loads(dumps(a))
True
sage: a.union('a','c')
sage: a == loads(dumps(a))
True
Returns 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(); e
{0: 0, 1: 4, 2: 2, 3: 2, 4: 4}
sage: WordMorphism(e)
WordMorphism: 0->0, 1->4, 2->2, 3->2, 4->4
Returns the representative of the set that e currently belongs to.
INPUT:
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
Returns 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(); e
{0: [0], 2: [2, 3], 4: [1, 4]}
Returns 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(); g
Looped digraph on 5 vertices
sage: g.edges()
[(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()
[(0, 0, None), (1, 1, None), (2, 1, None), (3, 1, None), (4, 1, None)]
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 gotten using find.
INPUT:
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'}}
Bases: sage.sets.disjoint_set.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
TESTS:
sage: a = DisjointSet(5)
sage: a == loads(dumps(a))
True
sage: a.union(3,4)
sage: a == loads(dumps(a))
True
Returns 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(); e
{0: 0, 1: 4, 2: 2, 3: 2, 4: 4}
sage: WordMorphism(e)
WordMorphism: 0->0, 1->4, 2->2, 3->2, 4->4
Returns the representative of the set that i currently belongs to.
INPUT:
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(5)
Traceback (most recent call last):
...
ValueError: i(=5) must be between 0 and 4
Returns 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: d.root_to_elements_dict()
{0: [0], 1: [1], 2: [2], 3: [3], 4: [4]}
sage: d.union(2,3)
sage: d.root_to_elements_dict()
{0: [0], 1: [1], 2: [2, 3], 4: [4]}
sage: d.union(3,0)
sage: d.root_to_elements_dict()
{1: [1], 2: [0, 2, 3], 4: [4]}
sage: d
{{0, 2, 3}, {1}, {4}}
Returns 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
Looped digraph on 5 vertices
sage: g.edges()
[(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()
[(0, 0, None), (1, 1, None), (2, 1, None), (3, 1, None), (4, 1, None)]
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 gotten using find.
INPUT:
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(=5) must be between 0 and 4
Demonstration and testing.
TESTS:
sage: from sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label import OP_represent
sage: OP_represent(9, [(0,1),(2,3),(3,4)], [1,2,0,4,3,6,7,5,8])
Allocating OrbitPartition...
Allocation passed.
Checking that each element reports itself as its root.
Each element reports itself as its root.
Merging:
Merged 0 and 1.
Merged 2 and 3.
Merged 3 and 4.
Done merging.
Finding:
0 -> 0, root: size=2, mcr=0, rank=1
1 -> 0
2 -> 2, root: size=3, mcr=2, rank=1
3 -> 2
4 -> 2
5 -> 5, root: size=1, mcr=5, rank=0
6 -> 6, root: size=1, mcr=6, rank=0
7 -> 7, root: size=1, mcr=7, rank=0
8 -> 8, root: size=1, mcr=8, rank=0
Allocating array to test merge_perm.
Allocation passed.
Merging permutation: [1, 2, 0, 4, 3, 6, 7, 5, 8]
Done merging.
Finding:
0 -> 0, root: size=5, mcr=0, rank=2
1 -> 0
2 -> 0
3 -> 0
4 -> 0
5 -> 5, root: size=3, mcr=5, rank=1
6 -> 5
7 -> 5
8 -> 8, root: size=1, mcr=8, rank=0
Deallocating OrbitPartition.
Done.
Demonstration and testing.
TESTS:
sage: from sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label import PS_represent
sage: PS_represent([[6],[3,4,8,7],[1,9,5],[0,2]], [6,1,8,2])
Allocating PartitionStack...
Allocation passed:
(0 1 2 3 4 5 6 7 8 9)
Checking that entries are in order and correct level.
Everything seems in order, deallocating.
Deallocated.
Creating PartitionStack from partition [[6], [3, 4, 8, 7], [1, 9, 5], [0, 2]].
PartitionStack's data:
entries -> [6, 3, 4, 8, 7, 1, 9, 5, 0, 2]
levels -> [0, 10, 10, 10, 0, 10, 10, 0, 10, -1]
depth = 0, degree = 10
(6|3 4 8 7|1 9 5|0 2)
Checking PS_is_discrete:
False
Checking PS_num_cells:
4
Checking PS_is_mcr, min cell reps are:
[6, 3, 1, 0]
Checking PS_is_fixed, fixed elements are:
[6]
Copying PartitionStack:
(6|3 4 8 7|1 9 5|0 2)
Checking for consistency.
Everything is consistent.
Clearing copy:
(0 3 4 8 7 1 9 5 6 2)
Splitting point 6 from original:
0
(6|3 4 8 7|1 9 5|0 2)
Splitting point 1 from original:
5
(6|3 4 8 7|1|5 9|0 2)
Splitting point 8 from original:
1
(6|8|3 4 7|1|5 9|0 2)
Splitting point 2 from original:
8
(6|8|3 4 7|1|5 9|2|0)
Getting permutation from PS2->PS:
[6, 1, 0, 8, 3, 9, 2, 7, 4, 5]
Finding first smallest:
Minimal element is 5, bitset is:
0000010001
Finding element 1:
Location is: 5
Bitset is:
0100000000
Deallocating PartitionStacks.
Done.
Test that the permutation group generated by list perms in L of degree n is of the correct order, by comparing with GAP. Don’t test if the group is of size greater than limit.
TESTS:
sage: from sage.groups.perm_gps.partn_ref.automorphism_group_canonical_label import SC_test_list_perms
sage: limit = 10^7
sage: def test_Sn_on_m_points(n, m, gap, contains):
... perm1 = [1,0] + range(m)[2:]
... perm2 = [(i+1)%n for i in range( n )] + range(m)[n:]
... SC_test_list_perms([perm1, perm2], m, limit, gap, 0, contains)
sage: for i in range(2,9):
... test_Sn_on_m_points(i,i,1,0)
sage: for i in range(2,9):
... test_Sn_on_m_points(i,i,0,1)
sage: for i in range(2,9): # long time
... test_Sn_on_m_points(i,i,1,1) # long time
sage: test_Sn_on_m_points(8,8,1,1)
sage: def test_stab_chain_fns_1(n, gap, contains):
... perm1 = sum([[2*i+1,2*i] for i in range(n)], [])
... perm2 = [(i+1)%(2*n) for i in range( 2*n)]
... SC_test_list_perms([perm1, perm2], 2*n, limit, gap, 0, contains)
sage: for n in range(1,11):
... test_stab_chain_fns_1(n, 1, 0)
sage: for n in range(1,11):
... test_stab_chain_fns_1(n, 0, 1)
sage: for n in range(1,9): # long time
... test_stab_chain_fns_1(n, 1, 1) # long time
sage: test_stab_chain_fns_1(11, 1, 1)
sage: def test_stab_chain_fns_2(n, gap, contains):
... perms = []
... for p,e in factor(n):
... perm1 = [(p*(i//p)) + ((i+1)%p) for i in range(n)]
... perms.append(perm1)
... SC_test_list_perms(perms, n, limit, gap, 0, contains)
sage: for n in range(2,11):
... test_stab_chain_fns_2(n, 1, 0)
sage: for n in range(2,11):
... test_stab_chain_fns_2(n, 0, 1)
sage: for n in range(2,11): # long time
... test_stab_chain_fns_2(n, 1, 1) # long time
sage: test_stab_chain_fns_2(11, 1, 1)
sage: def test_stab_chain_fns_3(n, gap, contains):
... perm1 = [(-i)%n for i in range( n )]
... perm2 = [(i+1)%n for i in range( n )]
... SC_test_list_perms([perm1, perm2], n, limit, gap, 0, contains)
sage: for n in range(2,20):
... test_stab_chain_fns_3(n, 1, 0)
sage: for n in range(2,20):
... test_stab_chain_fns_3(n, 0, 1)
sage: for n in range(2,14): # long time
... test_stab_chain_fns_3(n, 1, 1) # long time
sage: test_stab_chain_fns_3(20, 1, 1)
sage: def test_stab_chain_fns_4(n, g, gap, contains):
... perms = []
... for _ in range(g):
... perm = range(n)
... shuffle(perm)
... perms.append(perm)
... SC_test_list_perms(perms, n, limit, gap, 0, contains)
sage: for n in range(4,9): # long time
... test_stab_chain_fns_4(n, 1, 1, 0) # long time
... test_stab_chain_fns_4(n, 2, 1, 0) # long time
... test_stab_chain_fns_4(n, 2, 1, 0) # long time
... test_stab_chain_fns_4(n, 2, 1, 0) # long time
... test_stab_chain_fns_4(n, 2, 1, 0) # long time
... test_stab_chain_fns_4(n, 3, 1, 0) # long time
sage: for n in range(4,9):
... test_stab_chain_fns_4(n, 1, 0, 1)
... for j in range(6):
... test_stab_chain_fns_4(n, 2, 0, 1)
... test_stab_chain_fns_4(n, 3, 0, 1)
sage: for n in range(4,8): # long time
... test_stab_chain_fns_4(n, 1, 1, 1) # long time
... test_stab_chain_fns_4(n, 2, 1, 1) # long time
... test_stab_chain_fns_4(n, 2, 1, 1) # long time
... test_stab_chain_fns_4(n, 3, 1, 1) # long time
sage: test_stab_chain_fns_4(8, 2, 1, 1)
sage: def test_stab_chain_fns_5(n, gap, contains):
... perms = []
... m = n//3
... perm1 = range(2*m)
... shuffle(perm1)
... perm1 += range(2*m,n)
... perm2 = range(m,n)
... shuffle(perm2)
... perm2 = range(m) + perm2
... SC_test_list_perms([perm1, perm2], n, limit, gap, 0, contains)
sage: for n in [4..9]: # long time
... for _ in range(2): # long time
... test_stab_chain_fns_5(n, 1, 0) # long time
sage: for n in [4..8]: # long time
... test_stab_chain_fns_5(n, 0, 1) # long time
sage: for n in [4..9]: # long time
... test_stab_chain_fns_5(n, 1, 1) # long time
sage: def random_perm(x):
... shuffle(x)
... return x
sage: def test_stab_chain_fns_6(m,n,k, gap, contains):
... perms = []
... for i in range(k):
... perm = sum([random_perm(range(i*(n//m),min(n,(i+1)*(n//m)))) for i in range(m)], [])
... perms.append(perm)
... SC_test_list_perms(perms, m*(n//m), limit, gap, 0, contains)
sage: for m in range(2,9): # long time
... for n in range(m,3*m): # long time
... for k in range(1,3): # long time
... test_stab_chain_fns_6(m,n,k, 1, 0) # long time
sage: for m in range(2,10):
... for n in range(m,4*m):
... for k in range(1,3):
... test_stab_chain_fns_6(m,n,k, 0, 1)
sage: test_stab_chain_fns_6(10,20,2, 1, 1)
sage: test_stab_chain_fns_6(8,16,2, 1, 1)
sage: test_stab_chain_fns_6(6,36,2, 1, 1)
sage: test_stab_chain_fns_6(4,40,3, 1, 1)
sage: test_stab_chain_fns_6(4,40,2, 1, 1)
sage: def test_stab_chain_fns_7(n, cop, gap, contains):
... perms = []
... for i in range(0,n//2,2):
... p = range(n)
... p[i] = i+1
... p[i+1] = i
... if cop:
... perms.append([c for c in p])
... else:
... perms.append(p)
... SC_test_list_perms(perms, n, limit, gap, 0, contains)
sage: for n in [6..14]:
... test_stab_chain_fns_7(n, 1, 1, 0)
... test_stab_chain_fns_7(n, 0, 1, 0)
sage: for n in [6..30]:
... test_stab_chain_fns_7(n, 1, 0, 1)
... test_stab_chain_fns_7(n, 0, 0, 1)
sage: for n in [6..14]: # long time
... test_stab_chain_fns_7(n, 1, 1, 1) # long time
... test_stab_chain_fns_7(n, 0, 1, 1) # long time
sage: test_stab_chain_fns_7(20, 1, 1, 1)
sage: test_stab_chain_fns_7(20, 0, 1, 1)