luka 0.4.0

use crate::{Graph, Vertex};
use crate::error::GraphError;
use crate::algorithms::dfs::VisitorDFSAction::Nothing;
use crate::algorithms::definitions::Parents;

#[derive(PartialEq, Copy, Clone)]
pub enum Color {
    White = 0,
    Grey = 1,
    Black = 2
}

pub fn _dfs<'a, 'b, T>(graph: &'a Graph<T>, from: usize, parents: &mut[Option<&'a Vertex<T>>], colors: & 'b mut [Color]) {
    colors[from] = Color::Grey;
    for edge in &graph.adj[from].edges {
        if colors[edge.to] == Color::White {
            parents[edge.to] = Some(&graph.adj[from]);
            _dfs(graph, edge.to, parents, colors);
        }
    }
    colors[from] = Color::Black;
}

///
/// Depth-first search (DFS) - one of the methods of graph traversal 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.
///
/// ```rust
/// use luka::Graph;
/// use luka::utils;
/// use luka::algorithms;
///
/// let mut graph = Graph::new(10);
///
/// graph.add_edge(1, 2, 0.0).unwrap();
/// graph.add_edge(2, 3, 0.0).unwrap();
/// graph.add_edge(3, 5, 0.0).unwrap();
///
/// let start = graph.get_vertex(1).unwrap();
/// let target = graph.get_vertex(5).unwrap();
/// let parents = algorithms::dfs(&graph, &start).unwrap();
/// match utils::find_path(&graph, &target, &parents).unwrap() {
///     Some(path) => {
///         assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3, 5]);
///     }
///     None => {
///         println!("Path not found !!!")
///     }
/// }
/// ```

pub fn dfs<'a, T>(graph: &'a Graph<T>, from: &'a Vertex<T>) -> Result<Parents<'a, T>, GraphError> {
    let mut parents = vec![None; graph.size()];
    let mut colors = vec![Color::White; graph.size()];
    parents[from.id()] = None;
    _dfs(graph, from.id(), &mut parents, &mut colors);
    Ok(parents)
}

/// Allows DFS algorithm to be extended with callbacks on specific events
pub trait VisitorDFS<T> {
    #[allow(unused_variables)]
    fn entry_to_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
        Ok(Nothing)
    }
    #[allow(unused_variables)]
    fn entry_to_white_vertex_event(&mut self, vertex: &Vertex<T>, parent: &Vertex<T>, grand_parent: Option<&Vertex<T>>) -> Result<VisitorDFSAction, GraphError> {
        Ok(Nothing)
    }
    #[allow(unused_variables)]
    fn exit_from_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
        Ok(Nothing)
    }
    #[allow(unused_variables)]
    fn exit_from_white_vertex_event(&mut self, vertex: &Vertex<T>, parent: &Vertex<T>, grand_parent: Option<&Vertex<T>>) -> Result<VisitorDFSAction, GraphError> {
        Ok(Nothing)
    }
    #[allow(unused_variables)]
    fn entry_to_grey_vertex_event(&mut self, vertex: &Vertex<T>, parent: &Vertex<T>, grand_parent: Option<&Vertex<T>>) -> Result<VisitorDFSAction, GraphError> {
        Ok(Nothing)
    }
}

#[derive(PartialEq)]
pub enum VisitorDFSAction {
    Nothing,
    Break,
    Err(GraphError)
}

pub fn _dfs_with_visitor<'a, 'b, T>(graph: &'a Graph<T>, from: usize, parents: &mut[Option<&'a Vertex<T>>], colors: & 'b mut [Color], visitor: &'b mut dyn VisitorDFS<T>) -> Result<(), GraphError> {
    colors[from] = Color::Grey;
    match visitor.entry_to_vertex_event(&graph.adj[from])? {
        VisitorDFSAction::Nothing => {}
        VisitorDFSAction::Break => {
            return Ok(());
        }
        VisitorDFSAction::Err(err) => {
            return Err(err);
        }
    }
    for edge in &graph.adj[from].edges {
        if colors[edge.to] == Color::White {
            parents[edge.to] = Some(&graph.adj[from]);
            match visitor.entry_to_white_vertex_event(&graph.adj[edge.to], &graph.adj[from], parents[from])? {
                VisitorDFSAction:: Nothing => {}
                VisitorDFSAction::Break => {
                    return Ok(());
                }
                VisitorDFSAction::Err(err) => {
                    return Err(err);
                }
            }
            _dfs_with_visitor(graph, edge.to, parents, colors, visitor)?;
            match visitor.exit_from_white_vertex_event(&graph.adj[edge.to], &graph.adj[from], parents[from])? {
                VisitorDFSAction:: Nothing => {}
                VisitorDFSAction::Break => {
                    return Ok(());
                }
                VisitorDFSAction::Err(err) => {
                    return Err(err);
                }
            }
        }
        if colors[edge.to] == Color::Grey {
            match visitor.entry_to_grey_vertex_event(&graph.adj[edge.to], &graph.adj[from], parents[from])? {
                VisitorDFSAction:: Nothing => {}
                VisitorDFSAction::Break => {
                    return Ok(());
                }
                VisitorDFSAction::Err(err) => {
                    return Err(err);
                }
            }
        }
    }
    colors[from] = Color::Black;
    match visitor.exit_from_vertex_event(&graph.adj[from])? {
        VisitorDFSAction::Nothing => {}
        VisitorDFSAction::Break => {
            return Ok(());
        }
        VisitorDFSAction::Err(err) => {
            return Err(err)
        }
    }
    Ok(())
}

///
/// Depth-first search (DFS) - one of the methods of graph traversal 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.
/// Used by a visitor you can intercept certain events of the algorithm
///
/// ```rust
/// use luka::Graph;
/// use luka::Vertex;
/// use luka::algorithms;
/// use luka::algorithms::{VisitorDFS, VisitorDFSAction};
/// use luka::utils;
/// use luka::error::GraphError;
///
/// struct CustomVisitor {
///     visiting_order: Vec<usize>
/// }
///
/// impl <T> VisitorDFS<T> for CustomVisitor {
///     fn entry_to_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
///         self.visiting_order.push(vertex.id());
///         Ok(VisitorDFSAction::Nothing)
///     }
/// }
///
/// let mut graph = Graph::new(10);
///
/// graph.add_edge(1, 2, 0.0).unwrap();
/// graph.add_edge(2, 3, 0.0).unwrap();
/// graph.add_edge(3, 5, 0.0).unwrap();
///
/// let mut visitor = CustomVisitor{ visiting_order: vec![] };
/// let start = graph.get_vertex(1).unwrap();
/// algorithms::dfs_with_visitor(&graph, &start, &mut visitor).unwrap();
///
/// assert_eq!(vec![1, 2, 3, 5], visitor.visiting_order);
/// ```

pub fn dfs_with_visitor<'a, 'b, T>(graph: &'a Graph<T>, from: &'a Vertex<T>, visitor: &'b mut dyn VisitorDFS<T>) -> Result<Parents<'a, T>, GraphError> {
    let mut parents = vec![None; graph.size()];
    let mut colors = vec![Color::White; graph.size()];
    parents[from.id()] = None;
    _dfs_with_visitor(graph, from.id(), &mut parents, &mut colors, visitor)?;
    Ok(parents)
}

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

    #[test]
    fn test_dfs_algorithm(){
        use crate::utils;
        let mut graph = Graph::new(10);

        graph.add_edge(1, 2, 0.0).unwrap();
        graph.add_edge(2, 3, 0.0).unwrap();
        graph.add_edge(3, 5, 0.0).unwrap();

        let start = graph.get_vertex(1).unwrap();
        let target = graph.get_vertex(5).unwrap();
        let parents = dfs(&graph, &start).unwrap();
        match utils::find_path(&graph, &target, &parents).unwrap() {
            Some(path) => {
                assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3, 5]);
            }
            None => {
                println!("Path not found !!!")
            }
        }

        let mut graph = Graph::new(10);

        graph.add_edge(1, 2, 0.0).unwrap();
        graph.add_edge(2, 3, 0.0).unwrap();
        graph.add_edge(3, 1, 0.0).unwrap();

        let start = graph.get_vertex(1).unwrap();
        let target = graph.get_vertex(5).unwrap();
        let parents = dfs(&graph, &start).unwrap();
        match utils::find_path(&graph, &target, &parents).unwrap() {
            Some(path) => {
                assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3]);
            }
            None => {
                println!("Path not found !!!")
            }
        }
    }

    #[test]
    #[should_panic]
    fn test_dfs_algorithm_panic() {
        let mut graph = Graph::new(100);
        graph.add_edge(1, 2, 0.0).unwrap();
        let start = graph.get_vertex(122).unwrap();
        dfs(&graph, &start).unwrap();
    }

    #[test]
    fn test_dfs_with_visitor_algorithm(){
        struct CustomVisitor {
            visiting_order: Vec<usize>
        }

        impl <T> VisitorDFS<T> for CustomVisitor {
            fn entry_to_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
                self.visiting_order.push(vertex.id());
                Ok(VisitorDFSAction::Nothing)
            }
        }

        let mut graph = Graph::new(10);

        graph.add_edge(1, 2, 0.0).unwrap();
        graph.add_edge(2, 3, 0.0).unwrap();
        graph.add_edge(3, 5, 0.0).unwrap();

        let mut visitor = CustomVisitor{ visiting_order: vec![] };
        let start = graph.get_vertex(1).unwrap();
        dfs_with_visitor(&graph, &start, &mut visitor).unwrap();

        assert_eq!(vec![1, 2, 3, 5], visitor.visiting_order);
    }
}