import pathlib
import sys
sys.path.insert(0, str(pathlib.Path(__file__).resolve().parent))
from bfs_shortest_path import shortest_path, shortest_distances

def test_basic():
    adj = {0:[1,2],1:[3],2:[3],3:[]}
    assert shortest_path(adj,0,3) in ([0,1,3],[0,2,3])
    assert shortest_distances(adj,0) == {0:0,1:1,2:1,3:2}

def test_same():
    adj = {5:[]}
    assert shortest_path(adj,5,5) == [5]

def test_unreachable():
    adj = {0:[1],2:[]}
    assert shortest_path(adj,0,2) is None

def test_unknown_vertex():
    adj = {0:[1]}
    assert shortest_path(adj,0,99) is None
    assert shortest_path(adj,99,0) is None

def test_empty_graph():
    adj = {}
    assert shortest_path(adj,1,1) is None  # vertex not present
    assert shortest_distances(adj,1) == {1:0}  # isolated allowed for distances? spec: yes if src given

def test_directed():
    adj = {0:[1],1:[]}
    assert shortest_path(adj,1,0) is None

def test_path_reconstruction_long():
    adj = {i:[i+1] for i in range(5)}
    assert shortest_path(adj,0,5) == [0,1,2,3,4,5]

if __name__ == "__main__":
    for name in [n for n in globals() if n.startswith("test_")]:
        globals()[name]()
    print("ALL TESTS PASSED")