weavatrix-graph 0.6.1

Deterministic, evidence-carrying graph primitives for repository intelligence
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

use weavatrix_graph::{
    Direction, EdgeEndpoints, GraphError, NodeIndex, Topology, astar, astar_filtered, bellman_ford,
    bellman_ford_filtered,
};

fn topology(node_count: usize, edges: &[(u32, u32)]) -> Topology {
    Topology::try_from_edges(
        node_count,
        edges.iter().map(|&(source, target)| {
            EdgeEndpoints::new(NodeIndex::new(source), NodeIndex::new(target))
        }),
    )
    .unwrap()
}

#[test]
fn astar_finds_the_weighted_path_and_honors_direction_and_filtering() {
    let graph = topology(5, &[(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]);
    let weights = [2_u64, 2, 2, 7, 1];
    let heuristic = [5_u64, 3, 7, 1, 0];
    let path = astar(
        &graph,
        NodeIndex::new(0),
        NodeIndex::new(4),
        |edge| weights[edge.index()],
        |node| heuristic[node.index()],
    )
    .unwrap();
    assert_eq!(path.nodes(), [0, 1, 3, 4].map(NodeIndex::new));
    assert_eq!(path.total_cost(), 5);

    let reverse = astar_filtered(
        &graph,
        NodeIndex::new(4),
        NodeIndex::new(0),
        Direction::Incoming,
        |edge| (edge.index() != 2).then_some(weights[edge.index()]),
        |_| 0,
    )
    .unwrap();
    assert_eq!(reverse.nodes(), [4, 3, 2, 0].map(NodeIndex::new));
    assert_eq!(reverse.total_cost(), 10);
    assert!(astar(&graph, NodeIndex::new(0), NodeIndex::new(9), |_| 1, |_| 0).is_none());
}

#[test]
fn bellman_ford_handles_negative_edges_and_reconstructs_paths() {
    let graph = topology(5, &[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]);
    let weights = [4_i64, 5, -2, 6, 3];
    let result = bellman_ford(&graph, NodeIndex::new(0), |edge| weights[edge.index()])
        .unwrap()
        .unwrap();

    assert_eq!(result.source(), NodeIndex::new(0));
    assert_eq!(result.distance_to(NodeIndex::new(3)), Some(5));
    assert_eq!(
        result.path_to(NodeIndex::new(3)).unwrap().nodes(),
        [0, 1, 2, 3].map(NodeIndex::new)
    );
    assert_eq!(result.path_to(NodeIndex::new(3)).unwrap().total_cost(), 5);
    assert!(result.distance_to(NodeIndex::new(4)).is_none());
    assert!(
        bellman_ford(&graph, NodeIndex::new(9), |_| 1)
            .unwrap()
            .is_none()
    );
}

#[test]
fn bellman_ford_rejects_only_reachable_negative_cycles_and_overflow() {
    let graph = topology(5, &[(0, 1), (1, 2), (2, 1), (3, 4), (4, 3)]);
    let error = bellman_ford(&graph, NodeIndex::new(0), |edge| {
        [1_i64, -3, 1, -5, 1][edge.index()]
    })
    .unwrap_err();
    assert!(matches!(error, GraphError::NegativeCycle { .. }));

    let filtered = bellman_ford_filtered(&graph, NodeIndex::new(0), |edge| {
        (edge.index() != 1).then_some(1)
    })
    .unwrap()
    .unwrap();
    assert_eq!(filtered.distance_to(NodeIndex::new(2)), None);

    let overflow = topology(3, &[(0, 1), (1, 2)]);
    let error = bellman_ford(&overflow, NodeIndex::new(0), |edge| {
        [i64::MAX, 1][edge.index()]
    })
    .unwrap_err();
    assert!(matches!(error, GraphError::ArithmeticOverflow { .. }));
}