luka 0.4.0

Library for working with graphs
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

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

pub struct VerticesDepths<'a, T> {
    values: Vec<Option<usize>>,
    phantom: PhantomData<&'a T>,
}

impl <'a, T> VerticesDepths<'a, T> where T: Copy {
    pub fn get_vertex_depth(&self, target: &Vertex<T>) -> Option<usize> {
        self.values[target.id()]
    }
}

struct CustomVisitor {
    values: Vec<Option<usize>>,
    cycle: bool
}

impl<T> VisitorDFS<T> for  CustomVisitor {
    fn entry_to_vertex_event(&mut self, _vertex: &Vertex<T>) -> Result<VisitorDFSAction, GraphError> {
        Ok(VisitorDFSAction::Nothing)
    }
    fn entry_to_white_vertex_event(&mut self, vertex: &Vertex<T>, parent: &Vertex<T>, _grand_parent: Option<&Vertex<T>>) -> Result<VisitorDFSAction, GraphError> {
        self.values[vertex.id] = Some(self.values[parent.id].unwrap() + 1);
        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 && vertex.id != grand_parent.unwrap().id {
            self.cycle = true;
            return Ok(VisitorDFSAction::Break);
        }
        Ok(VisitorDFSAction::Nothing)
    }
}

///
/// Find vertices depths
/// The algorithm finds the depth of each vertex. The graph must be a tree, i.e. a connected acyclic graph.
/// Algorithmic complexity - O(|E|), where |E| is the number of edges in the graph.
///
/// ```
/// use luka::{Graph, algorithms};
///
/// let mut graph = Graph::new(12);
///
/// graph.add_edge(1, 4, 0).unwrap();
/// graph.add_edge(1, 2, 0).unwrap();
/// graph.add_edge(4, 11, 0).unwrap();
/// graph.add_edge(4, 12, 0).unwrap();
/// graph.add_edge(12, 3, 0).unwrap();
/// graph.add_edge(2, 5, 0).unwrap();
/// graph.add_edge(2, 6, 0).unwrap();
/// graph.add_edge(5, 9, 0).unwrap();
/// graph.add_edge(5, 10, 0).unwrap();
/// graph.add_edge(6, 7, 0).unwrap();
/// graph.add_edge(7, 8, 0).unwrap();
///
/// let depths = algorithms::find_vertices_depths(&graph, graph.get_vertex(1).unwrap()).unwrap();
/// assert_eq!(depths.get_vertex_depth(graph.get_vertex(3).unwrap()), Some(3));
/// assert_eq!(depths.get_vertex_depth(graph.get_vertex(8).unwrap()), Some(4));
/// assert_eq!(depths.get_vertex_depth(graph.get_vertex(11).unwrap()), Some(2));
/// ```

pub fn find_vertices_depths<'a, T>(graph: &'a Graph<T>, from: &'a Vertex<T>) -> Result<VerticesDepths<'a, T>, GraphError> where T: Default + Copy {
    let mut visitor = CustomVisitor{
        values: vec![None; graph.size()],
        cycle: false
    };
    visitor.values[from.id] = Some(0);
    dfs_with_visitor(graph, from , &mut visitor)?;
    if visitor.cycle {
        return Err(GraphError::Regular(ErrorKind::TreeContainsCycle));
    }
    Ok(VerticesDepths{ values: visitor.values, phantom: PhantomData })
}

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

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

        graph.add_edge(1, 4, 0).unwrap();
        graph.add_edge(1, 2, 0).unwrap();
        graph.add_edge(4, 11, 0).unwrap();
        graph.add_edge(4, 12, 0).unwrap();
        graph.add_edge(12, 3, 0).unwrap();
        graph.add_edge(2, 5, 0).unwrap();
        graph.add_edge(2, 6, 0).unwrap();
        graph.add_edge(5, 9, 0).unwrap();
        graph.add_edge(5, 10, 0).unwrap();
        graph.add_edge(6, 7, 0).unwrap();
        graph.add_edge(7, 8, 0).unwrap();

        let depths = find_vertices_depths(&graph, graph.get_vertex(1).unwrap()).unwrap();
        assert_eq!(depths.get_vertex_depth(graph.get_vertex(3).unwrap()), Some(3));
        assert_eq!(depths.get_vertex_depth(graph.get_vertex(8).unwrap()), Some(4));
        assert_eq!(depths.get_vertex_depth(graph.get_vertex(11).unwrap()), Some(2));
    }
}