Abstracting Breadth First Search

Breadth First Search is applied on a number of algorithms with the same pattern, that is:

1. Initiate processing state with starting node
2. Do some work on the node before exploring any paths
3. For each edge off this node
   1. Process the edge before performing search on it
   2. Push edge node on the queue for further processing
4. Do some work on the node after all edges has been discovered

Different path search algorithms have different demands in terms of

• Queue type, that is, FIFO, LIFO, etc
• Initiation states for starting node
• Pre-processing & post-processing logic required for nodes and edges

The above can be observed on how the Graph State realises the BFSearch trait for Minimum Path Cost and Shortest Distance implementation

Implementation

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

/// Breadth First Search abstraction, that can be used to find shortest distance, lowest cost paths, etc
/// The `Path_Search()` default implementation uses the below functions while it leaves their behaviour to the trait implementer
/// - initiate step fn()
/// - Queue push & pop step fn()
/// - Queue-to-Node and vice versa step fn()
/// - Node pre/post-processing step fn()
/// - Edge pre-processing step fn()
/// - Path return fn()
/// - node state fn()
trait BFSearch {
    type Output;
    type QueueItem;

    /// Initialise the Path search given the starting node
    fn initiate(&mut self, start:Node) -> &mut Self;

    /// Pull an Item from the queue
    fn pop(&mut self) -> Option<Self::QueueItem>;

    /// Extract Node value from a Queued Item
    fn node_from_queued(&self, qt: &Self::QueueItem) -> Node;

    /// Pre-process item retrieved from the queue and before proceeding with queries the Edges
    /// return true to proceed or false to abandon node processing
    fn pre_process_node(&mut self, _node: Node) -> bool { true }

    /// Process node after all edges have been processes and pushed in the queue
    fn post_process_node(&mut self, _node: Node) { }

    /// Has the node been Discovered ?
    fn is_discovered(&self, _node: NodeType) -> bool;

    /// Process the Edge node and
    /// return 'true' to proceed with push or 'false' to skip the edge node
    fn pre_process_edge(&mut self, src: Node, dst: NodeType) -> bool;

    /// Construct a Queued Item from the Node
    fn node_to_queued(&self, node: Node) -> Self::QueueItem;

    /// Push to the queue
    fn push(&mut self, item: Self::QueueItem);

    /// Retrieve path
    fn extract_path(&self, start: Node) -> Self::Output;

    /// Path Search Implementation
    fn path_search(&mut self, g: &Graph, start: Node, goal:Node) -> Option<Self::Output> {
        // initiate BFSearch given a start node
        self.initiate(start);
        // until no items left for processing
        while let Some(qt) = self.pop() {
            //Extract the src node
            let src = self.node_from_queued(&qt);
            // pre-process and if false abandon and proceed to next item
            if !self.pre_process_node(src) { continue };
            // if we have reached our goal return the path
            if src == goal {
                return Some(self.extract_path(goal))
            }
            // given graph's edges
            // get src node's edges and per their NodeType
            if let Some(edges) = g.edges.get(&src) {
                edges.iter()
                    .for_each(|&dst| {
                        // if dst hasn't been visited AND pre-processing results to true,
                        // then push to explore further
                        if !self.is_discovered(dst)
                            && self.pre_process_edge(src, dst) {
                            // push dst node for further processing
                            self.push(self.node_to_queued(dst.into()))
                        }
                    });
                // Process node after edges have been discovered and pushed for further processing
                self.post_process_node(src);
            }
        }
        None
    }
}