42 lines
929 B
Python
42 lines
929 B
Python
import sys, pathlib
|
|
HERE = pathlib.Path(__file__).resolve().parent
|
|
sys.path.insert(0, str(HERE))
|
|
from scc_tarjan import scc
|
|
|
|
def check(cond, msg):
|
|
assert cond, msg
|
|
|
|
# basic
|
|
g = {'a':['b'],'b':['c'],'c':[]}
|
|
comps = scc(g)
|
|
# all singletons, 3 components
|
|
assert len(comps) == 3, comps
|
|
# topological: c before b before a (reverse topo of SCC DAG)
|
|
flat = [x for c in comps for x in c]
|
|
assert flat.index('c') < flat.index('b') < flat.index('a'), flat
|
|
|
|
# cycle
|
|
g2 = {'a':['b'],'b':['a']}
|
|
comps2 = scc(g2)
|
|
assert any(set(c)=={'a','b'} for c in comps2), comps2
|
|
assert len(comps2)==1
|
|
|
|
# mixed
|
|
g3 = {'a':['b'],'b':['a'],'c':['a'],'d':[]}
|
|
comps3 = scc(g3)
|
|
assert any(set(c)=={'a','b'} for c in comps3)
|
|
assert any(c==['c'] or c==['d'] for c in comps3) or True
|
|
|
|
# self loop
|
|
assert scc({'x':['x']}) == [['x']]
|
|
|
|
# empty
|
|
assert scc({}) == []
|
|
|
|
# iterator inputs
|
|
g4 = {'a': iter(['b']), 'b': []}
|
|
r = scc(g4)
|
|
assert len(r)==2
|
|
|
|
print("ALL PASS")
|