Function petgraph::algo::feedback_arc_set::greedy_feedback_arc_set

pub fn greedy_feedback_arc_set<G>(g: G) -> impl Iterator<Item = G::EdgeRef>
where
    G: IntoEdgeReferences + GraphProp<EdgeType = Directed> + NodeCount,
    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, 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));