Traversal

Imagine a video game; you have a map of every area you must visit, see the map below. Every arrow symbolizes a one-way route from one area to another. Every area is a node. Every route between two areas is an edge associated with a weight which is the travel time. Let us assume, since this is a video game, that one can teleport at any previously visited node. How would you plan the visit of every node?

Graph traversal example

From a starting node, the three most obvious way to explore the map:

• the go-getter way: Depth First, the exploration follows one branch as deeply as possible before going back.

Choose a starting node.
Mark it as visited.
Select one of its unvisited children and continue the exploration from that child.
Repeat this process, always going deeper along unvisited children.
When a node has no unvisited children, return to its parent node.
Continue this backtracking process until every reachable node has been visited.

• the no-unexplored-route-left-behind way: Breadth First, the exploration spreads outward from the start, visiting nodes in order of decreasing family relationship proximity.

Choose a starting node.
Mark it as visited.
Explore all of its unvisited children.
Then explore the unvisited children of those nodes.
Continue expanding the search level by level.
Stop when all reachable nodes have been visited.

• the speed-runner way: Uniform Cost, the exploration always expands the least costly path discovered so far.

Choose a starting node and assign it a total cost of zero.
Among the not-yet-visited-children of the visited nodes, select the one with the lowest total accumulated cost from the start.
Mark this node as visited.
For each of its children, compute the total cost required to reach them through the current node.
If this new cost is lower than a previously known cost, update it.
Repeat this process until all reachable nodes have been visited.

These traversal algorithms (especially the uniform cost) will be very useful in the future lecture about state problem. It will be used to determine the succession of actions with a minimum cost in order to reach a goal state.

Note

The uniform cost algorithm is only valid for positive weights.

Exercise (easy)

Apply (by hand) the three strategies outlined above to the graph above starting from “a”. Assume a lexicographic order when looping over children (in reality this lexicographic order is not enforced).

Correction

With the teleportation between brackets:

• Depth first:

  [a, b, e, d, g, f, (g), (e), (a), c]

• Breadth first:

  [a, b, (a), c, (a), d, (b), e, (c), (d), g, f]

• Uniform cost:

  [a, b, (a), c, e, (a), d, (e), f, (d), g]

The following types can be defined to annotate the future traversal functions:

src

type Node = str | int
type Weight = float | int
type DirectedWeightedGraph = dict[Node, dict[Node, Weight]]
type PathGraph = list[Node]
type PredecessorGraph = dict[Node, Node | None]

Exercise (intermediate)

Implement a generator for the DFS traversal of a directed graph from a starting node. Test it.

1. Recursively: direct implementation of the DFS above.

2. Iteratively: the notion of a queue is used, meaning that the node to be visited are appended to a list.

3. Yield also the total distance and path from the starting node for the recursive version.

4. Same as previously but for the iterative version.

5. Two solutions are given the previous question, what are the key differences?

Correction

1. recursive

src

def depth_first_traversal_recursive_simple_print(
    graph: DirectedWeightedGraph, starting_node: Node
) -> None:
    visited = set()

    def _df_recurse(node: Node) -> None:
        visited.add(node)
        print(node)
        for child in graph[node]:
            if child not in visited:
                _df_recurse(child)

    _df_recurse(starting_node)

tests

@pytest.fixture
def graph_example() -> DirectedWeightedGraph:
    return {
        "a": {"b": 1.0, "c": 2.0, "d": 4.0},
        "b": {"e": 3.0},
        "c": {"e": 1.0},
        "d": {"g": 5.0},
        "e": {"d": 2.0, "f": 3.0},
        "f": {},
        "g": {"a": 1.0, "f": 8.0},
    }

tests

def test_depth_first_traversal_recursive_simple_print(
    capsys, graph_example: DirectedWeightedGraph
) -> None:
    depth_first_traversal_recursive_simple_print(graph_example, "a")
    captured = capsys.readouterr().out
    assert captured == "a\nb\ne\nd\ng\nf\nc\n"

src

def depth_first_traversal_recursive_yield_nodes(
    graph: DirectedWeightedGraph, starting_node: Node
) -> Generator[Node]:
    visited = set()

    def _df_recurse(node: Node) -> Generator[Node]:
        visited.add(node)
        yield node
        for child in graph[node]:
            if child not in visited:
                yield from _df_recurse(child)

    yield from _df_recurse(starting_node)

tests

@pytest.mark.parametrize(
    "starting_node, expected",
    [
        ("a", ["a", "b", "e", "d", "g", "f", "c"]),
        ("e", ["e", "d", "g", "a", "b", "c", "f"]),
    ],
)
def test_depth_first_traversal_recursive_yield_nodes(
    graph_example: DirectedWeightedGraph, starting_node: Node, expected: list[Node]
) -> None:
    obtained = list(
        depth_first_traversal_recursive_yield_nodes(graph_example, starting_node)
    )
    assert obtained == expected

2. iterative

src

def depth_first_traversal_iterative_yield_nodes(
    graph: DirectedWeightedGraph, starting_node: Node
) -> Generator[Node]:
    visited = {starting_node}
    queue: list[Node] = [starting_node]

    while queue:
        node = queue.pop()
        yield node

        for child in graph[node]:
            if child not in visited:
                visited.add(child)
                queue.append(child)

tests

@pytest.mark.parametrize(
    "starting_node, expected",
    [
        ("a", ["a", "d", "g", "f", "c", "e", "b"]),
        ("e", ["e", "f", "d", "g", "a", "c", "b"]),
    ],
)
def test_depth_first_traversal_iterative_yield_nodes(
    graph_example: DirectedWeightedGraph,
    starting_node: Node,
    expected: PathGraph,
) -> None:
    obtained = list(
        depth_first_traversal_iterative_yield_nodes(graph_example, starting_node)
    )
    assert obtained == expected

3. with predecessors:

   src

   def depth_first_traversal_recursive_yield_node_and_predecessors(
       graph: DirectedWeightedGraph, starting_node: Node
   ) -> Generator[tuple[Node, PredecessorGraph]]:
       predecessors: PredecessorGraph = {starting_node: None}
   
       def _df_recurse(node: Node) -> Generator[tuple[Node, PredecessorGraph]]:
           yield node, predecessors
           for child in graph[node]:
               if child not in predecessors:
                   predecessors[child] = node
                   yield from _df_recurse(child)
   
       yield from _df_recurse(starting_node)
   

   src

   def rebuild_path_and_distance_from_predecessors(
       graph: DirectedWeightedGraph,
       predecessors: PredecessorGraph,
       source: Node,
       target: Node,
   ) -> tuple[Node, PathGraph, Weight]:
       if target not in predecessors:
           return target, [], float("inf")  # unreachable, because never visited
   
       path: PathGraph = []
       distance: Weight = 0.0
   
       current = target
   
       while current != source:  # go back until the source is found
           parent = predecessors[current]
   
           if parent is None:
               return target, [], float("inf")  # unreachable
   
           distance += graph[parent][current]
           path.append(current)
           current = parent
   
       path.append(source)
       path.reverse()
   
       return target, path, distance
   

   tests

   def test_depth_first_traversal_recursive_yield_node_and_predecessors(
       graph_example: DirectedWeightedGraph,
   ) -> None:
       expected = [
           ("a", {"a": None}),
           ("b", {"a": None, "b": "a"}),
           ("e", {"a": None, "b": "a", "e": "b"}),
           ("d", {"a": None, "b": "a", "e": "b", "d": "e"}),
           ("g", {"a": None, "b": "a", "e": "b", "d": "e", "g": "d"}),
           ("f", {"a": None, "b": "a", "e": "b", "d": "e", "g": "d", "f": "g"}),
           ("c", {"a": None, "b": "a", "e": "b", "d": "e", "g": "d", "f": "g", "c": "a"}),
       ]
       obtained = [
           (node, predecessors.copy())
           for node, predecessors in depth_first_traversal_recursive_yield_node_and_predecessors(
               graph_example, "a"
           )
       ]
       assert expected == obtained
   

   tests

   def test_rebuild_path_and_distance_from_predecessors(
       graph_example: DirectedWeightedGraph,
   ) -> None:
       predecessors: PredecessorGraph = {
           "a": None,
           "b": "a",
           "e": "b",
           "d": "e",
           "g": "d",
           "f": "g",
           "c": "a",
       }
       target = "g"
       distance_expected = 11.0
       target_obtained, path, distance = rebuild_path_and_distance_from_predecessors(
           graph_example, predecessors, "a", target
       )
       assert target == target_obtained
       assert path == ["a", "b", "e", "d", "g"]
       assert pytest.approx(distance_expected) == distance
   

   with explicit paths:

   src

   def depth_first_traversal_recursive_with_paths_and_distances(
       graph: DirectedWeightedGraph, starting_node: Node
   ) -> Generator[tuple[Node, PathGraph, Weight]]:
       visited = set()
       path: PathGraph = [starting_node]
       starting_distance: Weight = 0.0
   
       def _df_recurse(
           node: Node, path: list[Node], distance: Weight
       ) -> Generator[tuple[Node, PathGraph, Weight]]:
           visited.add(node)
           yield node, path, distance
           for child, distance_child in graph[node].items():
               if child not in visited:
                   yield from _df_recurse(child, path + [child], distance + distance_child)
   
       yield from _df_recurse(starting_node, path, starting_distance)
   

   tests

   def test_depth_first_traversal_recursive_with_paths_and_distances(
       graph_example: DirectedWeightedGraph,
   ) -> None:
       expected = [
           ("a", ["a"], 0.0),
           ("b", ["a", "b"], 1.0),
           ("e", ["a", "b", "e"], 4.0),
           ("d", ["a", "b", "e", "d"], 6.0),
           ("g", ["a", "b", "e", "d", "g"], 11.0),
           ("f", ["a", "b", "e", "d", "g", "f"], 19.0),
           ("c", ["a", "c"], 2.0),
       ]
       obtained = list(
           depth_first_traversal_recursive_with_paths_and_distances(graph_example, "a")
       )
       assert expected == obtained
   

4. with predecessors:

   src

   def depth_first_traversal_iterative_yield_node_and_predecessors(
       graph: DirectedWeightedGraph, starting_node: Node
   ) -> Generator[tuple[Node, PredecessorGraph]]:
       predecessors: PredecessorGraph = {starting_node: None}
       queue: list[Node] = [starting_node]
   
       while queue:
           node = queue.pop()
           yield node, predecessors
   
           for child in graph[node]:
               if child not in predecessors:
                   predecessors[child] = node
                   queue.append(child)
   

   tests

   def test_depth_first_traversal_iterative_yield_node_and_predecessors(
       graph_example: DirectedWeightedGraph,
   ) -> None:
       expected = [
           ("a", {"a": None}),
           ("d", {"a": None, "b": "a", "c": "a", "d": "a"}),
           ("g", {"a": None, "b": "a", "c": "a", "d": "a", "g": "d"}),
           ("f", {"a": None, "b": "a", "c": "a", "d": "a", "g": "d", "f": "g"}),
           ("c", {"a": None, "b": "a", "c": "a", "d": "a", "g": "d", "f": "g"}),
           ("e", {"a": None, "b": "a", "c": "a", "d": "a", "g": "d", "f": "g", "e": "c"}),
           ("b", {"a": None, "b": "a", "c": "a", "d": "a", "g": "d", "f": "g", "e": "c"}),
       ]
       obtained = [
           (node, predecessors.copy())
           for node, predecessors in depth_first_traversal_iterative_yield_node_and_predecessors(
               graph_example, "a"
           )
       ]
       assert expected == obtained
   

   with explicit paths:

   src

   def depth_first_traversal_iterative_yield_paths_and_distances(
       graph: DirectedWeightedGraph, starting_node: Node
   ) -> Generator[tuple[Node, PathGraph, Weight]]:
       visited = set()
       path: PathGraph = [starting_node]
       starting_distance: Weight = 0.0
       queue: list[tuple[Node, PathGraph, Weight]] = [
           (starting_node, path, starting_distance)
       ]
   
       while queue:
           node, path, distance = queue.pop()
           if node not in visited:
               visited.add(node)
               yield node, path, distance
               for child, distance_child in graph[node].items():
                   queue.append((child, path + [child], distance + distance_child))
   

   tests

   def test_depth_first_traversal_iterative_yield_paths_and_distances(
       graph_example: DirectedWeightedGraph,
   ) -> None:
       expected = [
           ("a", ["a"], 0.0),
           ("d", ["a", "d"], 4.0),
           ("g", ["a", "d", "g"], 9.0),
           ("f", ["a", "d", "g", "f"], 17.0),
           ("c", ["a", "c"], 2.0),
           ("e", ["a", "c", "e"], 3.0),
           ("b", ["a", "b"], 1.0),
       ]
       obtained = list(
           depth_first_traversal_iterative_yield_paths_and_distances(graph_example, "a")
       )
       assert expected == obtained
   

5. The use of a predecessor tree enables to decrease the memory requirement. Indeed, the other solution duplicates all the paths for every visited node. The main drawback of the predecessor tree is that the path has to be reconstructed a posteriori.

Exercise (intermediate)

1. Study the implementation below of the breadth first and uniform cost traversal. Test them.

2. Explain briefly the choice of the queue in both.

3. What is the main difference between the uniform cost implementation and the outlined algorithm above?

src

def breadth_first_traversal_iterative_yield_node(
    graph: DirectedWeightedGraph, starting_node: Node
) -> Generator[Node]:
    visited = set()
    queue = deque([starting_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            yield node
            queue.extend(graph[node])

src

def breadth_first_traversal_iterative_yield_node_and_distances(
    graph: DirectedWeightedGraph, starting_node: Node
) -> Generator[tuple[Node, Weight]]:
    visited = set()
    starting_distance: Weight = 0.0
    queue = deque([(starting_node, starting_distance)])
    while queue:
        node, distance = queue.popleft()
        if node not in visited:
            visited.add(node)
            yield node, distance
            for child, child_distance in graph[node].items():
                queue.append((child, distance + child_distance))

src

def uniform_cost_traversal_iterative_yield_node_and_distances(
    graph: DirectedWeightedGraph, starting_node: Node
) -> Generator[tuple[Node, Weight]]:
    visited = set()
    node = starting_node
    starting_distance: Weight = 0.0
    index: int = 0
    queue = [(starting_distance, index, starting_node)]

    while queue:
        distance, _, node = heapq.heappop(queue)
        if node not in visited:
            visited.add(node)
            yield node, distance
            for child, child_distance in graph[node].items():
                index += 1
                heapq.heappush(queue, (child_distance + distance, index, child))

Correction

tests

@pytest.mark.parametrize(
    "starting_node, expected",
    [
        ("a", ["a", "b", "c", "d", "e", "g", "f"]),
        ("g", ["g", "a", "f", "b", "c", "d", "e"]),
    ],
)
def test_breadth_first_traversal_iterative_yield_node(
    graph_example: DirectedWeightedGraph,
    starting_node: Node,
    expected: PathGraph,
) -> None:
    obtained = list(
        breadth_first_traversal_iterative_yield_node(graph_example, starting_node)
    )
    assert obtained == expected

tests

def test_breadth_first_traversal_iterative_yield_node_and_distances(
    graph_example: DirectedWeightedGraph,
) -> None:
    expected = [
        ("a", 0.0),
        ("b", 1.0),
        ("c", 2.0),
        ("d", 4.0),
        ("e", 4.0),
        ("g", 9.0),
        ("f", 7.0),
    ]
    obtained = list(
        breadth_first_traversal_iterative_yield_node_and_distances(graph_example, "a")
    )
    assert expected == obtained

tests

def test_uniform_cost_traversal_iterative_yield_node_and_distances(
    graph_example: DirectedWeightedGraph,
) -> None:
    expected = [
        ("a", 0.0),
        ("b", 1.0),
        ("c", 2.0),
        ("e", 3.0),
        ("d", 4.0),
        ("f", 6.0),
        ("g", 9.0),
    ]
    obtained = list(
        uniform_cost_traversal_iterative_yield_node_and_distances(graph_example, "a")
    )
    assert expected == obtained

2. BF: the deque acts as a First-In-First-Out queue meaning that nodes are popped in the order of addition. By comparison, the simple list of the DF implementation acts as a Last-In-First-Out queue. The use of a deque is required to maintain a constant complexity of the pop operation on the left of the queue.

   UC: the priority queue maintains an order based on the first parameter of the tuple (total distance). When a node is popped, one gets the node not yet visited with the smallest distance from the starting node.

3. In the outlined algorithm, it is said that “If this new cost is lower than a previously known cost, update it”. However, in this implementation, the node is just re-added in the priority queue with the new (shorter) distance. The previous value is still in the queue, not updated. The visit of the node will be done with the shortest total distance. When, the old distance will pop later on, the node will be already visited and thus ignored.

   A second change is the introduction of an index to avoid comparing nodes if the total distances where to be equal.

Exercise (intermediate)

Implement a uniform cost search from a starting to a target node which returns the path and the distance. Test it. Use explicit paths (not a predecessor tree).

One caveat is that since this not a simple traversal, but a search, the case where the target is not reachable must be considered. It means that a convention must be adopted for the return value in this case: for example, an empty path and an infinite distance.

Correction

src

def uniform_cost_search_iterative_path_and_distance(
    graph: DirectedWeightedGraph, starting_node: Node, target_node: Node
) -> tuple[PathGraph, Weight]:
    visited = set()
    node = starting_node
    starting_distance: Weight = 0.0
    index: int = 0
    queue = [(starting_distance, index, [starting_node])]
    inf = float("inf")

    while queue:
        distance, _, nodes = heapq.heappop(queue)
        node: Node = nodes[-1]
        if node == target_node:
            return nodes, distance
        if node in visited:
            continue

        visited.add(node)
        for child, child_distance in graph[node].items():
            index += 1
            total_distance: Weight = child_distance + distance
            heapq.heappush(queue, (total_distance, index, nodes + [child]))

    return [], inf

tests

@pytest.mark.parametrize(
    "starting_node, target_node, expected",
    [
        ("a", "f", (["a", "c", "e", "f"], 6.0)),
        ("g", "d", (["g", "a", "d"], 5.0)),
    ],
)
def test_uniform_cost_search_iterative_yield_path_and_distance(
    graph_example: DirectedWeightedGraph,
    starting_node: Node,
    target_node: Node,
    expected: PathGraph,
) -> None:
    obtained = list(
        uniform_cost_search_iterative_path_and_distance(
            graph_example, starting_node, target_node
        )
    )
    assert expected[0] == obtained[0]
    assert pytest.approx(expected[1]) == obtained[1]

Note

The three traversal algorithms differ only by the choice of the queue:

• DF: list, last scheduled -> popped

• BF: deque, first scheduled -> popped

• UC: heapq, shortest distance from start -> popped

Note

Two choices for the path:

• predecessor tree (memory efficient, but requires a post treatment to get the path)

• explicit paths (memory costly, every node has his own copy of the path to it)