Function bevy_internal::utils::petgraph::algo::condensation
source · pub fn condensation<N, E, Ty, Ix>(
g: Graph<N, E, Ty, Ix>,
make_acyclic: bool
) -> Graph<Vec<N>, E, Ty, Ix>
Expand description
Graph Condense every strongly connected component into a single node and return the result.
If make_acyclic
is true, self-loops and multi edges are ignored, guaranteeing that
the output is acyclic.
§Example
use petgraph::Graph;
use petgraph::algo::condensation;
use petgraph::prelude::*;
let mut graph : Graph<(),(),Directed> = Graph::new();
let a = graph.add_node(()); // node with no weight
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
graph.extend_with_edges(&[
(a, b),
(b, c),
(c, d),
(d, a),
(b, e),
(e, f),
(f, g),
(g, h),
(h, e)
]);
// a ----> b ----> e ----> f
// ^ | ^ |
// | v | v
// d <---- c h <---- g
let condensed_graph = condensation(graph,false);
let A = NodeIndex::new(0);
let B = NodeIndex::new(1);
assert_eq!(condensed_graph.node_count(), 2);
assert_eq!(condensed_graph.edge_count(), 9);
assert_eq!(condensed_graph.neighbors(A).collect::<Vec<_>>(), vec![A, A, A, A]);
assert_eq!(condensed_graph.neighbors(B).collect::<Vec<_>>(), vec![A, B, B, B, B]);
If make_acyclic
is true, self-loops and multi edges are ignored:
let acyclic_condensed_graph = condensation(graph, true);
let A = NodeIndex::new(0);
let B = NodeIndex::new(1);
assert_eq!(acyclic_condensed_graph.node_count(), 2);
assert_eq!(acyclic_condensed_graph.edge_count(), 1);
assert_eq!(acyclic_condensed_graph.neighbors(B).collect::<Vec<_>>(), vec![A]);