luka 0.4.0

Library for working with graphs
Documentation 
use crate::{Graph, Vertex};
use crate::algorithms::{VisitorDFS, VisitorDFSAction, dfs_with_visitor};
use crate::error::GraphError;
use crate::stack::Stack;

struct CustomVisitor {
    visited: Vec<bool>,
    stack: Stack<usize>,
    cycle: Option<Vec<usize>>,
}
impl <T> VisitorDFS<T> for CustomVisitor {
    fn entry_to_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
        self.stack.push(vertex.id);
        Ok(VisitorDFSAction::Nothing)
    }
    fn exit_from_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
        self.stack.pop();
        self.visited[vertex.id()] = true;
        Ok(VisitorDFSAction::Nothing)
    }
    fn entry_to_grey_vertex_event(&mut self, vertex: &Vertex<T>, _parent: &Vertex<T>, grand_parent: Option<&Vertex<T>>) -> Result<VisitorDFSAction, GraphError> {
        if self.cycle.is_none() && vertex.id != grand_parent.unwrap().id {
            let mut start = self.stack.pop().unwrap();
            let mut cycle = vec![start];
            while start != vertex.id() {
                start = self.stack.pop().unwrap();
                cycle.push(start);
            }
            cycle.reverse();
            self.cycle = Some(cycle);
            return Ok(VisitorDFSAction::Break);
        }
        Ok(VisitorDFSAction::Nothing)
    }
}

struct CustomVisitorOrientedGraph {
    visited: Vec<bool>,
    stack: Stack<usize>,
    cycle: Option<Vec<usize>>,
}

impl <T> VisitorDFS<T> for CustomVisitorOrientedGraph {
    fn entry_to_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
        self.stack.push(vertex.id);
        Ok(VisitorDFSAction::Nothing)
    }
    fn exit_from_vertex_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
        self.stack.pop();
        self.visited[vertex.id()] = true;
        Ok(VisitorDFSAction::Nothing)
    }
    fn entry_to_grey_vertex_event(&mut self, vertex: &Vertex<T>, _parent: &Vertex<T>, _grand_parent: Option<&Vertex<T>>) -> Result<VisitorDFSAction, GraphError> {
        let mut start = self.stack.pop().unwrap();
        let mut cycle = vec![start];
        while start != vertex.id() {
            start = self.stack.pop().unwrap();
            cycle.push(start);
        }
        cycle.reverse();
        self.cycle = Some(cycle);
        Ok(VisitorDFSAction::Nothing)
    }
}

///
/// Find cycle in the not oriented graph
///
/// ```
/// use luka::{Graph, algorithms};
///
/// let mut graph = Graph::new(10);
/// graph.add_edge(1, 2, 0).unwrap();
/// graph.add_edge(2, 1, 0).unwrap();
/// graph.add_edge(2, 3, 0).unwrap();
/// graph.add_edge(3, 2, 0).unwrap();
///
/// assert_eq!(algorithms::find_cycle(&graph).unwrap().is_none(), true);
///
/// graph.add_edge(3, 1, 0).unwrap();
/// graph.add_edge(1, 3, 0).unwrap();
///
/// assert_eq!(algorithms::find_cycle(&graph).unwrap().unwrap().iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3]);
/// ```

pub fn find_cycle<T>(graph: &Graph<T>) -> Result<Option<Vec<&Vertex<T>>>, GraphError> {
    let mut visitor = CustomVisitor{ visited: vec![false; graph.size()], stack: Stack::new(), cycle: None};
    for from in 1..graph.size() {
        if !visitor.visited[from] {
            dfs_with_visitor(graph, graph.get_vertex(from)?, &mut visitor)?;
        }
    }
    match visitor.cycle {
        Some(values) => {
            let cycle = values.iter().map(|id| &graph.adj[*id]).collect::<Vec<&Vertex<T>>>();
            Ok(Some(cycle))
        }
        None => Ok(None)
    }
}

///
/// Find cycle in the oriented graph
///
/// ```
/// use luka::{Graph, algorithms};
///
/// let mut graph = Graph::new(10);
/// graph.add_edge(1, 2, 0).unwrap();
/// graph.add_edge(2, 3, 0).unwrap();
/// assert!(algorithms::find_oriented_cycle(&graph).unwrap().is_none());
/// graph.add_edge(3, 1, 0).unwrap();
/// assert_eq!(algorithms::find_oriented_cycle(&graph).unwrap().unwrap().iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3]);
/// ```

pub fn find_oriented_cycle<T>(graph: &Graph<T>) -> Result<Option<Vec<&Vertex<T>>>, GraphError> {
    let mut visitor = CustomVisitorOrientedGraph{ visited: vec![false; graph.size()], stack: Stack::new(), cycle: None};
    for from in 1..graph.size() {
        if !visitor.visited[from] {
            dfs_with_visitor(graph, graph.get_vertex(from)?, &mut visitor)?;
        }
    }
    match visitor.cycle {
        Some(values) => {
            let cycle = values.iter().map(|id| &graph.adj[*id]).collect::<Vec<&Vertex<T>>>();
            Ok(Some(cycle))
        }
        None => Ok(None)
    }
}

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

    #[test]
    fn test_find_cycle() {
        let mut graph = Graph::new(10);
        graph.add_edge(1, 2, 0).unwrap();
        graph.add_edge(2, 1, 0).unwrap();
        graph.add_edge(2, 3, 0).unwrap();
        graph.add_edge(3, 2, 0).unwrap();
        assert!(find_cycle(&graph).unwrap().is_none());
        graph.add_edge(3, 1, 0).unwrap();
        graph.add_edge(1, 3, 0).unwrap();
        assert_eq!(find_cycle(&graph).unwrap().unwrap().iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3]);

        let mut graph = Graph::new(10);
        graph.add_edge(3, 4, 0).unwrap();
        graph.add_edge(4, 3, 0).unwrap();
        graph.add_edge(4, 5, 0).unwrap();
        graph.add_edge(5, 4, 0).unwrap();
        graph.add_edge(5, 7, 0).unwrap();
        graph.add_edge(7, 5, 0).unwrap();
        graph.add_edge(3, 7, 0).unwrap();
        graph.add_edge(7, 3, 0).unwrap();

        graph.add_edge(1, 8, 0).unwrap();
        graph.add_edge(8, 1, 0).unwrap();
        graph.add_edge(8, 9, 0).unwrap();
        graph.add_edge(9, 8, 0).unwrap();
        graph.add_edge(9, 1, 0).unwrap();
        graph.add_edge(1, 9, 0).unwrap();
        assert_eq!(find_cycle(&graph).unwrap().unwrap().iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), vec![1, 8, 9]);
    }

    #[test]
    fn test_find_oriented_cycle() {
        let mut graph = Graph::new(10);
        graph.add_edge(1, 2, 0).unwrap();
        graph.add_edge(2, 3, 0).unwrap();
        assert!(find_oriented_cycle(&graph).unwrap().is_none());
        graph.add_edge(3, 1, 0).unwrap();
        assert_eq!(find_oriented_cycle(&graph).unwrap().unwrap().iter().map(|vertex| vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 3]);
    }
}