.. role:: python(code) :language: python .. _`sec:graphs_traversal`: .. index:: graph; Depth First Search graph; Breadth First Search graph; Uniform Cost Search graph; Dijkstra graph; traversal Dijkstra Depth First Search Breadth First Search Uniform Cost Search traversal .. `Graph traversal `_ `Graph Depth First recursive and iterative `_ `Graph Breadth First and Uniform Cost `_ `Graph Uniform Cost Search `_ Traversal --------- Imagine a video game; you have a map of every area you must visit, see the :ref:`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? .. _`fig:graph_example`: .. figure:: graph_traversal_example.png :width: 300 :alt: graphs_traversal_example Graph traversal example From a starting node, the three most obvious way to explore the map: .. _`algo:dfs`: - the go-getter way: **Depth First**, the exploration follows one branch as deeply as possible before going back. .. code-block:: text :linenos: 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. .. _`algo:bfs`: - 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. .. code-block:: text :linenos: 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. .. _`algo:ucs`: - the speed-runner way: **Uniform Cost**, the exploration always expands the least costly path discovered so far. .. code-block:: text :linenos: 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 :ref:`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. .. admonition:: Exercise (easy) Apply (by hand) the three strategies outlined above to the :ref:`graph ` above starting from "a". Assume a lexicographic order when looping over children (in reality this lexicographic order is not enforced). .. _`ex:graphs_traversal_hand`: .. collapse:: 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: .. literalinclude:: ../../../../src/algo/graphs/graph_types.py :name: graph_types :linenos: :caption: src .. admonition:: 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 :ref:`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? .. _`ex:graphs_DFS_recursive_iterative`: .. collapse:: Correction 1. recursive .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: depth_first_traversal_recursive_simple_print :name: depth_first_traversal_recursive_simple_print :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: graph_example :name: graph_example :linenos: :caption: tests .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_depth_first_traversal_recursive_simple_print :name: test_depth_first_traversal_recursive_simple_print :linenos: :caption: tests .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: depth_first_traversal_recursive_yield_nodes :name: depth_first_traversal_recursive_yield_nodes :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_depth_first_traversal_recursive_yield_nodes :name: test_depth_first_traversal_recursive_yield_nodes :linenos: :caption: tests 2. iterative .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: depth_first_traversal_iterative_yield_nodes :name: depth_first_traversal_iterative_yield_nodes :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_depth_first_traversal_iterative_yield_nodes :name: test_depth_first_traversal_iterative_yield_nodes :linenos: :caption: tests 3. with predecessors: .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: depth_first_traversal_recursive_yield_node_and_predecessors :name: depth_first_traversal_recursive_yield_node_and_predecessors :linenos: :caption: src .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: rebuild_path_and_distance_from_predecessors :name: rebuild_path_and_distance_from_predecessors :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_depth_first_traversal_recursive_yield_node_and_predecessors :name: test_depth_first_traversal_recursive_yield_node_and_predecessors :linenos: :caption: tests .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_rebuild_path_and_distance_from_predecessors :name: test_rebuild_path_and_distance_from_predecessors :linenos: :caption: tests with explicit paths: .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: depth_first_traversal_recursive_with_paths_and_distances :name: depth_first_traversal_recursive_with_paths_and_distances :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_depth_first_traversal_recursive_with_paths_and_distances :name: test_depth_first_traversal_recursive_with_paths_and_distances :linenos: :caption: tests 4. with predecessors: .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: depth_first_traversal_iterative_yield_node_and_predecessors :name: depth_first_traversal_iterative_yield_node_and_predecessors :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_depth_first_traversal_iterative_yield_node_and_predecessors :name: test_depth_first_traversal_iterative_yield_node_and_predecessors :linenos: :caption: tests with explicit paths: .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: depth_first_traversal_iterative_yield_paths_and_distances :name: depth_first_traversal_iterative_yield_paths_and_distances :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_depth_first_traversal_iterative_yield_paths_and_distances :name: test_depth_first_traversal_iterative_yield_paths_and_distances :linenos: :caption: tests 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. .. admonition:: 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 :ref:`algorithm ` above? .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: breadth_first_traversal_iterative_yield_node :name: breadth_first_traversal_iterative_yield_node :linenos: :caption: src .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: breadth_first_traversal_iterative_yield_node_and_distances :name: breadth_first_traversal_iterative_yield_node_and_distances :linenos: :caption: src .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: uniform_cost_traversal_iterative_yield_node_and_distances :name: uniform_cost_traversal_iterative_yield_node_and_distances :linenos: :caption: src .. _`ex:graphs_traversal_BF_UC`: .. collapse:: Correction 1. .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_breadth_first_traversal_iterative_yield_node :name: test_breadth_first_traversal_iterative_yield_node :linenos: :caption: tests .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_breadth_first_traversal_iterative_yield_node_and_distances :name: test_breadth_first_traversal_iterative_yield_node_and_distances :linenos: :caption: tests .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_uniform_cost_traversal_iterative_yield_node_and_distances :name: test_uniform_cost_traversal_iterative_yield_node_and_distances :linenos: :caption: tests 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. .. admonition:: 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. .. _`ex:graphs_UCS`: .. collapse:: Correction .. literalinclude:: ../../../../src/algo/graphs/traversal.py :pyobject: uniform_cost_search_iterative_path_and_distance :name: uniform_cost_search_iterative_path_and_distance :linenos: :caption: src .. literalinclude:: ../../../../tests/algo/graphs/test_traversal.py :pyobject: test_uniform_cost_search_iterative_yield_path_and_distance :name: test_uniform_cost_search_iterative_yield_path_and_distance :linenos: :caption: tests .. note:: The three traversal algorithms differ only by the choice of the queue: + DF: :python:`list`, last scheduled -> popped + BF: :python:`deque`, first scheduled -> popped + UC: :python:`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)