.. role:: python(code) :language: python .. _`sec:graphs_dag`: .. index:: graph; Directed Acyclic Graph graph; shortest path graph; topological order Directed Acyclic Graph dynamic programming shortest path topological order .. `Shortest path in DAG `_ `Topological order `_ 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. .. _`fig:dag_example`: .. figure:: dag_example.png :width: 200 :alt: dag_example Directed Acyclic Graph example .. admonition:: 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. .. collapse:: 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? .. literalinclude:: ../../../../src/algo/graphs/dag.py :pyobject: shortest_distance_DAG_empty :name: shortest_distance_DAG_empty :linenos: :caption: src .. _`ex:shortest_path_dag`: .. collapse:: Correction 1. The answer to the question in the hint above is: + Assume that :math:`u` has two children :math:`v` and :math:`w` (thus one knows the distances from :math:`u` to :math:`v` and from :math:`u` to :math:`w`, respectively :math:`d_{uv}` and :math:`d_{uw}`) + if I know the shortest distance :math:`d_{vt}` from :math:`v` to the target :math:`t`, and the shortest distance :math:`d_{wt}` from :math:`w` to :math:`t`, the shorted distance :math:`d_{ut}` from :math:`u` to :math:`t` is :math:`\min(d_{uv}+d_{vt}, d_{uw}+d_{wt})` 2. .. literalinclude:: ../../../../src/algo/graphs/dag.py :pyobject: shortest_distance_DAG :name: shortest_distance_DAG :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_dag.py :pyobject: dag :name: dag :linenos: :caption: tests .. literalinclude:: ../../../../tests/algo/graphs/test_dag.py :pyobject: test_shortest_distance_DAG :name: test_shortest_distance_DAG :linenos: :caption: tests .. literalinclude:: ../../../../tests/algo/graphs/test_dag.py :pyobject: test_shortest_distance_DAG_unreachable :name: test_shortest_distance_DAG_unreachable :linenos: :caption: tests 3. Similarly to the traversal algorithms, one has the choice between the predecessors strategy or building the path explicitly. Only one is given below: .. literalinclude:: ../../../../src/algo/graphs/dag.py :pyobject: shortest_distance_and_path_DAG :name: shortest_distance_and_path_DAG :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_dag.py :pyobject: test_shortest_distance_and_path_DAG :name: test_shortest_distance_and_path_DAG :linenos: :caption: tests .. literalinclude:: ../../../../tests/algo/graphs/test_dag.py :pyobject: test_shortest_distance_and_path_DAG_unreachable :name: test_shortest_distance_and_path_DAG_unreachable :linenos: :caption: tests .. .. literalinclude:: ../../../../src/algo/graphs/dag.py .. :pyobject: shortest_distance_and_predecessors_DAG .. :name: shortest_distance_and_predecessors_DAG .. :linenos: .. :caption: src .. .. literalinclude:: ../../../../tests/algo/graphs/test_dag.py .. :pyobject: test_shortest_distance_and_predecessors_DAG .. :name: test_shortest_distance_and_predecessors_DAG .. :linenos: .. :caption: tests Topological order ^^^^^^^^^^^^^^^^^ A topological order of a directed graph is a linear ordering of its nodes such that, for every directed edge :math:`u \rightarrow v` the node :math:`u` appears before :math:`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 :ref:`section Traversal ` is : .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: depth_first_traversal_recursive_yield_nodes :linenos: :caption: src This algorithm yields nodes during traversal, deeper and deeper nodes. If the :python:`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. .. literalinclude:: ../../../../src/algo/graphs/dag.py :pyobject: order_topologically :name: order_topologically :linenos: :caption: src .. admonition:: Exercise (easy) Unfold by hand the previous code assuming a lexicographic order when iterating children of a node. .. _`ex:topological`: .. collapse:: 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)