pub fn greedy_feedback_arc_set<G>(
    g: G
) -> impl Iterator<Item = <G as IntoEdgeReferences>::EdgeRef>where
    G: IntoEdgeReferences + GraphProp<EdgeType = Directed> + NodeCount,
    <G as GraphBase>::NodeId: GraphIndex,
Expand description

[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, but does not necessarily find the minimum feedback arc set. Time complexity is roughly O(|E|) for an input graph with edges E.

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.


use petgraph::{
    algo::{greedy_feedback_arc_set, is_cyclic_directed},

let mut g: StableGraph<(), ()> = StableGraph::from_edges(&[
    (0, 1),
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 5),
    (5, 0),
    (4, 1),
    (1, 3),


let fas: Vec<EdgeIndex> = greedy_feedback_arc_set(&g).map(|e|;

// Remove edges in feedback arc set from original graph
for edge_id in fas {