wolf-graph 0.1.0

use std::marker::PhantomData;

use anyhow::Result;

use crate::{DFSVisitor, DepthFirstSearch, EdgeID, Error, NodeID, Nodes, VisitableGraph};

/// A trait for a graph that supports topological sort.
pub trait TopologicalSort {
    type Graph: VisitableGraph;

    /// Returns reverse-order of topological sort.
    fn topological_sort_opt(&self, roots: &Nodes, roots_only: bool) -> Result<Vec<NodeID>>;

    /// Returns reverse-order of topological sort.
    fn topological_sort(&self) -> Result<Vec<NodeID>> {
        self.topological_sort_opt(&Nodes::new(), false)
    }

    fn is_dag(&self) -> bool {
        self.topological_sort().is_ok()
    }
}

impl<G> TopologicalSort for G
where
    G: VisitableGraph,
{
    type Graph = G;

    fn topological_sort_opt(&self, roots: &Nodes, roots_only: bool) -> Result<Vec<NodeID>> {
        let mut visitor = TopologicalSortVisitor::with_capacity(self.node_count());
        self.depth_first_search_opt(&mut visitor, roots, roots_only, None::<EdgeID>)
    }
}

pub struct TopologicalSortVisitor<Graph>
where
    Graph: VisitableGraph,
{
    order: Vec<NodeID>,
    graph: PhantomData<Graph>,
}

impl<Graph> TopologicalSortVisitor<Graph>
where
    Graph: VisitableGraph,
{
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            order: Vec::with_capacity(capacity),
            graph: PhantomData
        }
    }
}

impl<Graph> DFSVisitor for TopologicalSortVisitor<Graph>
where
    Graph: VisitableGraph,
{
    type Graph = Graph;
    type Output = Vec<NodeID>;

    fn back_edge(&mut self, _graph: &Self::Graph, _edge: &EdgeID) -> Result<Option<Self::Output>> {
        Err(Error::NotADAG.into())
    }

    fn finish_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<Self::Output>> {
        self.order.push(node.clone());
        Ok(None)
    }

    fn finish(&mut self, _graph: &Self::Graph) -> Result<Self::Output> {
        Ok(self.order.clone().into_iter().rev().collect())
    }
}