luka 0.4.0

use crate::{Vertex, Graph};
use crate::error::{GraphError, ErrorKind};
use crate::algorithms::{VisitorDFS, VisitorDFSAction, dfs_with_visitor};

struct CustomVisitor {
    orders: Vec<usize>,
    visited: Vec<bool>
}
impl <T> VisitorDFS<T> for CustomVisitor {
    fn exit_from_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
        if !self.visited[vertex.id()] {
            self.visited[vertex.id()] = true;
            self.orders.push(vertex.id());
            Ok(VisitorDFSAction::Nothing)
        } else {
            Ok(VisitorDFSAction::Break)
        }
    }
    fn entry_to_grey_vertex_event(&mut self, vertex: &Vertex<T>, _parent: &Vertex<T>, _grand_parent: Option<&Vertex<T>>) -> Result<VisitorDFSAction, GraphError> {
        Err(GraphError::Regular(ErrorKind::ExistsCycle(vertex.id())))
    }
}

/// The problem of topological sorting of a graph is as follows: specify such a linear order on its vertices that any edge leads from a vertex with a smaller number to a vertex with a larger number.
/// Obviously, if the graph has cycles, there is no such order. Algorithmic complexity - O(|V| + |E|), where |V| is the number of vertexs in the graph and |E| is the number of edges in the graph.
///
/// ```
/// use luka::{Graph, algorithms};
///
/// let mut graph = Graph::new(5);
///
/// graph.add_edge(1, 2, 0.0).unwrap();
/// graph.add_edge(1, 3, 0.0).unwrap();
/// graph.add_edge(1, 5, 0.0).unwrap();
/// graph.add_edge(1, 4, 0.0).unwrap();
/// graph.add_edge(2, 4, 0.0).unwrap();
/// graph.add_edge(3, 4, 0.0).unwrap();
/// graph.add_edge(3, 5, 0.0).unwrap();
/// let vertexes = algorithms::topoligical_sort(&graph).unwrap();
/// assert_eq!(vertexes.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 3, 5, 2, 4]);
///
/// let mut graph = Graph::new(5);
///
/// graph.add_edge(1, 2, 0.0).unwrap();
/// graph.add_edge(2, 3, 0.0).unwrap();
/// graph.add_edge(3, 4, 0.0).unwrap();
/// graph.add_edge(4, 2, 0.0).unwrap();
/// match algorithms::topoligical_sort(&graph) {
///     Ok(_) => { }
///     Err(err) => {
///         // Found cycle
///         println!("{}", err);
///     }
/// }
/// ```

pub fn topoligical_sort<T>(graph: &Graph<T>) -> Result<Vec<&Vertex<T>>, GraphError> {
    let mut visitor = CustomVisitor{ orders: vec![], visited: vec![false; graph.size()] };
    for from in 1..graph.size() {
        if !visitor.visited[from] {
            dfs_with_visitor(graph, graph.get_vertex(from)?, &mut visitor)?;
        }
    }
    let vertexes = visitor.orders.iter().rev().map(|id| &graph.adj[*id]).collect::<Vec<&Vertex<T>>>();
    Ok(vertexes)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_topology_sort() {
        let mut graph = Graph::new(5);

        graph.add_edge(1, 2, 0.0).unwrap();
        graph.add_edge(1, 3, 0.0).unwrap();
        graph.add_edge(1, 5, 0.0).unwrap();
        graph.add_edge(1, 4, 0.0).unwrap();
        graph.add_edge(2, 4, 0.0).unwrap();
        graph.add_edge(3, 4, 0.0).unwrap();
        graph.add_edge(3, 5, 0.0).unwrap();
        let vertexes = topoligical_sort(&graph).unwrap();
        assert_eq!(vertexes.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 3, 5, 2, 4]);

        let mut graph = Graph::new(8);
        graph.add_edge(1, 2, 0.0).unwrap();
        graph.add_edge(1, 3, 0.0).unwrap();
        graph.add_edge(1, 5, 0.0).unwrap();
        graph.add_edge(1, 4, 0.0).unwrap();
        graph.add_edge(2, 4, 0.0).unwrap();
        graph.add_edge(3, 4, 0.0).unwrap();
        graph.add_edge(3, 5, 0.0).unwrap();
        graph.add_edge(6, 7, 0.0).unwrap();
        graph.add_edge(7, 8, 0.0).unwrap();
        let vertexes = topoligical_sort(&graph).unwrap();
        assert_eq!(vertexes.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![6, 7, 8, 1, 3, 5, 2, 4]);

        let mut graph = Graph::new(10);
        graph.add_edge(2, 4, 0).unwrap();
        graph.add_edge(2, 5, 0).unwrap();
        graph.add_edge(2, 1, 0).unwrap();
        graph.add_edge(3, 1, 0).unwrap();
        graph.add_edge(4, 5, 0).unwrap();
        graph.add_edge(4, 3, 0).unwrap();
        graph.add_edge(5, 3, 0).unwrap();
        let vertexes = topoligical_sort(&graph).unwrap();
        assert_eq!(vertexes.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![10, 9, 8, 7, 6, 2, 4, 5, 3, 1]);
    }

    #[test]
    #[should_panic]
    fn test_exists_cycle_topology_sort() {
        let mut graph = Graph::new(5);

        graph.add_edge(1, 2, 0.0).unwrap();
        graph.add_edge(2, 3, 0.0).unwrap();
        graph.add_edge(3, 4, 0.0).unwrap();
        graph.add_edge(4, 2, 0.0).unwrap();
        let vertexes = topoligical_sort(&graph).unwrap();
        assert_eq!(vertexes.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 3, 5, 2, 4]);
    }
}