three_edge_connected/
algorithm.rs

1use std::collections::VecDeque;
2
3use crate::{graph::FxMapGraph, state::State};
4
5#[derive(Debug)]
6enum Inst {
7    Recur(usize, usize),
8    Loop(usize, usize, usize),
9    Return(usize, usize),
10}
11
12macro_rules! assert_state_len {
13    ($state:ident, $var:ident) => {
14        assert!(
15            $var < $state.visited.len()
16                && $var < $state.next_sigma.len()
17                && $var < $state.next_on_path.len()
18                && $var < $state.degrees.len()
19                && $var < $state.pre.len()
20                && $var < $state.lowpt.len()
21                && $var < $state.num_descendants.len()
22        );
23    };
24}
25
26type InstStack = VecDeque<Inst>;
27
28fn run_inst(
29    inst: Inst,
30    stack: &mut InstStack,
31    state: &mut State,
32    graph: &FxMapGraph,
33) {
34    match inst {
35        Inst::Recur(w, v) => {
36            state.mut_recur(w);
37
38            graph[&w]
39                .iter()
40                .rev()
41                .for_each(|edge| stack.push_front(Inst::Loop(w, v, *edge)));
42        }
43        Inst::Loop(w, v, u) => {
44            assert_state_len!(state, w);
45            assert_state_len!(state, v);
46            assert_state_len!(state, u);
47            state.degrees[w] += 1;
48
49            if !state.visited[u] {
50                stack.push_front(Inst::Return(w, u));
51                stack.push_front(Inst::Recur(u, w));
52            } else {
53                // (w, u) outgoing back-edge of w, i.e. dfs(w) > dfs(u)
54                if u != v && state.is_back_edge(w, u) {
55                    if state.pre[u] < state.lowpt[w] {
56                        state.absorb_path(w, state.next_on_path[w], None);
57                        state.next_on_path[w] = w; // P_w in paper
58                        state.lowpt[w] = state.pre[u];
59                    }
60                // (w, u) incoming back-edge of w, i.e. dfs(u) > dfs(w)
61                } else if u != v {
62                    state.degrees[w] -= 2;
63
64                    if !state.is_null_path(w) {
65                        let mut parent = w;
66                        let mut child = state.next_on_path[w];
67
68                        while !state.is_null_path(parent)
69                            && state.pre[child] <= state.pre[u]
70                        // child must have been visited before u
71                            && state.pre[u] < state.pre[child] + state.num_descendants[child]
72                        // child is still an ancestor of u
73                        {
74                            parent = child;
75                            child = state.next_on_path[child];
76                        }
77
78                        // P_w[w..u] in paper
79                        state.absorb_path(
80                            w,
81                            state.next_on_path[w],
82                            Some(parent),
83                        );
84
85                        state.next_on_path[w] = if state.is_null_path(parent) {
86                            w
87                        } else {
88                            state.next_on_path[parent]
89                        }
90                    }
91                }
92            }
93        }
94        Inst::Return(w, u) => {
95            assert_state_len!(state, w);
96            assert_state_len!(state, u);
97            state.num_descendants[w] += state.num_descendants[u];
98
99            if state.degrees[u] <= 2 {
100                state.degrees[w] += state.degrees[u] - 2;
101                state.add_component(u);
102
103                state.path_u = if state.is_null_path(u) {
104                    w // P_u = w + P_u
105                } else {
106                    state.next_on_path[u] // P_u
107                };
108            } else {
109                // since degree[u] != 2, u can be absorbed
110                state.path_u = u;
111            }
112
113            if state.lowpt[w] <= state.lowpt[u] {
114                // w + P_u in paper
115                state.absorb_path(w, state.path_u, None);
116            } else {
117                state.lowpt[w] = state.lowpt[u];
118                // P_w in paper
119                state.absorb_path(w, state.next_on_path[w], None);
120                state.next_on_path[w] = state.path_u;
121            }
122        }
123    }
124}
125
126fn three_edge_connect(graph: &FxMapGraph, state: &mut State) {
127    let mut stack: InstStack = VecDeque::new();
128
129    for &n in graph.keys() {
130        if !state.visited[n] {
131            stack.push_front(Inst::Recur(n, 0));
132            while let Some(inst) = stack.pop_front() {
133                run_inst(inst, &mut stack, state, graph);
134            }
135            state.add_component(n);
136        }
137    }
138}
139
140pub fn find_components(graph: &FxMapGraph) -> Vec<Vec<usize>> {
141    let mut state = State::initialize(graph);
142    three_edge_connect(graph, &mut state);
143    state.sigma
144}
three_edge_connected/algorithm.rs

three_edge_connected/
algorithm.rs
