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

mod common;
use common::*;

use wolf_graph::prelude::*;

pub fn make_forest() -> BlankForest {
    let tree = BlankTree::new_with_root_and_graph(nid!("A"), make_tree()).unwrap();
    BlankForest::new_with_tree(tree)
}

#[test]
fn test_forest_encoding() {
    let f = make_forest();
    recode(&f, r#"["A",[["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O"],[["AB","A","B"],["AC","A","C"],["AD","A","D"],["BI","B","I"],["CH","C","H"],["DE","D","E"],["DF","D","F"],["DG","D","G"],["EM","E","M"],["EN","E","N"],["EO","E","O"],["FL","F","L"],["HJ","H","J"],["HK","H","K"]]]]"#).unwrap();
}

#[test]
fn test_forest_queries() {
    let f = make_forest().adding_node(nid!("Z"), None::<NodeID>, eid!("AZ")).unwrap();
    assert!(!f.has_predecessors(nid!("Z")).unwrap());
    assert_eq!(f.node_count(), 15);
    assert_eq!(f.edge_count(), 11);
    assert_eq!(format_ids(f.all_nodes()), "[B, C, D, E, F, G, H, I, J, K, L, M, N, O, Z]");
    assert_eq!(format_ids(f.all_edges()), "[BI, CH, DE, DF, DG, EM, EN, EO, FL, HJ, HK]");
    assert!(!f.has_node(nid!("A")));
    assert!(f.has_node(nid!("B")));
    assert!(!f.has_edge(eid!("AB")));
    assert!(f.has_edge(eid!("BI")));
    assert!(!f.has_edge_between(nid!("A"), nid!("C")));
    assert!(f.has_edge_between(nid!("C"), nid!("H")));
    assert!(f.source(eid!("AC")).is_err());
    assert_eq!(f.source(eid!("CH")).unwrap(), nid!("C"));
    assert!(f.target(eid!("AC")).is_err());
    assert_eq!(f.target(eid!("DE")).unwrap(), nid!("E"));
    assert!(f.endpoints(eid!("AC")).is_err());
    assert_eq!(format!("({}, {})", f.endpoints(eid!("DF")).unwrap().0, f.endpoints(eid!("DF")).unwrap().1), "(D, F)");
    assert!(f.out_degree(nid!("A")).is_err());
    assert_eq!(f.out_degree(nid!("D")).unwrap(), 3);
    assert!(f.in_degree(nid!("A")).is_err());
    assert_eq!(f.in_degree(nid!("D")).unwrap(), 0);
    assert!(f.degree(nid!("A")).is_err());
    assert_eq!(f.degree(nid!("C")).unwrap(), 1);
    assert!(f.out_edges(nid!("A")).is_err());
    assert_eq!(format_ids(f.out_edges(nid!("D")).unwrap()), "[DE, DF, DG]");
    assert!(f.in_edges(nid!("A")).is_err());
    assert_eq!(format_ids(f.in_edges(nid!("D")).unwrap()), "[]");
    assert!(f.incident_edges(nid!("A")).is_err());
    assert_eq!(format_ids(f.incident_edges(nid!("C")).unwrap()), "[CH]");
    assert!(f.has_successors(nid!("A")).is_err());
    assert!(f.has_successors(nid!("D")).unwrap());
    assert!(!f.has_successors(nid!("I")).unwrap());
    assert!(f.has_predecessors(nid!("A")).is_err());
    assert!(!f.has_predecessors(nid!("D")).unwrap());
    assert!(f.has_predecessors(nid!("I")).unwrap());
    assert!(f.has_neighbors(nid!("A")).is_err());
    assert!(f.has_neighbors(nid!("B")).unwrap());
    assert!(!f.has_neighbors(nid!("Z")).unwrap());
    assert!(f.successors(nid!("A")).is_err());
    assert_eq!(format_ids(f.successors(nid!("D")).unwrap()), "[E, F, G]");
    assert!(f.predecessors(nid!("A")).is_err());
    assert_eq!(format_ids(f.predecessors(nid!("D")).unwrap()), "[]");
    assert_eq!(format_ids(f.predecessors(nid!("E")).unwrap()), "[D]");
    assert!(f.neighbors(nid!("A")).is_err());
    assert_eq!(format_ids(f.neighbors(nid!("D")).unwrap()), "[E, F, G]");
    assert_eq!(format_ids(f.neighbors(nid!("E")).unwrap()), "[D, M, N, O]");
    assert_eq!(format_ids(f.all_roots()), "[B, C, D, Z]");
    assert_eq!(format_ids(f.non_roots()), "[E, F, G, H, I, J, K, L, M, N, O]");
    assert_eq!(format_ids(f.all_leaves()), "[G, I, J, K, L, M, N, O, Z]");
    assert_eq!(format_ids(f.all_internals()), "[B, C, D, E, F, H]");

    assert!(f.is_leaf(nid!("A")).is_err());
    assert!(f.is_leaf(nid!("K")).unwrap());
    assert!(!f.is_leaf(nid!("H")).unwrap());

    assert!(f.is_root(nid!("A")).is_err());
    assert!(f.is_root(nid!("B")).unwrap());
    assert!(!f.is_root(nid!("H")).unwrap());

    assert!(f.is_internal(nid!("A")).is_err());
    assert!(f.is_internal(nid!("H")).unwrap());
    assert!(!f.is_internal(nid!("D")).unwrap());
}