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

sim_lib_discrete_graph/
bridge.rs
