Abstracting Depth First Search

Depth First Search is applied on a number of algorithms with the same pattern

1. Do some work on the node before exploring any paths
2. For edge of the node
   1. Process the edge before performing search on it
   2. Perform search on the edge
   3. Process the edge after all paths from this edge, got explored
3. Do some work on the node after all paths from this node, got explored

Different algorithms have different demands on how what the graph state should be and which of those steps are required and in what way

The above can be observed on how the Graph State realises the DFSearch trait for Topological sort and Strongly Connected Components implementation

Implementation

As a result, we can define a trait for any Graph State structure, that provide the means of how the pre-processing / post-processing steps should be performed and in relation to the required state and behaviour.

It is important to note here the recursive nature of the search and hence the need for self to maintain the internal state while recursively searching the graph

/// Depth First Search abstraction, enabling a variety of implementations such as, strongly connected components, topological sort, etc
/// The `Path_Search()` default implementation uses the below functions while it leaves their behaviour to the trait implementer
/// - Node pre-processing step fn()
/// - Node post-processing step fn()
/// - Node pre-processing edge fn()
/// - abort recursion fn()
/// - Path return fn()
/// - node state fn()
trait DFSearch {
    type Output;

    /// work to be done before edges are explored, that is, discovered but not processed
    /// uses incl. measuring entry time, set node state, etc
    fn pre_process_node(&mut self, node: Node) -> &mut Self;

    /// work to be done after the edges have been explored; hence the node is now processed
    /// uses incl. measuring exit time, set node parent, save node in path, etc
    fn post_process_node(&mut self, node: Node) -> &mut Self;

    /// work to be done after the node pre-processed and before the edges is explored
    /// uses incl. check for loops, categorize edge into types, etc
    /// default implementation does nothing otherwise you have to override
    fn pre_process_edge(&mut self, _edge: Edge) -> &mut Self { self }

    /// Abort the recursion
    /// uses incl. detecting the graph is not Direct acyclic, etc
    fn abort(&self) -> bool { false }

    /// return the path at position and given the pre/post processing steps
    fn path(&self) -> &Self::Output;

    /// return whether the node has been seen before
    fn is_discovered(&self, node: Node) -> bool;

    /// Default implementation of depth first search
    fn path_search(&mut self, g: &Graph, start: Node) -> Option<&Self::Output> {
        // Entering the node at time tick()
        if self.pre_process_node(start).abort() { return None }

        // processing the edges
        // println!("Enter: {start}:{:?}", self.tracker[start]);
        if let Some(edges) = g.edges.get(&start) {
            for &dst in edges {
                let d = dst;

                if self.pre_process_edge(Edge(start,d)).abort() { return None };

                if !self.is_discovered(d.into()) {
                    self.path_search(g, d.into());
                }
            }
        }
        // Exiting the node at time tick()
        if self.post_process_node(start).abort() { return None };
        // println!("Exit: {start}:{:?}", self.tracker[start]);
        Some(self.path())
    }
}