[−][src]Function petgraph::algo::greedy_feedback_arc_set
pub fn greedy_feedback_arc_set<G>(g: G) -> impl Iterator<Item = G::EdgeRef> where
G: IntoEdgeReferences + GraphProp<EdgeType = Directed>,
G::NodeId: GraphIndex,
[Generic] Finds a feedback arc set: a set of edges in the given directed graph, which when removed, make the graph acyclic.
Uses a greedy heuristic algorithm to select a small number of edges in reasonable time, but does not necessarily find the minimum feedback arc set.
Does not consider edge/node weights when selecting edges for the feedback arc set.
Loops (edges to and from the same node) are always included in the returned set.
Example
use petgraph::{ algo::{greedy_feedback_arc_set, is_cyclic_directed}, graph::EdgeIndex, stable_graph::StableGraph, visit::EdgeRef, }; let mut g: StableGraph<(), ()> = StableGraph::from_edges(&[ (0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (4, 1), (1, 3), ]); assert!(is_cyclic_directed(&g)); let fas: Vec<EdgeIndex> = greedy_feedback_arc_set(&g).map(|e| e.id()).collect(); // Remove edges in feedback arc set from original graph for edge_id in fas { g.remove_edge(edge_id); } assert!(!is_cyclic_directed(&g));