backtracking_cyclic_graph_example.cc File Reference

Reference example: DFS/backtracking on a cyclic directed graph using a depth-aware visited map (SearchStorageMap) to avoid loops. More...

#include <cstddef>
#include <iostream>
#include <State_Search.H>

Include dependency graph for backtracking_cyclic_graph_example.cc:

Go to the source code of this file.

Classes
struct	GraphState
struct	CyclicGraphDomain
struct	CyclicGraphDomain::Move

Functions
int	main ()

Detailed Description

Reference example: DFS/backtracking on a cyclic directed graph using a depth-aware visited map (SearchStorageMap) to avoid loops.

Without cycle detection, a DFS on a graph with back-edges would loop indefinitely. Passing a SearchStorageMap<Key, size_t> to Depth_First_Backtracking::search() turns the tree-search into a graph-search: each state is recorded with the depth at which it was first reached. When the same state is encountered again via a longer path, it is pruned. Via a shorter path the stored depth is updated and exploration continues.

Graph used in this example (directed):

0 ──► 1 ──► 0  (back-edge, creates a cycle)
      │
      ▼
      2 ──► 3  (goal)

Without visited tracking the engine would loop between nodes 0 and 1 forever. With visited tracking it prunes the 1→0 back-edge and finds the goal at node 3 via the path 0→1→2→3.

Build and run:

• cmake --build build --target backtracking_cyclic_graph_example
• ./build/Examples/backtracking_cyclic_graph_example

Definition in file backtracking_cyclic_graph_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 131 of file backtracking_cyclic_graph_example.cc.

References engine.