Illustration of breadth-first search for Hack.Diversity Learning Labs 2022-03-22

breadth_first.py

#!/usr/bin/env python

class Node:
    def __init__(self, value=None, children=None):
        self.value = value
        self.children = children or []
        self.visited = False

def make_graph():
    graph = {}
    # Nodes with no children
    graph[9] = Node(9)
    graph[7] = Node(7)
    graph[15] = Node(15)
    graph[5] = Node(5)
    graph[19] = Node(19) # Target node
    graph[3] = Node(3)
    graph[16] = Node(16)

    # Nodes with children
    graph[4] = Node(4, [graph[7], graph[15]])
    graph[13] = Node(13, [graph[5], graph[19], graph[3]])
    graph[21] = Node(21, [graph[13]])
    graph[6] = Node(6, [graph[13]])
    graph[12] = Node(12, [graph[6]])
    graph[1] = Node(1, [graph[12], graph[16]])
    graph[2] = Node(2, [graph[9], graph[4], graph[21], graph[1]])
    graph[8] = Node(8, [graph[2]])
    return graph

def add_children_to_queue(node, queue):
    for child_node in node.children:
        queue.append(child_node)

def find_path_breadth_first(start_node, target_node):
    queue = []
    add_children_to_queue(start_node, queue)

    start_node.visited = True

    # While we have more children in our queue...
    while len(queue) > 0:
        # Remove the first child node in the queue.
        child_node = queue.pop(0)

        # If the node is our target, return True.
        if child_node.value == target_node.value:
            return True

        # If we have already visited this node, go to the next node in the queue.
        if child_node.visited:
            continue

        # Mark this node as visited so we do not re-process it.
        child_node.visited = True

        # Add this node's children to the queue.
        add_children_to_queue(child_node, queue)

    # If we got here without returning True, there is no path from start_node to target_node.
    return False

import unittest

class TestBreadthFirst(unittest.TestCase):

    def test_path_exists_from_8_to_19(self):
        graph = make_graph()
        start_node = graph[8]
        target_node = graph[19]
        found = find_path_breadth_first(start_node, target_node)
        self.assertTrue(found)

    def test_path_does_not_exist_from_4_to_19(self):
        graph = make_graph()
        start_node = graph[4]
        target_node = graph[19]
        found = find_path_breadth_first(start_node, target_node)
        self.assertFalse(found)

if __name__ == "__main__":
    unittest.main()