# Function bevy::utils::petgraph::algo::greedy_feedback_arc_set

``````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.

## 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));``````