luka 0.4.0

use crate::{Graph, Vertex, utils};
use crate::algorithms::{VisitorDFS, dfs_with_visitor, VisitorBFS, bfs_with_visitor, VisitorDFSAction, VisitorBFSAction};
use crate::error::GraphError;
use crate::algorithms::definitions::ConnectedComponents;

struct CustomVisitor {
    orders: Vec<usize>
}
impl <T> VisitorBFS<T> for CustomVisitor {
    fn vertex_visited_event(&mut self, vertex: &Vertex<T>, _parents: &[Option<&Vertex<T>>]) -> Result<VisitorBFSAction, GraphError> {
        self.orders.push(vertex.id());
        Ok(VisitorBFSAction::Nothing)
    }
}

///
/// Search for connectivity components. The algorithm works with an undirected graph.
/// The algorithm divides the vertices of the graph into several groups, so that within one group one can reach from one vertex to any other, but between different groups there is no path.
/// 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;
/// use luka::algorithms;
///
/// let mut graph = Graph::new(11);
///
/// 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(5, 6, 0.0).unwrap();
/// graph.add_edge(6, 7, 0.0).unwrap();
///
/// graph.add_edge(8, 9, 0.0).unwrap();
/// graph.add_edge(9, 10, 0.0).unwrap();
/// graph.add_edge(10, 11, 0.0).unwrap();
///
/// let components = algorithms::find_connected_components(&graph).unwrap();
/// assert_eq!(components[0].iter().map(|elem| elem.id()).collect::<Vec<usize>>(), [1, 2, 3, 4]);
/// assert_eq!(components[1].iter().map(|elem| elem.id()).collect::<Vec<usize>>(), [5, 6, 7]);
/// assert_eq!(components[2].iter().map(|elem| elem.id()).collect::<Vec<usize>>(), [8, 9, 10, 11]);
/// assert_eq!(components.len(), 3);
/// ```

pub fn find_connected_components<T>(graph: &Graph<T>) -> Result<Vec<Vec<& Vertex<T>>>, GraphError> {
    let mut components = vec![];
    let mut visited = vec![false; graph.size()];
    for from in 1..graph.size() {
        let from = graph.get_vertex(from)?;
        if !visited[from.id()] {
            let mut visitor = CustomVisitor{ orders: vec![] };
            bfs_with_visitor(graph, from, &mut visitor)?;
            let mut vec = vec![];
            for vertex in visitor.orders {
                vec.push(&graph.adj[vertex]);
                visited[vertex] = true;
            }
            components.push(vec)
        }
    }
    Ok(components)
}

struct CustomVisitorFirst {
    orders: Vec<usize>,
    visited: Vec<bool>
}
impl <T> VisitorDFS<T> for CustomVisitorFirst {
    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)
        }
    }
}

struct CustomVisitorSecond {
    orders: Vec<usize>,
    visited: Vec<bool>
}
impl <T> VisitorDFS<T> for CustomVisitorSecond {
    fn entry_to_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)
        }
    }
}

/// A strong connectivity component is a subset of vertices (maximal inclusion) such that any two vertices of this subset are reachable from each other.
/// The graph is oriented. 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;
/// use luka::algorithms;
///
/// let mut graph = Graph::new(8);
///
/// graph.add_edge(1, 2, 0.0).unwrap();
/// graph.add_edge(2, 6, 0.0).unwrap();
/// graph.add_edge(5, 1, 0.0).unwrap();
/// graph.add_edge(2, 5, 0.0).unwrap();
/// graph.add_edge(5, 6, 0.0).unwrap();
///
/// graph.add_edge(2, 3, 0.0).unwrap();
/// graph.add_edge(6, 7, 0.0).unwrap();
/// graph.add_edge(7, 6, 0.0).unwrap();
/// graph.add_edge(3, 7, 0.0).unwrap();
///
/// graph.add_edge(3, 4, 0.0).unwrap();
/// graph.add_edge(4, 3, 0.0).unwrap();
/// graph.add_edge(4, 8, 0.0).unwrap();
/// graph.add_edge(8, 4, 0.0).unwrap();
/// graph.add_edge(8, 7, 0.0).unwrap();
///
/// let components = algorithms::find_strongly_connected_components_search(&graph).unwrap();
/// assert_eq!(components[0].iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), [6, 7]);
/// assert_eq!(components[1].iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), [3, 4, 8]);
/// assert_eq!(components[2].iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), [1, 2, 5]);
/// ```

pub fn find_strongly_connected_components_search<T>(graph: &Graph<T>) -> Result<ConnectedComponents<T>, GraphError> where T: Copy {
    let graph_transp = utils::transpose(graph);
    let mut components = vec![];
    let mut orders = Vec::with_capacity(graph.size());
    let mut visitor = CustomVisitorFirst {orders: vec![], visited: vec![false; graph.size()] };
    for from in 1..graph.size() {
        if !visitor.visited[from] {
            dfs_with_visitor(&graph_transp, graph.get_vertex(from)?,  &mut visitor)?;
            for vertex in &visitor.orders {
                orders.push(*vertex);
            }
        }
    }
    let mut visitor = CustomVisitorSecond {orders: vec![], visited: vec![false; graph.size()] };
    for from in orders.iter().rev() {
        if !visitor.visited[*from] {
            visitor.orders.clear();
            let mut component = vec![];
            dfs_with_visitor(graph, graph.get_vertex(*from)?,  &mut visitor)?;
            for vertex in &visitor.orders {
                component.push(&graph.adj[*vertex]);
            }
            components.push(component);
        }
    }
    Ok(components)
}

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

    #[cfg(test)]
    #[test]
    fn test_find_strongly_connected_components() {
        let mut graph = Graph::new(8);

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

        graph.add_edge(2, 3, 0.0).unwrap();
        graph.add_edge(6, 7, 0.0).unwrap();
        graph.add_edge(7, 6, 0.0).unwrap();
        graph.add_edge(3, 7, 0.0).unwrap();

        graph.add_edge(3, 4, 0.0).unwrap();
        graph.add_edge(4, 3, 0.0).unwrap();
        graph.add_edge(4, 8, 0.0).unwrap();
        graph.add_edge(8, 4, 0.0).unwrap();
        graph.add_edge(8, 7, 0.0).unwrap();

        let components = find_strongly_connected_components_search(&graph).unwrap();
        assert_eq!(components[0].iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), [6, 7]);
        assert_eq!(components[1].iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), [3, 4, 8]);
        assert_eq!(components[2].iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), [1, 2, 5]);
    }

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

        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(5, 6, 0.0).unwrap();
        graph.add_edge(6, 7, 0.0).unwrap();

        graph.add_edge(8, 9, 0.0).unwrap();
        graph.add_edge(9, 10, 0.0).unwrap();
        graph.add_edge(10, 11, 0.0).unwrap();

        let components = find_connected_components(&graph).unwrap();
        assert_eq!(components[0].iter().map(|elem| elem.id()).collect::<Vec<usize>>(), [1, 2, 3, 4]);
        assert_eq!(components[1].iter().map(|elem| elem.id()).collect::<Vec<usize>>(), [5, 6, 7]);
        assert_eq!(components[2].iter().map(|elem| elem.id()).collect::<Vec<usize>>(), [8, 9, 10, 11]);
        assert_eq!(components.len(), 3);

        let graph = Graph::<i32>::new(100);
        let components = find_connected_components(&graph).unwrap();
        assert_eq!(components.len(), 100);
    }
}