wolf-graph 0.1.0

Data structures and algorithms for working with graphs with reference or value semantics.
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
107
108
109
110
111

mod common;
use common::*;

use anyhow::Result;

use wolf_graph::prelude::*;

#[test]
fn test_depth_first_search() {
    let v: Vec<(EdgeID, NodeID, NodeID)> = vec![
        ("AB", "A", "B"),
        ("AC", "A", "C"),
        ("BD", "B", "D"),
        ("CD", "C", "D"),
        ("DA", "D", "A"),
    ].into_iter().map(|(a, b, c)| (eid!(a), nid!(b), nid!(c))).collect();
    let graph = make_test_graph(&v);
    let mut visitor = DFSTestVisitor::new();
    graph.depth_first_search(&mut visitor).unwrap();

    assert_eq!(format_ids(visitor.init_nodes), "[A, B, C, D]");
    assert_eq!(format_ids(visitor.start_nodes), "[A]");
    assert_eq!(format_ids(visitor.discovered_nodes), "[A, C, D, B]");
    assert_eq!(format_ids(visitor.finished_nodes), "[D, C, B, A]");

    assert_eq!(format_ids(visitor.examined_edges), "[AC, CD, DA, AB, BD]");
    assert_eq!(format_ids(visitor.tree_edges), "[AC, CD, AB]");
    assert_eq!(format_ids(visitor.back_edges), "[DA]");
    assert_eq!(format_ids(visitor.forward_edges), "[BD]");
    assert_eq!(format_ids(visitor.finished_edges), "[DA, CD, AC, BD, AB]");
}

struct DFSTestVisitor {
    init_nodes: Vec<NodeID>,
    start_nodes: Vec<NodeID>,
    discovered_nodes: Vec<NodeID>,
    finished_nodes: Vec<NodeID>,

    examined_edges: Vec<EdgeID>,
    tree_edges: Vec<EdgeID>,
    back_edges: Vec<EdgeID>,
    forward_edges: Vec<EdgeID>,
    finished_edges: Vec<EdgeID>,
}

impl DFSTestVisitor {
    fn new() -> Self {
        Self {
            init_nodes: vec![],
            start_nodes: vec![],
            discovered_nodes: vec![],
            finished_nodes: vec![],

            examined_edges: vec![],
            tree_edges: vec![],
            back_edges: vec![],
            forward_edges: vec![],
            finished_edges: vec![],
        }
    }
}

impl DFSVisitor for DFSTestVisitor {
    type Graph = BlankGraph;
    type Output = ();

    fn init_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<()>> {
        self.init_nodes.push(node.clone());
        Ok(None)
    }

    fn start_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<()>> {
        self.start_nodes.push(node.clone());
        Ok(None)
    }

    fn discover_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<()>> {
        self.discovered_nodes.push(node.clone());
        Ok(None)
    }

    fn finish_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<()>> {
        self.finished_nodes.push(node.clone());
        Ok(None)
    }

    fn examine_edge(&mut self, _graph: &Self::Graph, edge: &EdgeID) -> Result<Option<()>> {
        self.examined_edges.push(edge.clone());
        Ok(None)
    }

    fn tree_edge(&mut self, _graph: &Self::Graph, edge: &EdgeID) -> Result<Option<()>> {
        self.tree_edges.push(edge.clone());
        Ok(None)
    }

    fn back_edge(&mut self, _graph: &Self::Graph, edge: &EdgeID) -> Result<Option<()>> {
        self.back_edges.push(edge.clone());
        Ok(None)
    }

    fn forward_or_cross_edge(&mut self, _graph: &Self::Graph, edge: &EdgeID) -> Result<Option<()>> {
        self.forward_edges.push(edge.clone());
        Ok(None)
    }

    fn finish_edge(&mut self, _graph: &Self::Graph, edge: &EdgeID) -> Result<Option<()>> {
        self.finished_edges.push(edge.clone());
        Ok(None)
    }
}