blob: a5fa31b2dabf0906bc0919571fc0b77c8bc83e24 [file] [log] [blame]
//! Integration tests for Tarjan's and Kosaraju's strongly connected components algorithms.
//!
//! As both algorithms are very similar, we test them together.
//!
//! Uses the various graph representations that are consolidated in the `petgraph` crate to test
//! against.
//!
//! All tests are run against the same graph, which is a directed graph with 9 nodes and 9 edges.
//!
//! The graph is as follows:
//!
//! ```text
//! 6 → 0 4
//! ↑ ↖ ↓
//! 8 3
//! ↓ ↖
//! 2 → 5 ← 7 → 1
//! ↓ ↗
//! 9
//! ```
//!
//! The strongly connected components are:
//! * `0, 3, 6`
//! * `1, 7, 9`
//! * `2, 5, 8`
//! * `4`
use petgraph::graphmap::GraphMap;
use petgraph_adjacency_matrix::{AdjacencyList, UnweightedAdjacencyList};
use petgraph_algorithms::components::{kosaraju_scc, tarjan_scc};
use petgraph_core::{
edge::Directed,
id::{DefaultIx, SafeCast},
visit::{GraphBase, Reversed},
};
use petgraph_graph::{stable::StableGraph, Graph};
use proptest::prelude::*;
const EDGES: &[(DefaultIx, DefaultIx)] = &[
(6, 0),
(0, 3),
(3, 6),
(8, 6),
(8, 2),
(2, 5),
(5, 8),
(7, 5),
(1, 7),
(7, 9),
(9, 1),
];
fn assert_scc<T: SafeCast<usize>, U: SafeCast<usize>>(
received: Vec<Vec<T>>,
expected: Vec<Vec<U>>,
) {
assert_eq!(received.len(), expected.len());
// We first convert both representations to usize, so that we can sort them.
let mut received: Vec<_> = received
.into_iter()
.map(|component| {
component
.into_iter()
.map(SafeCast::cast)
.collect::<Vec<_>>()
})
.collect();
let mut expected: Vec<_> = expected
.into_iter()
.map(|component| {
component
.into_iter()
.map(SafeCast::cast)
.collect::<Vec<_>>()
})
.collect();
// The order of the components is not guaranteed, so we first order all components by their
// index.
for component in &mut received {
component.sort_unstable();
}
for component in &mut expected {
component.sort_unstable();
}
// we now have a ordered components, but the order of the components is still not guaranteed,
// therefore we sort them by their first element.
// We know that each component has at least one element, so we can safely use indexed access
// here.
received.sort_by_key(|component| component[0]);
expected.sort_by_key(|component| component[0]);
assert_eq!(received, expected);
}
fn adjacency_list(
scc: impl FnOnce(
AdjacencyList<(), DefaultIx>,
) -> Vec<Vec<petgraph::adjacency_matrix::NodeIndex<DefaultIx>>>,
) {
let mut graph = UnweightedAdjacencyList::<DefaultIx>::new();
for _ in 0..10 {
graph.add_node();
}
for &(from, to) in EDGES {
graph.add_edge(
petgraph::adjacency_matrix::NodeIndex::new(from),
petgraph::adjacency_matrix::NodeIndex::new(to),
(),
);
}
let scc = scc(graph);
assert_scc(scc, vec![
vec![0usize, 3, 6], //
vec![1, 7, 9],
vec![2, 5, 8],
vec![4],
]);
}
#[test]
fn adjacency_list_tarjan() {
adjacency_list(|graph| tarjan_scc(&graph));
}
fn graph_map(scc: impl FnOnce(GraphMap<DefaultIx, (), Directed>) -> Vec<Vec<DefaultIx>>) {
let mut graph = GraphMap::<DefaultIx, (), Directed>::new();
for index in 0..10 {
graph.add_node(index);
}
for &(from, to) in EDGES {
graph.add_edge(from, to, ());
}
let scc = scc(graph);
assert_scc(scc, vec![
vec![0usize, 3, 6], //
vec![1, 7, 9],
vec![2, 5, 8],
vec![4],
]);
}
#[test]
fn graph_map_tarjan() {
graph_map(|graph| tarjan_scc(&graph));
}
#[test]
fn graph_map_kosaraju() {
graph_map(|graph| kosaraju_scc(&graph));
}
fn graph(
scc: impl FnOnce(Graph<(), (), Directed, DefaultIx>) -> Vec<Vec<petgraph::graph::NodeIndex>>,
) {
let graph = Graph::from_edges(EDGES);
let scc = scc(graph);
assert_scc(scc, vec![
vec![0usize, 3, 6], //
vec![1, 7, 9],
vec![2, 5, 8],
vec![4],
]);
}
#[test]
fn graph_tarjan() {
graph(|graph| tarjan_scc(&graph));
}
#[test]
fn graph_kosaraju() {
graph(|graph| kosaraju_scc(&graph));
}
fn stable_graph(
scc: impl FnOnce(StableGraph<(), (), Directed, DefaultIx>) -> Vec<Vec<petgraph::graph::NodeIndex>>,
) {
let mut graph = StableGraph::from_edges(EDGES);
// from_edges does not add isolated nodes, so we add them manually.
graph.add_node(());
let scc = scc(graph);
assert_scc(scc, vec![
vec![0usize, 3, 6], //
vec![1, 7, 9],
vec![2, 5, 8],
vec![4],
]);
}
#[test]
fn stable_graph_tarjan() {
stable_graph(|graph| tarjan_scc(&graph));
}
#[test]
fn stable_graph_kosaraju() {
stable_graph(|graph| kosaraju_scc(&graph));
}
#[cfg(not(miri))]
proptest! {
/// Ensure that when reversing the graph, the SCCs are still the same.
#[test]
fn graph_kosaraju_reverse_same(graph in any::<Graph<(), (), Directed, u8>>()) {
let scc = kosaraju_scc(&graph);
let reversed = kosaraju_scc(Reversed(&graph));
assert_scc(scc, reversed);
}
#[test]
fn graphmap_kosaraju_reverse_same(graph in any::<GraphMap<u8, (), Directed>>()) {
let scc = kosaraju_scc(&graph);
let reversed = kosaraju_scc(Reversed(&graph));
assert_scc(scc, reversed);
}
/// Ensure that when reversing the graph, the SCCs are still the same.
#[test]
fn graph_tarjan_reverse_same(graph in any::<Graph<(), (), Directed, u8>>()) {
let scc = tarjan_scc(&graph);
let reversed = tarjan_scc(Reversed(&graph));
assert_scc(scc, reversed);
}
#[test]
fn graphmap_tarjan_reverse_same(graph in any::<GraphMap<u8, (), Directed>>()) {
let scc = tarjan_scc(&graph);
let reversed = tarjan_scc(Reversed(&graph));
assert_scc(scc, reversed);
}
#[test]
fn kosaraju_tarjan_same(graph in any::<Graph<(), (), Directed, u8>>()) {
let kosaraju = kosaraju_scc(&graph);
let tarjan = tarjan_scc(&graph);
assert_scc(kosaraju, tarjan);
}
}