blob: de666eafb2bd39acdc7fcb1dcb56249457739ac7 [file] [log] [blame]
use petgraph::{graph::stable::StableDiGraph, visit::EdgeRef};
use petgraph_algorithms::cycles::{greedy_feedback_arc_set, is_cyclic_directed};
use petgraph_graph::DiGraph;
use petgraph_proptest::tournament::graph_tournament_strategy;
use proptest::prelude::*;
#[cfg(not(miri))]
proptest! {
#[test]
fn remaining_graph_is_acyclic(mut graph in any::<StableDiGraph<(), (), u8>>()) {
let feedback_arc_set = greedy_feedback_arc_set(&graph).map(|edge| edge.id()).collect::<Vec<_>>();
for edge in feedback_arc_set {
graph.remove_edge(edge);
}
prop_assert!(!is_cyclic_directed(&graph));
}
/// Assert that the size of the feedback arc set of a tournament does not exceed
/// **|E| / 2 - |V| / 6**
#[test]
#[allow(clippy::cast_sign_loss, clippy::cast_possible_truncation, clippy::cast_precision_loss)]
fn performance_within_bound(graph in graph_tournament_strategy::<DiGraph<(), ()>>(0..128)) {
let expected_bound = if graph.node_count() < 2 {
0
} else {
((graph.edge_count() as f64) / 2.0 - (graph.node_count() as f64) / 6.0) as usize
};
let size = greedy_feedback_arc_set(&graph).count();
prop_assert!(size <= expected_bound);
}
}