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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

use super::result::{MinCostFlow, finish};
use super::search::shortest_residual_path;
use super::{Predecessors, Step};
use crate::algo::flow::common::prepare;
use crate::algo::flow::cut::indexed_nodes;
use crate::{GraphError, IndexGraphView, Result};

/// Computes a maximum flow of minimum cost with successive shortest paths.
///
/// # Errors
///
/// Returns an error for arithmetic overflow or a reachable negative residual
/// cycle.
pub fn min_cost_max_flow<G, Capacity, Cost>(
    graph: &G,
    source: G::Node,
    sink: G::Node,
    edge_capacity: Capacity,
    edge_cost: Cost,
) -> Result<Option<MinCostFlow<G::Node, G::Edge>>>
where
    G: IndexGraphView,
    Capacity: FnMut(G::Edge) -> u64,
    Cost: Fn(G::Edge) -> i64,
{
    if !graph.contains_node(source) || !graph.contains_node(sink) {
        return Ok(None);
    }
    let input = prepare(graph, edge_capacity);
    let mut costs = vec![0_i64; graph.edge_bound()];
    for &edge in &input.edges {
        costs[G::edge_slot(edge)] = edge_cost(edge);
    }
    let mut flows = vec![0_u64; graph.edge_bound()];
    if source == sink {
        return Ok(Some(finish(graph, source, input, &flows, 0, 0)));
    }
    let nodes = indexed_nodes(graph);
    let source_slot = G::node_slot(source);
    let sink_slot = G::node_slot(sink);
    let mut value = 0_u64;
    let mut total_cost = 0_i128;
    while let Some(predecessors) = shortest_residual_path(
        graph,
        &nodes,
        source_slot,
        sink_slot,
        &input.capacities,
        &costs,
        &flows,
    )? {
        let amount = bottleneck::<G>(
            source_slot,
            sink_slot,
            &predecessors,
            &input.capacities,
            &flows,
        );
        let path_cost = apply::<G>(
            source_slot,
            sink_slot,
            amount,
            &predecessors,
            &costs,
            &mut flows,
        )?;
        value = value
            .checked_add(amount)
            .ok_or(GraphError::ArithmeticOverflow {
                operation: "minimum-cost maximum flow value",
            })?;
        total_cost = total_cost
            .checked_add(i128::from(amount).checked_mul(path_cost).ok_or(
                GraphError::ArithmeticOverflow {
                    operation: "minimum-cost path multiplication",
                },
            )?)
            .ok_or(GraphError::ArithmeticOverflow {
                operation: "minimum-cost maximum flow cost",
            })?;
    }
    Ok(Some(finish(
        graph, source, input, &flows, value, total_cost,
    )))
}

fn bottleneck<G>(
    source: usize,
    mut cursor: usize,
    predecessors: &Predecessors<G::Edge>,
    capacities: &[u64],
    flows: &[u64],
) -> u64
where
    G: IndexGraphView,
{
    let mut amount = u64::MAX;
    while cursor != source {
        let step = predecessors[cursor].expect("sink has a residual predecessor");
        let slot = G::edge_slot(step.edge);
        amount = amount.min(if step.forward {
            capacities[slot] - flows[slot]
        } else {
            flows[slot]
        });
        cursor = step.previous;
    }
    amount
}

fn apply<G>(
    source: usize,
    mut cursor: usize,
    amount: u64,
    predecessors: &Predecessors<G::Edge>,
    costs: &[i64],
    flows: &mut [u64],
) -> Result<i128>
where
    G: IndexGraphView,
{
    let mut cost = 0_i128;
    while cursor != source {
        let Step {
            previous,
            edge,
            forward,
        } = predecessors[cursor].expect("sink has a residual predecessor");
        let slot = G::edge_slot(edge);
        cost = if forward {
            flows[slot] += amount;
            cost.checked_add(i128::from(costs[slot]))
        } else {
            flows[slot] -= amount;
            cost.checked_sub(i128::from(costs[slot]))
        }
        .ok_or(GraphError::ArithmeticOverflow {
            operation: "minimum-cost path sum",
        })?;
        cursor = previous;
    }
    Ok(cost)
}