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

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.

Arguments

• g: a directed graph.

Returns

• impl Iterator: the iterator of edge references G::EdgeRef in the feedback arc set.

Complexity

• Time complexity: O(|V| + |E|).
• Auxiliary space: O(|V| + |E|).

where |V| is the number of nodes and |E| is the number of edges.

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