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

mod common;
use common::*;

use wolf_graph::prelude::*;

#[test]
fn test_path_exists() {
    let tests = vec![
        ("B", "K", true),
        ("B", "A", true),
        ("H", "A", true),
        ("A", "A", true),
        ("I", "B", true),
        ("G", "B", true),
        ("H", "D", true),
        ("D", "H", false),
        ("A", "B", false),
        ("F", "C", false),
        ("J", "I", false),
        ("I", "J", false),
    ];
    let g = make_graph();
    for (from, to, expected) in tests {
        assert_eq!(g.path_exists(nid!(from), nid!(to)).unwrap(), expected);
    }
}

#[test]
fn test_can_add_dag_edge() {
    let tests = vec![
        ("H", "I", true),
        ("K", "J", true),
        ("C", "H", false),
        ("E", "B", false),
        ("A", "B", false),
        ("B", "B", false), // Does not allow loops
        ("B", "A", true),  // Does allow multi-edges
    ];
    let g = make_dag();
    for (from, to, expected) in tests {
        assert_eq!(g.can_add_dag_edge(nid!(from), nid!(to), None::<EdgeID>).unwrap(), expected);
    }
}

#[test]
fn test_can_move_dag_edge() {
    let tests = vec![
        // Identity
        ("BA", "B", "A", true),

        // Move the head of an edge
        ("JA", "J", "B", true),

        // Move the tail of an edge
        ("JA", "H", "A", true),

        // Disallow making a cycle
        ("BC", "C", "J", false),

        // Allow moving an edge that would have been in a cycle if not moved
        ("JA", "C", "J", true),

        // Disallow reversing an edge that makes a cycle
        ("BG", "G", "B", false),

        // Reverse an edge without making a cycle
        ("IK", "K", "I", true),

        // Does not allow loops
        ("CD", "C", "C", false),

        // Does allow multi-edges
        ("AC", "C", "D", true),
    ];
    let g = make_dag();
    for (edge, new_source, new_target, expected) in tests {
        assert_eq!(g.can_move_dag_edge(eid!(edge), nid!(new_source), nid!(new_target)).unwrap(), expected);
    }
}