weavatrix_graph/algo/cuts/
mod.rs

1mod stoer_wagner;
2
3pub use stoer_wagner::{StoerWagnerCut, stoer_wagner_min_cut, stoer_wagner_min_cut_filtered};
4
5use crate::IndexUndirectedGraphView;
6use crate::Vec;
7
8#[derive(Debug, Clone, PartialEq, Eq)]
9pub struct UndirectedCuts<Node, Edge> {
10    bridges: Vec<Edge>,
11    articulation_points: Vec<Node>,
12}
13
14impl<Node, Edge> UndirectedCuts<Node, Edge> {
15    #[must_use]
16    pub fn bridges(&self) -> &[Edge] {
17        &self.bridges
18    }
19
20    #[must_use]
21    pub fn articulation_points(&self) -> &[Node] {
22        &self.articulation_points
23    }
24}
25
26pub fn bridges_and_articulation_points<G>(graph: &G) -> UndirectedCuts<G::Node, G::Edge>
27where
28    G: IndexUndirectedGraphView,
29{
30    let mut state = CutState::<G>::new(graph);
31    let mut nodes = graph.node_indices().collect::<Vec<_>>();
32    nodes.sort_unstable_by_key(|node| G::node_slot(*node));
33    for node in nodes {
34        if state.discovery[G::node_slot(node)].is_none() {
35            visit(graph, node, None, &mut state);
36        }
37    }
38    state
39        .bridges
40        .sort_unstable_by_key(|edge| G::edge_slot(*edge));
41    let mut articulation_points = graph
42        .node_indices()
43        .filter(|node| state.articulation[G::node_slot(*node)])
44        .collect::<Vec<_>>();
45    articulation_points.sort_unstable_by_key(|node| G::node_slot(*node));
46    UndirectedCuts {
47        bridges: state.bridges,
48        articulation_points,
49    }
50}
51
52struct CutState<G: IndexUndirectedGraphView> {
53    time: usize,
54    discovery: Vec<Option<usize>>,
55    low: Vec<usize>,
56    articulation: Vec<bool>,
57    bridges: Vec<G::Edge>,
58}
59
60impl<G: IndexUndirectedGraphView> CutState<G> {
61    fn new(graph: &G) -> Self {
62        Self {
63            time: 0,
64            discovery: vec![None; graph.node_bound()],
65            low: vec![0; graph.node_bound()],
66            articulation: vec![false; graph.node_bound()],
67            bridges: Vec::new(),
68        }
69    }
70}
71
72fn visit<G>(graph: &G, node: G::Node, parent_edge: Option<G::Edge>, state: &mut CutState<G>)
73where
74    G: IndexUndirectedGraphView,
75{
76    let slot = G::node_slot(node);
77    let node_discovery = state.time;
78    state.discovery[slot] = Some(node_discovery);
79    state.low[slot] = node_discovery;
80    state.time += 1;
81    let mut children = 0;
82    let mut incident = graph.incident_edges(node).collect::<Vec<_>>();
83    incident.sort_unstable_by_key(|edge| G::edge_slot(*edge));
84    for edge in incident {
85        if Some(edge) == parent_edge {
86            continue;
87        }
88        let Some(neighbor) = graph.opposite(edge, node) else {
89            continue;
90        };
91        let neighbor_slot = G::node_slot(neighbor);
92        if let Some(discovery) = state.discovery[neighbor_slot] {
93            state.low[slot] = state.low[slot].min(discovery);
94            continue;
95        }
96        children += 1;
97        visit(graph, neighbor, Some(edge), state);
98        state.low[slot] = state.low[slot].min(state.low[neighbor_slot]);
99        if state.low[neighbor_slot] > node_discovery {
100            state.bridges.push(edge);
101        }
102        if parent_edge.is_some() && state.low[neighbor_slot] >= node_discovery {
103            state.articulation[slot] = true;
104        }
105    }
106    if parent_edge.is_none() && children > 1 {
107        state.articulation[slot] = true;
108    }
109}
weavatrix_graph/algo/cuts/mod.rs

weavatrix_graph/algo/cuts/
mod.rs
