sim_lib_discrete_graph/
bridge.rs

1//! Graph <-> matrix conversions: adjacency (boolean, min-plus, sparse),
2//! incidence, and Laplacian, with explicit multiedge policies and a mapping
3//! witness.
4//!
5//! Bridge matrices omit graph self-loops. This keeps adjacency, incidence, and
6//! Laplacian exports aligned with the simple-graph matrix contract while
7//! preserving the original graph value unchanged.
8
9use crate::edge::Directedness;
10use crate::error::GraphError;
11use crate::graph::Graph;
12use crate::intring::IntRing;
13use sim_lib_discrete_algebra::{
14    AlgebraLimits, BoolRing, Matrix, MinPlus, SparseEntry, SparseMatrix,
15};
16use std::collections::HashMap;
17
18/// Resolved canonical-pair values plus the per-edge `(row, col)` mapping.
19type ResolveResult =
20    Result<(HashMap<(usize, usize), i64>, Vec<Option<(usize, usize)>>), GraphError>;
21
22/// How to collapse parallel edges between the same endpoints into one cell.
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub enum MultiedgePolicy {
25    /// Fail if any pair has more than one edge.
26    ErrorOnMultiedge,
27    /// Keep the first edge (by edge id) for each pair.
28    KeepFirst,
29    /// Keep the last edge (by edge id) for each pair.
30    KeepLast,
31    /// Keep the minimum weight for each pair.
32    MinWeight,
33    /// Sum the weights for each pair.
34    SumWeight,
35    /// Use the number of parallel edges as the cell value.
36    CountEdges,
37}
38
39impl MultiedgePolicy {
40    fn label(self) -> &'static str {
41        match self {
42            MultiedgePolicy::ErrorOnMultiedge => "error-on-multiedge",
43            MultiedgePolicy::KeepFirst => "keep-first",
44            MultiedgePolicy::KeepLast => "keep-last",
45            MultiedgePolicy::MinWeight => "min-weight",
46            MultiedgePolicy::SumWeight => "sum-weight",
47            MultiedgePolicy::CountEdges => "count-edges",
48        }
49    }
50}
51
52/// Mapping metadata recording how graph elements landed in the matrix.
53#[derive(Debug, Clone, PartialEq, Eq)]
54pub struct GraphMatrixMap {
55    /// `node_to_row[node]` is the matrix row for `node` (identity here).
56    pub node_to_row: Vec<usize>,
57    /// `row_to_node[row]` is the node for a matrix row (identity here).
58    pub row_to_node: Vec<usize>,
59    /// `edge_to_entry[edge_id]` is the `(row, col)` the edge contributed to.
60    pub edge_to_entry: Vec<Option<(usize, usize)>>,
61    /// The multiedge policy applied, as a label.
62    pub policy: String,
63}
64
65fn identity_map(n: usize, edge_count: usize, policy: &str) -> GraphMatrixMap {
66    GraphMatrixMap {
67        node_to_row: (0..n).collect(),
68        row_to_node: (0..n).collect(),
69        edge_to_entry: vec![None; edge_count],
70        policy: policy.to_string(),
71    }
72}
73
74fn canonical<N, W>(graph: &Graph<N, W>, s: usize, t: usize) -> (usize, usize) {
75    if graph.is_directed() {
76        (s, t)
77    } else {
78        (s.min(t), s.max(t))
79    }
80}
81
82fn checked_sum_weights(group: &[(usize, i64)]) -> Result<i64, GraphError> {
83    let mut total = 0_i64;
84    for (_, weight) in group {
85        total = total
86            .checked_add(*weight)
87            .ok_or_else(|| GraphError::WeightOverflow("parallel edge sum".to_string()))?;
88    }
89    Ok(total)
90}
91
92/// Resolve parallel edges per the policy. Returns the resolved value per
93/// canonical pair and the per-edge entry mapping.
94fn resolve<N>(graph: &Graph<N, i64>, policy: MultiedgePolicy) -> ResolveResult {
95    let mut groups: HashMap<(usize, usize), Vec<(usize, i64)>> = HashMap::new();
96    let mut edge_to_entry = vec![None; graph.edge_count()];
97    for e in &graph.edges {
98        if e.is_self_loop() {
99            continue;
100        }
101        let key = canonical(graph, e.source, e.target);
102        groups.entry(key).or_default().push((e.id, e.weight));
103        edge_to_entry[e.id] = Some((e.source, e.target));
104    }
105    let mut resolved = HashMap::new();
106    for (key, mut group) in groups {
107        group.sort_by_key(|(id, _)| *id);
108        if matches!(policy, MultiedgePolicy::ErrorOnMultiedge) && group.len() > 1 {
109            return Err(GraphError::Unsupported(
110                "multiple edges between a pair under ErrorOnMultiedge".to_string(),
111            ));
112        }
113        let value = match policy {
114            MultiedgePolicy::ErrorOnMultiedge | MultiedgePolicy::KeepFirst => group[0].1,
115            MultiedgePolicy::KeepLast => group[group.len() - 1].1,
116            MultiedgePolicy::MinWeight => group.iter().map(|(_, w)| *w).min().unwrap(),
117            MultiedgePolicy::SumWeight => checked_sum_weights(&group)?,
118            MultiedgePolicy::CountEdges => i64::try_from(group.len())
119                .map_err(|_| GraphError::WeightOverflow("parallel edge count".to_string()))?,
120        };
121        resolved.insert(key, value);
122    }
123    Ok((resolved, edge_to_entry))
124}
125
126/// Expand a canonical resolved map into directed `(row, col)` cells.
127fn directed_cells<N>(
128    graph: &Graph<N, i64>,
129    resolved: &HashMap<(usize, usize), i64>,
130) -> Vec<((usize, usize), i64)> {
131    let mut cells = Vec::new();
132    for (&(a, b), &v) in resolved {
133        cells.push(((a, b), v));
134        if !graph.is_directed() {
135            cells.push(((b, a), v));
136        }
137    }
138    cells
139}
140
141/// Boolean adjacency: `true` where at least one non-self-loop edge connects the
142/// pair.
143pub fn graph_to_bool_adjacency<N, W>(
144    graph: &Graph<N, W>,
145) -> Result<(Matrix<BoolRing>, GraphMatrixMap), GraphError> {
146    graph.validate()?;
147    let n = graph.node_count();
148    let mut m = Matrix::try_filled_with_limits(n, n, BoolRing(false), AlgebraLimits::default())?;
149    let undirected = !graph.is_directed();
150    let mut map = identity_map(n, graph.edge_count(), "boolean");
151    for e in &graph.edges {
152        if e.is_self_loop() {
153            continue;
154        }
155        m.data[e.source * n + e.target] = BoolRing(true);
156        map.edge_to_entry[e.id] = Some((e.source, e.target));
157        if undirected {
158            m.data[e.target * n + e.source] = BoolRing(true);
159        }
160    }
161    Ok((m, map))
162}
163
164/// Min-plus weighted adjacency (`Inf` = no non-self-loop edge), applying a
165/// multiedge policy.
166pub fn graph_to_minplus_adjacency<N>(
167    graph: &Graph<N, i64>,
168    policy: MultiedgePolicy,
169) -> Result<(Matrix<MinPlus>, GraphMatrixMap), GraphError> {
170    graph.validate()?;
171    let n = graph.node_count();
172    let (resolved, edge_to_entry) = resolve(graph, policy)?;
173    let mut m = Matrix::try_filled_with_limits(n, n, MinPlus::Inf, AlgebraLimits::default())?;
174    for ((r, c), v) in directed_cells(graph, &resolved) {
175        m.data[r * n + c] = MinPlus::Fin(v);
176    }
177    let mut map = identity_map(n, graph.edge_count(), policy.label());
178    map.edge_to_entry = edge_to_entry;
179    Ok((m, map))
180}
181
182/// Sparse min-plus weighted adjacency, applying a multiedge policy and omitting
183/// self-loops.
184pub fn graph_to_sparse_adjacency<N>(
185    graph: &Graph<N, i64>,
186    policy: MultiedgePolicy,
187) -> Result<(SparseMatrix<MinPlus>, GraphMatrixMap), GraphError> {
188    graph.validate()?;
189    let n = graph.node_count();
190    let (resolved, edge_to_entry) = resolve(graph, policy)?;
191    let mut entries = Vec::new();
192    for ((r, c), v) in directed_cells(graph, &resolved) {
193        entries.push(SparseEntry {
194            row: r,
195            col: c,
196            value: MinPlus::Fin(v),
197        });
198    }
199    let sparse = SparseMatrix::from_entries(n, n, entries)
200        .map_err(|e| GraphError::Unsupported(e.to_string()))?;
201    let mut map = identity_map(n, graph.edge_count(), policy.label());
202    map.edge_to_entry = edge_to_entry;
203    Ok((sparse, map))
204}
205
206/// Incidence matrix as a sparse `IntRing` matrix. Directed: `-1` at the source,
207/// `+1` at the target. Undirected: `+1` at both endpoints. One column per
208/// non-self-loop edge.
209pub fn graph_to_incidence<N, W>(graph: &Graph<N, W>) -> Result<SparseMatrix<IntRing>, GraphError> {
210    graph.validate()?;
211    let n = graph.node_count();
212    let directed = graph.is_directed();
213    let mut entries = Vec::new();
214    let mut col = 0;
215    for e in &graph.edges {
216        if e.is_self_loop() {
217            continue;
218        }
219        if directed {
220            entries.push(SparseEntry {
221                row: e.source,
222                col,
223                value: IntRing(-1),
224            });
225            entries.push(SparseEntry {
226                row: e.target,
227                col,
228                value: IntRing(1),
229            });
230        } else {
231            entries.push(SparseEntry {
232                row: e.source,
233                col,
234                value: IntRing(1),
235            });
236            entries.push(SparseEntry {
237                row: e.target,
238                col,
239                value: IntRing(1),
240            });
241        }
242        col += 1;
243    }
244    SparseMatrix::from_entries(n, col, entries).map_err(|e| GraphError::Unsupported(e.to_string()))
245}
246
247/// Unweighted graph Laplacian `L = D - A` over `IntRing`, ignoring self-loops.
248/// For an undirected graph each row sums to zero.
249pub fn graph_to_laplacian<N, W>(graph: &Graph<N, W>) -> Result<Matrix<IntRing>, GraphError> {
250    graph.validate()?;
251    let n = graph.node_count();
252    let mut m = Matrix::try_filled_with_limits(n, n, IntRing(0), AlgebraLimits::default())?;
253    let undirected = !graph.is_directed();
254    for e in &graph.edges {
255        if e.is_self_loop() {
256            continue;
257        }
258        m.data[e.source * n + e.target].0 -= 1;
259        m.data[e.source * n + e.source].0 += 1;
260        if undirected {
261            m.data[e.target * n + e.source].0 -= 1;
262            m.data[e.target * n + e.target].0 += 1;
263        }
264    }
265    Ok(m)
266}
267
268/// Reconstruct a graph from a min-plus adjacency matrix (`Inf` = no edge). Node
269/// labels are their indices. Directedness is supplied by the caller.
270pub fn minplus_adjacency_to_graph(
271    matrix: &Matrix<MinPlus>,
272    directedness: Directedness,
273) -> Result<Graph<usize, i64>, GraphError> {
274    matrix.validate()?;
275    if !matrix.is_square() {
276        return Err(GraphError::Unsupported(
277            "adjacency must be square".to_string(),
278        ));
279    }
280    let n = matrix.rows;
281    let mut g = Graph::with_nodes((0..n).collect(), directedness);
282    let undirected = matches!(directedness, Directedness::Undirected);
283    for i in 0..n {
284        for j in 0..n {
285            if i == j {
286                continue;
287            }
288            if undirected && j < i {
289                continue;
290            }
291            if let MinPlus::Fin(w) = matrix.data[i * n + j] {
292                g.add_edge(i, j, w)?;
293            }
294        }
295    }
296    Ok(g)
297}
298
299#[cfg(test)]
300mod tests {
301    use super::*;
302
303    fn weighted_directed() -> Graph<usize, i64> {
304        let mut g = Graph::with_nodes(vec![0, 1, 2], Directedness::Directed);
305        g.add_edge(0, 1, 4).unwrap();
306        g.add_edge(1, 2, 7).unwrap();
307        g
308    }
309
310    #[test]
311    fn adjacency_round_trip_preserves_simple_graph() {
312        let g = weighted_directed();
313        let (m, _map) = graph_to_minplus_adjacency(&g, MultiedgePolicy::ErrorOnMultiedge).unwrap();
314        let back = minplus_adjacency_to_graph(&m, Directedness::Directed).unwrap();
315        let mut got: Vec<_> = back
316            .edges
317            .iter()
318            .map(|e| (e.source, e.target, e.weight))
319            .collect();
320        got.sort_unstable();
321        assert_eq!(got, vec![(0, 1, 4), (1, 2, 7)]);
322        assert!(back.is_directed());
323    }
324
325    #[test]
326    fn directedness_is_preserved() {
327        let mut g: Graph<usize, i64> = Graph::with_nodes(vec![0, 1], Directedness::Undirected);
328        g.add_edge(0, 1, 5).unwrap();
329        let (m, _) = graph_to_minplus_adjacency(&g, MultiedgePolicy::MinWeight).unwrap();
330        // Symmetric for undirected: cells (0,1) and (1,0) in a 2x2 matrix.
331        assert_eq!(m.data[1], MinPlus::Fin(5));
332        assert_eq!(m.data[2], MinPlus::Fin(5));
333    }
334
335    #[test]
336    fn multiedge_policies_differ() {
337        let mut g: Graph<usize, i64> = Graph::with_nodes(vec![0, 1], Directedness::Directed);
338        g.add_edge(0, 1, 3).unwrap();
339        g.add_edge(0, 1, 10).unwrap();
340        let cell = |p| graph_to_minplus_adjacency(&g, p).unwrap().0.data[1];
341        assert_eq!(cell(MultiedgePolicy::MinWeight), MinPlus::Fin(3));
342        assert_eq!(cell(MultiedgePolicy::SumWeight), MinPlus::Fin(13));
343        assert_eq!(cell(MultiedgePolicy::KeepLast), MinPlus::Fin(10));
344        assert_eq!(cell(MultiedgePolicy::CountEdges), MinPlus::Fin(2));
345        assert!(graph_to_minplus_adjacency(&g, MultiedgePolicy::ErrorOnMultiedge).is_err());
346    }
347
348    #[test]
349    fn malformed_edge_ids_fail_before_matrix_indexing() {
350        let g = Graph {
351            nodes: vec![0, 1],
352            edges: vec![crate::edge::Edge {
353                id: 3,
354                source: 0,
355                target: 1,
356                weight: 7,
357            }],
358            directedness: Directedness::Directed,
359        };
360
361        assert!(matches!(
362            graph_to_bool_adjacency(&g),
363            Err(GraphError::InvalidEdgeId {
364                index: 0,
365                id: 3,
366                len: 1,
367            })
368        ));
369    }
370
371    #[test]
372    fn sum_weight_policy_rejects_overflow() {
373        let mut g: Graph<usize, i64> = Graph::with_nodes(vec![0, 1], Directedness::Directed);
374        g.add_edge(0, 1, i64::MAX).unwrap();
375        g.add_edge(0, 1, 1).unwrap();
376
377        assert!(matches!(
378            graph_to_minplus_adjacency(&g, MultiedgePolicy::SumWeight),
379            Err(GraphError::WeightOverflow(_))
380        ));
381    }
382
383    #[test]
384    fn self_loops_are_omitted_from_bridge_matrices() {
385        let mut g: Graph<usize, i64> = Graph::with_nodes(vec![0, 1], Directedness::Undirected);
386        g.add_edge(0, 0, 9).unwrap();
387        g.add_edge(0, 1, 5).unwrap();
388
389        let (bool_adj, bool_map) = graph_to_bool_adjacency(&g).unwrap();
390        assert_eq!(bool_adj.data[0], BoolRing(false));
391        assert_eq!(bool_adj.data[1], BoolRing(true));
392        assert_eq!(bool_adj.data[2], BoolRing(true));
393        assert_eq!(bool_map.edge_to_entry[0], None);
394        assert_eq!(bool_map.edge_to_entry[1], Some((0, 1)));
395
396        let (min_adj, min_map) =
397            graph_to_minplus_adjacency(&g, MultiedgePolicy::MinWeight).unwrap();
398        assert_eq!(min_adj.data[0], MinPlus::Inf);
399        assert_eq!(min_adj.data[1], MinPlus::Fin(5));
400        assert_eq!(min_adj.data[2], MinPlus::Fin(5));
401        assert_eq!(min_map.edge_to_entry[0], None);
402
403        let lap = graph_to_laplacian(&g).unwrap();
404        assert_eq!(lap.data[0].0, 1);
405        assert_eq!(lap.data[1].0, -1);
406        assert_eq!(lap.data[2].0, -1);
407        assert_eq!(lap.data[3].0, 1);
408    }
409
410    #[test]
411    fn laplacian_rows_sum_to_zero() {
412        // Triangle: each row of L sums to zero for a connected undirected graph.
413        let mut g: Graph<usize, i64> = Graph::with_nodes(vec![0, 1, 2], Directedness::Undirected);
414        g.add_edge(0, 1, 1).unwrap();
415        g.add_edge(1, 2, 1).unwrap();
416        g.add_edge(0, 2, 1).unwrap();
417        let l = graph_to_laplacian(&g).unwrap();
418        for r in 0..3 {
419            let sum: i64 = (0..3).map(|c| l.data[r * 3 + c].0).sum();
420            assert_eq!(sum, 0, "row {r}");
421        }
422        // Diagonal is the degree (2 for the triangle).
423        assert_eq!(l.data[0].0, 2);
424    }
425
426    #[test]
427    fn incidence_columns_have_expected_signs() {
428        let g = weighted_directed();
429        let inc = graph_to_incidence(&g).unwrap();
430        // Column 0 is edge 0->1: -1 at row 0, +1 at row 1.
431        let col0: Vec<_> = inc.entries.iter().filter(|e| e.col == 0).collect();
432        assert!(col0.iter().any(|e| e.row == 0 && e.value == IntRing(-1)));
433        assert!(col0.iter().any(|e| e.row == 1 && e.value == IntRing(1)));
434    }
435}
sim_lib_discrete_graph/bridge.rs

sim_lib_discrete_graph/
bridge.rs
