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()
.
AUTHORS:
- Sébastien Labbé (2008) - Initial version.
- Sébastien Labbé (2009-11-24) - Pickling support
- Sébastien Labbé (2010-01) - Inclusion into sage (trac ticket #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: list(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'
-
sage.sets.disjoint_set.
DisjointSet
(arg)¶ Constructs a disjoint set where each element of
arg
is in its own set. Ifarg
is an integer, then the disjoint set returned is made of the integers from0
toarg - 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
– non negative integer or an iterable of hashable objects.
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'
-
class
sage.sets.disjoint_set.
DisjointSet_class
¶ Bases:
sage.structure.sage_object.SageObject
Common class and methods for
DisjointSet_of_integers
andDisjointSet_of_hashables
.-
cardinality
()¶ 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
-
number_of_subsets
()¶ 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
-
-
class
sage.sets.disjoint_set.
DisjointSet_of_hashables
¶ 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
-
element_to_root_dict
()¶ 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(); 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
-
find
(e)¶ Return the representative of the set that
e
currently belongs to.INPUT:
e
– element inself
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
-
root_to_elements_dict
()¶ 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(); e {0: [0], 2: [2, 3], 4: [1, 4]}
-
to_digraph
()¶ 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(); 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)]
-
union
(e, f)¶ Combine the set of
e
and the set off
into one.All elements in those two sets will share the same representative that can be gotten using find.
INPUT:
e
- element inself
f
- element inself
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'}}
-
-
class
sage.sets.disjoint_set.
DisjointSet_of_integers
¶ Bases:
sage.sets.disjoint_set.DisjointSet_class
Disjoint set of integers from
0
ton-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
-
element_to_root_dict
()¶ 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(); 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
-
find
(i)¶ Return the representative of the set that
i
currently belongs to.INPUT:
i
– element inself
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
-
root_to_elements_dict
()¶ 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: 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}}
-
to_digraph
()¶ 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 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)]
-
union
(i, j)¶ Combine the set of
i
and the set ofj
into one.All elements in those two sets will share the same representative that can be gotten using find.
INPUT:
i
- element inself
j
- element inself
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
-
-
sage.sets.disjoint_set.
OP_represent
(n, merges, perm)¶ 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.
-
sage.sets.disjoint_set.
PS_represent
(partition, splits)¶ 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.
-
sage.sets.disjoint_set.
SC_test_list_perms
(L, n, limit, gap, limit_complain, test_contains)¶ 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] + list(range(2, m)) ....: perm2 = [(i+1)%n for i in range( n )] + list(range(n,m)) ....: 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 = list(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 = list(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(list(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 = list(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)