Spaces:
Sleeping
Sleeping
File size: 1,997 Bytes
baa4989 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | from .node import Node
from .breadth_first_search import breadth_first_search
"""
Driver to test breadth first search
"""
def main():
# Case 1: Strongly connected graph
# Output: Path found!
station1 = Node("Westminster")
station2 = Node("Waterloo", None, [station1])
station3 = Node("Trafalgar Square", None, [station1, station2])
station4 = Node("Canary Wharf", None, [station2, station3])
station5 = Node("London Bridge", None, [station4, station3])
station6 = Node("Tottenham Court Road", None, [station5, station4])
if breadth_first_search(station6, station1):
print("Path found!", end=" ")
else:
print("Path not found!", end=" ")
print()
# Case 2: Branching graph
# Output: Path found!
nodef = Node("F")
nodee = Node("E")
noded = Node("D")
nodec = Node("C", None, [nodef])
nodeb = Node("B", None, [nodee])
nodea = Node("A", None, [nodeb, nodec, noded])
if breadth_first_search(nodea, nodee):
print("Path found!", end=" ")
else:
print("Path not found!", end=" ")
print()
# Case 3: Two unconnected nodes in graph
# Output: Path not found
if breadth_first_search(nodef, nodee):
print("Path found!", end=" ")
else:
print("Path not found!", end=" ")
print()
# Case 4: One node graph
# Output: Path found!
if breadth_first_search(nodef, nodef):
print("Path found!", end=" ")
else:
print("Path not found!", end=" ")
print()
# Case 5: Graph with cycles
# Output: Path found!
node1 = Node("1")
node2 = Node("2")
node3 = Node("3")
node4 = Node("4", None, [node1])
node5 = Node("5", None, [node2])
node6 = Node("6", None, [node5, node4, node3])
node2.successors = [node6]
if breadth_first_search(node6, node1):
print("Path found!", end=" ")
else:
print("Path not found!", end=" ")
print()
if __name__ == "__main__":
main() |