42 lines
1.1 KiB
Python
42 lines
1.1 KiB
Python
import sys, os
|
|
sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
|
|
from toposort_kahn import toposort
|
|
|
|
def test_dag():
|
|
g = {"a":["b","c"],"b":["d"],"c":["d"],"d":[]}
|
|
o,c = toposort(g)
|
|
assert c is None
|
|
# a before b,c; d last
|
|
assert o.index("a") < o.index("b")
|
|
assert o.index("a") < o.index("c")
|
|
assert o.index("b") < o.index("d")
|
|
assert o.index("c") < o.index("d")
|
|
print("dag ok", o)
|
|
|
|
def test_cycle():
|
|
g = {"a":["b"],"b":["c"],"c":["a"]}
|
|
o,c = toposort(g)
|
|
assert c is not None
|
|
assert set(c[:-1]) <= {"a","b","c"}
|
|
print("cycle ok", c)
|
|
|
|
def test_empty():
|
|
o,c = toposort({})
|
|
assert o == [] and c is None
|
|
print("empty ok")
|
|
|
|
def test_single():
|
|
o,c = toposort({"x":[]})
|
|
assert o == ["x"] and c is None
|
|
print("single ok")
|
|
|
|
def test_disconnected():
|
|
g = {"a":[],"b":[]}
|
|
o,c = toposort(g)
|
|
assert c is None and o == ["a","b"]
|
|
print("disconnected ok", o)
|
|
|
|
if __name__ == "__main__":
|
|
test_dag(); test_cycle(); test_empty(); test_single(); test_disconnected()
|
|
print("ALL PASS")
|