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

depth_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 find_path_depth_first(node, target_node):
    # If the node is our target, return True.
    if node.value == target_node.value:
        return True

    # If we have already visited this node, stop recurring.
    # The previous recursion will pick up where we left off.
    if node.visited:
        return False

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

    # Recursively search each of this node's children.
    for child_node in node.children:
        found = find_path_depth_first(child_node, target_node)
        if found:
            return True

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

import unittest

class TestDepthFirst(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_depth_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_depth_first(start_node, target_node)
        self.assertFalse(found)

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