Directed acyclic graphs

Shortest path

A directed graph without cycles is called a Directed Acyclic Graphs. The image below is a DAG. The Uniform Cost Search algorithm is already an efficient solution to find the shortest distance and/or path between two nodes. Besides UCS, for a DAG, a dynamic programming solution exists for the shortest distance and/or path.

dag_example

Directed Acyclic Graph example

Exercise (intermediate)

For DAG, imagine a recursive algorithm to find the shortest distance between two nodes:

  • the shortest distance from a given node to a target should be easily obtainable from its subproblems

  • the subproblems can (or should) overlap to be a good candidate for dynamic programming

  1. Formulate an algorithm.

  2. Implement and test.

  3. Extend to the shortest distance and path.

Hint

If you assume you know the shortest distance from the children of a node to the target, how can you obtain the shortest distance from the node itseld to the target?

src
1def shortest_distance_DAG_empty(
2    graph: DirectedWeightedGraph, source: Node, target: Node
3) -> Weight:
4    @cache
5    def shortest_distance_to_target_from(current: Node) -> Weight: ...
6
7    return 0.0  #
Correction

  1. The answer to the question in the hint above is:

    • Assume that \(u\) has two children \(v\) and \(w\) (thus one knows the distances from \(u\) to \(v\) and from \(u\) to \(w\), respectively \(d_{uv}\) and \(d_{uw}\))

    • if I know the shortest distance \(d_{vt}\) from \(v\) to the target \(t\), and the shortest distance \(d_{wt}\) from \(w\) to \(t\), the shorted distance \(d_{ut}\) from \(u\) to \(t\) is \(\min(d_{uv}+d_{vt}, d_{uw}+d_{wt})\)

  2. src
     1def shortest_distance_DAG(
 2    graph: DirectedWeightedGraph, source: Node, target: Node
 3) -> Weight:
 4    @cache
 5    def shortest_distance_to_target_from(current: Node) -> Weight:
 6        """shortest distance from current to target"""
 7        if current == target:
 8            return 0.0
 9        # assuming that the shortest distance from child / neighbour
10        # to target is known (from recursive call),
11        # then the shortest distance from parent to target is
12        # the minimum of the distances of the paths through every child.
13        distances: list[Weight] = [
14            distance_to_neighbour + shortest_distance_to_target_from(neighbour)
15            for neighbour, distance_to_neighbour in graph[current].items()
16        ]
17        if distances:
18            return min(distances)
19
20        return float("inf")
21
22    return shortest_distance_to_target_from(source)
    tests
     1@pytest.fixture
 2def dag() -> DirectedWeightedGraph:
 3    return {
 4        "a": {
 5            "b": 1.0,
 6            "c": 2.0,
 7            "d": 4.0,
 8        },
 9        "b": {"e": 3.0},
10        "c": {"e": 1.0},
11        "d": {"g": 5.0},
12        "e": {"d": 2.0, "f": 3.0},
13        "f": {},
14        "g": {"f": 8.0},
15    }
    tests
    1def test_shortest_distance_DAG(dag) -> None:
2    distance: Weight = shortest_distance_DAG(dag, "a", "f")
3    assert pytest.approx(distance) == 6.0
    tests
    1def test_shortest_distance_DAG_unreachable(dag) -> None:
2    distance: Weight = shortest_distance_DAG(dag, "a", "z")
3    assert distance == float("inf")

  3. Similarly to the traversal algorithms, one has the choice between the predecessors strategy or building the path explicitly. Only one is given below:

    src
     1def shortest_distance_and_path_DAG(
 2    graph: DirectedWeightedGraph, source: Node, target: Node
 3) -> tuple[Weight, PathGraph]:
 4    @cache
 5    def shortest_distance_and_path_to_target_from(
 6        current: Node,
 7    ) -> tuple[Weight, PathGraph]:
 8        """shortest distance and path from current to target"""
 9        if current == target:
10            return 0.0, [target]
11        # assuming that the shortest distance from child / neighbour
12        # to target is known (from recursive call),
13        # then the shortest distance from parent to target is
14        # the minimum of the distances of the paths through every child.
15        distances_and_paths: list[tuple[Weight, PathGraph]] = []
16        for neighbour, distance_to_neighbour in graph[current].items():
17            future_distance, future_path = shortest_distance_and_path_to_target_from(
18                neighbour
19            )
20            if future_path:
21                distances_and_paths.append(
22                    (distance_to_neighbour + future_distance, [current] + future_path)
23                )
24        if distances_and_paths:
25            return min(distances_and_paths)
26
27        return float("inf"), []
28
29    return shortest_distance_and_path_to_target_from(source)
    tests
    1def test_shortest_distance_and_path_DAG(dag) -> None:
2    distance, path = shortest_distance_and_path_DAG(dag, "a", "f")
3    assert pytest.approx(distance) == 6.0
4    assert path == ["a", "c", "e", "f"]
    tests
    1def test_shortest_distance_and_path_DAG_unreachable(dag) -> None:
2    distance, path = shortest_distance_and_path_DAG(dag, "a", "z")
3    assert distance == float("inf")
4    assert path == []

Topological order

A topological order of a directed graph is a linear ordering of its nodes such that, for every directed edge \(u \rightarrow v\) the node \(u\) appears before \(v\) in the ordering. Think about the order of tasks which can be from one another. A topological order can only be defined on a DAG, any cycle means that two or more tasks may depend on each other, in this case impossible to define which one is the first to accomplish.

The depth first traversal from the section Traversal is :

src
 1def depth_first_traversal_recursive_yield_nodes(
 2    graph: DirectedWeightedGraph, starting_node: Node
 3) -> Generator[Node]:
 4    visited = set()
 5
 6    def _df_recurse(node: Node) -> Generator[Node]:
 7        visited.add(node)
 8        yield node
 9        for child in graph[node]:
10            if child not in visited:
11                yield from _df_recurse(child)
12
13    yield from _df_recurse(starting_node)

This algorithm yields nodes during traversal, deeper and deeper nodes. If the yield is moved at the end, it means that one goes as deep as possible (leaf node) before starting to yield on the way back. It will produce the reverse topological order.

src
 1def order_topologically(
 2    graph: DirectedWeightedGraph, starting_node: Node
 3) -> Generator[Node]:
 4    visited = set()
 5
 6    def _df_recurse(node: Node) -> Generator[Node]:
 7        visited.add(node)
 8        for child in graph[node]:
 9            if child not in visited:
10                yield from _df_recurse(child)
11        yield node
12
13    yield from reversed(list(_df_recurse(starting_node)))

Exercise (easy)

Unfold by hand the previous code assuming a lexicographic order when iterating children of a node.

Correction

From “a”:

  • 1st recursion: “b”

  • 2nd recursion: “e”

  • 3rd recursion: “d”

  • 4th recursion: “g”

  • 5th recursion: “f”

  • 1st yield: “f”

  • 2nd yield: “g”

  • 3rd yield: “d”

  • try to recurse towards “f” but already visited

  • 4th yield “e”

  • 5th yield “b”

  • 6th recursion “c”

  • try to recurse towards “e” but already visited

  • 6th yield “c”

  • 7th yield “a”

Finally: “a”, “c”, “b”, “e”, “d”, “g”, “f”

(an other valid solution is “a”, “b”, “c”, “e”, “d”, “g”, “f” if lexicographic order is not assumed)