rustworkx_core/connectivity/
cycle_basis.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 hashbrown::{HashMap, HashSet};
14use petgraph::visit::{IntoNeighbors, IntoNodeIdentifiers, NodeCount};
15use std::hash::Hash;
16
17/// Return a list of cycles which form a basis for cycles of a given graph.
18///
19/// A basis for cycles of a graph is a minimal collection of
20/// cycles such that any cycle in the graph can be written
21/// as a sum of cycles in the basis.  Here summation of cycles
22/// is defined as the exclusive-or of the edges.
23///
24/// This is adapted from
25///    Paton, K. An algorithm for finding a fundamental set of
26///    cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518.
27///
28/// The function implicitly assumes that there are no parallel edges.
29/// It may produce incorrect/unexpected results if the input graph has
30/// parallel edges.
31///
32///
33/// Arguments:
34///
35/// * `graph` - The graph in which to find the basis.
36/// * `root` - Optional node index for starting the basis search. If not
37///   specified, an arbitrary node is chosen.
38///
39/// # Example
40/// ```rust
41/// use petgraph::prelude::*;
42/// use rustworkx_core::connectivity::cycle_basis;
43///
44/// let edge_list = [(0, 1), (0, 3), (0, 5), (1, 2), (2, 3), (3, 4), (4, 5)];
45/// let graph = UnGraph::<i32, i32>::from_edges(&edge_list);
46/// let mut res: Vec<Vec<NodeIndex>> = cycle_basis(&graph, Some(NodeIndex::new(0)));
47/// ```
48pub fn cycle_basis<G>(graph: G, root: Option<G::NodeId>) -> Vec<Vec<G::NodeId>>
49where
50    G: NodeCount,
51    G: IntoNeighbors,
52    G: IntoNodeIdentifiers,
53    G::NodeId: Eq + Hash,
54{
55    let mut root_node = root;
56    let mut graph_nodes: HashSet<G::NodeId> = graph.node_identifiers().collect();
57    let mut cycles: Vec<Vec<G::NodeId>> = Vec::new();
58    while !graph_nodes.is_empty() {
59        let temp_value: G::NodeId;
60        // If root_node is not set get an arbitrary node from the set of graph
61        // nodes we've not "examined"
62        let root_index = match root_node {
63            Some(root_node) => root_node,
64            None => {
65                temp_value = *graph_nodes.iter().next().unwrap();
66                graph_nodes.remove(&temp_value);
67                temp_value
68            }
69        };
70        // Stack (ie "pushdown list") of vertices already in the spanning tree
71        let mut stack: Vec<G::NodeId> = vec![root_index];
72        // Map of node index to predecessor node index
73        let mut pred: HashMap<G::NodeId, G::NodeId> = HashMap::new();
74        pred.insert(root_index, root_index);
75        // Set of examined nodes during this iteration
76        let mut used: HashMap<G::NodeId, HashSet<G::NodeId>> = HashMap::new();
77        used.insert(root_index, HashSet::new());
78        // Walk the spanning tree
79        // Use the last element added so that cycles are easier to find
80        while let Some(z) = stack.pop() {
81            for neighbor in graph.neighbors(z) {
82                // A new node was encountered:
83                if !used.contains_key(&neighbor) {
84                    pred.insert(neighbor, z);
85                    stack.push(neighbor);
86                    let mut temp_set: HashSet<G::NodeId> = HashSet::new();
87                    temp_set.insert(z);
88                    used.insert(neighbor, temp_set);
89                // A self loop:
90                } else if z == neighbor {
91                    let cycle: Vec<G::NodeId> = vec![z];
92                    cycles.push(cycle);
93                // A cycle was found:
94                } else if !used.get(&z).unwrap().contains(&neighbor) {
95                    let prev_n = used.get(&neighbor).unwrap();
96                    let mut cycle: Vec<G::NodeId> = vec![neighbor, z];
97                    let mut p = pred.get(&z).unwrap();
98                    while !prev_n.contains(p) {
99                        cycle.push(*p);
100                        p = pred.get(p).unwrap();
101                    }
102                    cycle.push(*p);
103                    cycles.push(cycle);
104                    let neighbor_set = used.get_mut(&neighbor).unwrap();
105                    neighbor_set.insert(z);
106                }
107            }
108        }
109        let mut temp_hashset: HashSet<G::NodeId> = HashSet::new();
110        for key in pred.keys() {
111            temp_hashset.insert(*key);
112        }
113        graph_nodes = graph_nodes.difference(&temp_hashset).copied().collect();
114        root_node = None;
115    }
116    cycles
117}
118
119#[cfg(test)]
120mod tests {
121    use crate::connectivity::cycle_basis;
122    use petgraph::prelude::*;
123
124    fn sorted_cycle(cycles: Vec<Vec<NodeIndex>>) -> Vec<Vec<usize>> {
125        let mut sorted_cycles: Vec<Vec<usize>> = vec![];
126        for cycle in cycles {
127            let mut cycle: Vec<usize> = cycle.iter().map(|x| x.index()).collect();
128            cycle.sort();
129            sorted_cycles.push(cycle);
130        }
131        sorted_cycles.sort();
132        sorted_cycles
133    }
134
135    #[test]
136    fn test_cycle_basis_source() {
137        let edge_list = vec![
138            (0, 1),
139            (0, 3),
140            (0, 5),
141            (0, 8),
142            (1, 2),
143            (1, 6),
144            (2, 3),
145            (3, 4),
146            (4, 5),
147            (6, 7),
148            (7, 8),
149            (8, 9),
150        ];
151        let graph = UnGraph::<i32, i32>::from_edges(edge_list);
152        let expected = vec![vec![0, 1, 2, 3], vec![0, 1, 6, 7, 8], vec![0, 3, 4, 5]];
153        let res_0 = cycle_basis(&graph, Some(NodeIndex::new(0)));
154        assert_eq!(sorted_cycle(res_0), expected);
155        let res_1 = cycle_basis(&graph, Some(NodeIndex::new(1)));
156        assert_eq!(sorted_cycle(res_1), expected);
157        let res_9 = cycle_basis(&graph, Some(NodeIndex::new(9)));
158        assert_eq!(sorted_cycle(res_9), expected);
159    }
160
161    #[test]
162    fn test_self_loop() {
163        let edge_list = vec![
164            (0, 1),
165            (0, 3),
166            (0, 5),
167            (0, 8),
168            (1, 2),
169            (1, 6),
170            (2, 3),
171            (3, 4),
172            (4, 5),
173            (6, 7),
174            (7, 8),
175            (8, 9),
176        ];
177        let mut graph = UnGraph::<i32, i32>::from_edges(edge_list);
178        graph.add_edge(NodeIndex::new(1), NodeIndex::new(1), 0);
179        let res_0 = cycle_basis(&graph, Some(NodeIndex::new(0)));
180        assert_eq!(
181            sorted_cycle(res_0),
182            vec![
183                vec![0, 1, 2, 3],
184                vec![0, 1, 6, 7, 8],
185                vec![0, 3, 4, 5],
186                vec![1]
187            ]
188        );
189    }
190}
rustworkx_core/connectivity/cycle_basis.rs

rustworkx_core/connectivity/
cycle_basis.rs
