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

use crate::IndexGraphView;
use crate::Vec;
use alloc::collections::VecDeque;

pub(super) fn indexed_nodes<G: IndexGraphView>(graph: &G) -> Vec<Option<G::Node>> {
    let mut nodes = vec![None; graph.node_bound()];
    for node in graph.node_indices() {
        nodes[G::node_slot(node)] = Some(node);
    }
    nodes
}

pub(super) fn residual_reachable<G>(
    graph: &G,
    source: G::Node,
    capacities: &[u64],
    flows: &[u64],
) -> Vec<bool>
where
    G: IndexGraphView,
{
    let nodes = indexed_nodes(graph);
    let mut seen = vec![false; graph.node_bound()];
    let source = G::node_slot(source);
    seen[source] = true;
    let mut queue = VecDeque::from([source]);
    while let Some(node) = queue.pop_front() {
        let Some(node_key) = nodes[node] else {
            continue;
        };
        for edge in graph.outgoing_edges(node_key) {
            let slot = G::edge_slot(edge);
            if capacities[slot] > flows[slot]
                && let Some(target) = graph.edge_endpoints(edge).map(|e| G::node_slot(e.target()))
            {
                push_unseen(target, &mut seen, &mut queue);
            }
        }
        for edge in graph.incoming_edges(node_key) {
            if flows[G::edge_slot(edge)] > 0
                && let Some(target) = graph.edge_endpoints(edge).map(|e| G::node_slot(e.source()))
            {
                push_unseen(target, &mut seen, &mut queue);
            }
        }
    }
    seen
}

fn push_unseen(node: usize, seen: &mut [bool], queue: &mut VecDeque<usize>) {
    if !seen[node] {
        seen[node] = true;
        queue.push_back(node);
    }
}