retworkx_core/connectivity/
chain.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13use std::cmp::Eq;
14use std::hash::Hash;
15
16use hashbrown::HashMap;
17
18use petgraph::visit::{
19    GraphProp, IntoEdges, IntoNodeIdentifiers, NodeCount, NodeIndexable,
20    VisitMap, Visitable,
21};
22use petgraph::Undirected;
23
24use crate::traversal::{depth_first_search, DfsEvent};
25
26fn _build_chain<G, VM: VisitMap<G::NodeId>>(
27    graph: G,
28    parent: &[usize],
29    mut u_id: G::NodeId,
30    mut v_id: G::NodeId,
31    visited: &mut VM,
32) -> Vec<(G::NodeId, G::NodeId)>
33where
34    G: Visitable + NodeIndexable,
35{
36    let mut chain = Vec::new();
37    while visited.visit(v_id) {
38        chain.push((u_id, v_id));
39        u_id = v_id;
40        let u = graph.to_index(u_id);
41        let v = parent[u];
42        v_id = graph.from_index(v);
43    }
44    chain.push((u_id, v_id));
45
46    chain
47}
48
49/// Returns the chain decomposition of a graph.
50///
51/// The *chain decomposition* of a graph with respect to a depth-first
52/// search tree is a set of cycles or paths derived from the set of
53/// fundamental cycles of the tree in the following manner. Consider
54/// each fundamental cycle with respect to the given tree, represented
55/// as a list of edges beginning with the nontree edge oriented away
56/// from the root of the tree. For each fundamental cycle, if it
57/// overlaps with any previous fundamental cycle, just take the initial
58/// non-overlapping segment, which is a path instead of a cycle. Each
59/// cycle or path is called a *chain*. For more information,
60/// see [`Schmidt`](https://doi.org/10.1016/j.ipl.2013.01.016).
61///
62/// The graph should be undirected. If `source` is specified only the chain
63/// decomposition for the connected component containing this node will be returned.
64/// This node indicates the root of the depth-first search tree. If it's not
65/// specified, a source will be chosen arbitrarly and repeated until all components
66/// of the graph are searched.
67///
68/// Returns a list of list of edges where each inner list is a chain.
69///
70/// # Note
71/// The function implicitly assumes that there are no parallel edges
72/// or self loops. It may produce incorrect/unexpected results if the
73/// input graph has self loops or parallel edges.
74///
75/// # Example
76/// ```rust
77/// use retworkx_core::connectivity::chain_decomposition;
78/// use retworkx_core::petgraph::graph::{NodeIndex, UnGraph};
79///
80/// let mut graph : UnGraph<(), ()> = UnGraph::new_undirected();
81/// let a = graph.add_node(()); // node with no weight
82/// let b = graph.add_node(());
83/// let c = graph.add_node(());
84/// let d = graph.add_node(());
85/// let e = graph.add_node(());
86/// let f = graph.add_node(());
87/// let g = graph.add_node(());
88/// let h = graph.add_node(());
89///
90/// graph.extend_with_edges(&[
91///     (a, b),
92///     (b, c),
93///     (c, d),
94///     (d, a),
95///     (e, f),
96///     (b, e),
97///     (f, g),
98///     (g, h),
99///     (h, e)
100/// ]);
101/// // a ---- b ---- e ---- f
102/// // |      |      |      |
103/// // d ---- c      h ---- g
104///
105/// let chains = chain_decomposition(&graph, None);
106/// assert_eq!(
107///     chains,
108///     vec![
109///         vec![(a, d), (d, c), (c, b), (b, a)],
110///         vec![(e, h), (h, g), (g, f), (f, e)]
111///     ]
112/// );
113/// ```
114pub fn chain_decomposition<G>(
115    graph: G,
116    source: Option<G::NodeId>,
117) -> Vec<Vec<(G::NodeId, G::NodeId)>>
118where
119    G: IntoNodeIdentifiers
120        + IntoEdges
121        + Visitable
122        + NodeIndexable
123        + NodeCount
124        + GraphProp<EdgeType = Undirected>,
125    G::NodeId: Eq + Hash,
126{
127    let roots = match source {
128        Some(node) => vec![node],
129        None => graph.node_identifiers().collect(),
130    };
131
132    let mut parent = vec![std::usize::MAX; graph.node_bound()];
133    let mut back_edges: HashMap<G::NodeId, Vec<G::NodeId>> = HashMap::new();
134
135    // depth-first-index (DFI) ordered nodes.
136    let mut nodes = Vec::with_capacity(graph.node_count());
137    depth_first_search(graph, roots, |event| match event {
138        DfsEvent::Discover(u, _) => {
139            nodes.push(u);
140        }
141        DfsEvent::TreeEdge(u, v, _) => {
142            let u = graph.to_index(u);
143            let v = graph.to_index(v);
144            parent[v] = u;
145        }
146        DfsEvent::BackEdge(u_id, v_id, _) => {
147            let u = graph.to_index(u_id);
148            let v = graph.to_index(v_id);
149
150            // do *not* consider ``(u, v)`` as a back edge if ``(v, u)`` is a tree edge.
151            if parent[u] != v {
152                back_edges
153                    .entry(v_id)
154                    .and_modify(|v_edges| v_edges.push(u_id))
155                    .or_insert(vec![u_id]);
156            }
157        }
158        _ => {}
159    });
160
161    let visited = &mut graph.visit_map();
162    nodes
163        .into_iter()
164        .filter_map(|u| {
165            visited.visit(u);
166            back_edges.get(&u).map(|vs| {
167                vs.iter()
168                    .map(|v| _build_chain(graph, &parent, u, *v, visited))
169                    .collect::<Vec<Vec<(G::NodeId, G::NodeId)>>>()
170            })
171        })
172        .flatten()
173        .collect()
174}
retworkx_core/connectivity/chain.rs

retworkx_core/connectivity/
chain.rs
