libstatic._analyzer.unionfind

UnionFind Implementation in Python

>>> uf = UnionFind(list('abcdefghij'))
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
par=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=10>
>>> uf.union('e', 'd')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 1, 1, 2, 1, 1, 1, 1, 1],
par=[0, 1, 2, 4, 4, 5, 6, 7, 8, 9],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=9>
>>> uf.union('d', 'i')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 1, 1, 3, 1, 1, 1, 1, 1],
par=[0, 1, 2, 4, 4, 5, 6, 7, 4, 9],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=8>
>>> uf.union('g', 'f')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 1, 1, 3, 1, 2, 1, 1, 1],
par=[0, 1, 2, 4, 4, 6, 6, 7, 4, 9],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=7>
>>> uf.union('j', 'e')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 1, 1, 4, 1, 2, 1, 1, 1],
par=[0, 1, 2, 4, 4, 6, 6, 7, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=6>
>>> uf.union('c', 'b')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 2, 1, 4, 1, 2, 1, 1, 1],
par=[0, 2, 2, 4, 4, 6, 6, 7, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=5>
>>> uf.union('i', 'j')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 2, 1, 4, 1, 2, 1, 1, 1],
par=[0, 2, 2, 4, 4, 6, 6, 7, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=5>
>>> uf.union('f', 'a')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 2, 1, 4, 1, 3, 1, 1, 1],
par=[6, 2, 2, 4, 4, 6, 6, 7, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=4>
>>> uf.union('h', 'c')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 3, 1, 4, 1, 3, 1, 1, 1],
par=[6, 2, 2, 4, 4, 6, 6, 2, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=3>
>>> uf.union('g', 'b')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 3, 1, 4, 1, 6, 1, 1, 1],
par=[6, 2, 6, 4, 4, 6, 6, 2, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=2>
>>> uf.union('a', 'b')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 3, 1, 4, 1, 6, 1, 1, 1],
par=[6, 6, 6, 4, 4, 6, 6, 2, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=2>
>>> uf.union('g', 'h')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 3, 1, 4, 1, 6, 1, 1, 1],
par=[6, 6, 6, 4, 4, 6, 6, 6, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[],
n_elts=10,n_comps=2>
>>> uf.connected('a', 'g')
True
>>> uf.component('a')
<ordered_set {g, a, b, c, f, h}>
>>> uf.components()
[<ordered_set {g, a, b, c, f, h}>, <ordered_set {e, d, i, j}>]
>>> uf.remove('i')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 3, 1, 4, 1, 6, 1, 1, 1],
par=[6, 6, 6, 4, 4, 6, 6, 6, 4, 4],
nb_rm=[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
removed=[8],
free=[],
n_elts=9,n_comps=2>
>>> uf.components()
[<ordered_set {g, a, b, c, f, h}>, <ordered_set {e, d, j}>]
>>> uf.remove('j')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'],
siz=[1, 1, 3, 1, 4, 1, 6, 1, 1, 1],
par=[6, 6, 6, 4, 4, 6, 6, 6, 4, 4],
nb_rm=[0, 0, 0, 0, 2, 0, 0, 0, 0, 0],
removed=[8, 9],
free=[],
n_elts=8,n_comps=2>
>>> uf.components()
[<ordered_set {g, a, b, c, f, h}>, <ordered_set {e, d}>]
>>> uf.remove('d')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', <free>, 'e', 'f', 'g', 'h', <free>, <free>],
siz=[1, 1, 3, 0, 1, 1, 6, 1, 0, 0],
par=[6, 6, 6, 3, 4, 6, 6, 6, 8, 9],
nb_rm=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
removed=[],
free=[3, 8, 9],
n_elts=7,n_comps=2>
>>> uf.components()
[<ordered_set {g, a, b, c, f, h}>, <ordered_set {e}>]
>>> uf.component('e')
<ordered_set {e}>
>>> uf.union('e', 'z')
>>> uf.remove('a')
>>> uf.union('z', 'x')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'z', 'e', 'f', 'g', 'h', 'x', <free>],
siz=[1, 1, 3, 1, 3, 1, 6, 1, 1, 0],
par=[6, 6, 6, 4, 4, 6, 6, 6, 4, 9],
nb_rm=[0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
removed=[0],
free=[9],
n_elts=8,n_comps=2>
>>> uf.components()
[<ordered_set {g, b, c, f, h}>, <ordered_set {e, z, x}>]
>>> uf.remove('g')
>>> uf.components()
[<ordered_set {b, c, f, h}>, <ordered_set {e, z, x}>]
>>> uf.union('x', 'y')
>>> uf
<UnionFind:
elts=['a', 'b', 'c', 'z', 'e', 'f', 'g', 'h', 'x', 'y'],
siz=[1, 1, 3, 1, 4, 1, 6, 1, 1, 1],
par=[6, 6, 6, 4, 4, 6, 6, 6, 4, 4],
nb_rm=[0, 0, 0, 0, 0, 0, 2, 0, 0, 0],
removed=[0, 6],
free=[],
n_elts=8,n_comps=2>
>>> for e in 'bcfhe':
...     uf.remove(e)
...
>>> uf
<UnionFind:
elts=[<free>, <free>, <free>, 'z', 'e', <free>, <free>, <free>, 'x', 'y'],
siz=[0, 0, 0, 1, 4, 0, 0, 0, 1, 1],
par=[0, 1, 2, 4, 4, 5, 6, 7, 4, 4],
nb_rm=[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
removed=[4],
free=[0, 1, 2, 6, 5, 7],
n_elts=3,n_comps=1>
>>> uf.components()
[<ordered_set {z, x, y}>]