petgraph/algo/
feedback_arc_set.rs

1use alloc::{collections::VecDeque, vec::Vec};
2use core::ops::{Index, IndexMut};
3
4use hashbrown::HashMap;
5
6use crate::{
7    graph::{GraphIndex, NodeIndex},
8    visit::{EdgeRef, GraphProp, IntoEdgeReferences},
9    Directed,
10};
11
12use self::linked_list::{LinkedList, LinkedListEntry};
13
14/// \[Generic\] Finds a [feedback arc set]: a set of edges in the given directed graph, which when
15/// removed, make the graph acyclic.
16///
17/// Uses a [greedy heuristic algorithm] to select a small number of edges, but does not necessarily
18/// find the minimum feedback arc set.
19///
20/// Does not consider edge/node weights when selecting edges for the feedback arc set.
21///
22/// Loops (edges to and from the same node) are always included in the returned set.
23///
24/// # Arguments
25/// * `g`: a directed graph.
26///
27/// # Returns
28/// * `impl Iterator`:  the iterator of edge references `G::EdgeRef` in the feedback arc set.
29///
30/// # Complexity
31/// * Time complexity: **O(|V| + |E|)**.
32/// * Auxiliary space: **O(|V| + |E|)**.
33///
34/// where **|V|** is the number of nodes and **|E|** is the number of edges.
35///
36/// # Example
37///
38/// ```
39/// # #[cfg(feature = "stable_graph")] {
40/// use petgraph::{
41///     algo::{greedy_feedback_arc_set, is_cyclic_directed},
42///     graph::EdgeIndex,
43///     stable_graph::StableGraph,
44///     visit::EdgeRef,
45/// };
46///
47/// let mut g: StableGraph<(), ()> = StableGraph::from_edges(&[
48///     (0, 1),
49///     (1, 2),
50///     (2, 3),
51///     (3, 4),
52///     (4, 5),
53///     (5, 0),
54///     (4, 1),
55///     (1, 3),
56/// ]);
57///
58/// assert!(is_cyclic_directed(&g));
59///
60/// let fas: Vec<EdgeIndex> = greedy_feedback_arc_set(&g).map(|e| e.id()).collect();
61///
62/// // Remove edges in feedback arc set from original graph
63/// for edge_id in fas {
64///     g.remove_edge(edge_id);
65/// }
66///
67/// assert!(!is_cyclic_directed(&g));
68/// # }
69/// ```
70///
71/// [feedback arc set]: https://en.wikipedia.org/wiki/Feedback_arc_set
72/// [greedy heuristic algorithm]: https://doi.org/10.1016/0020-0190(93)90079-O
73pub fn greedy_feedback_arc_set<G>(g: G) -> impl Iterator<Item = G::EdgeRef>
74where
75    G: IntoEdgeReferences + GraphProp<EdgeType = Directed>,
76    G::NodeId: GraphIndex,
77    G: crate::visit::NodeCount,
78{
79    let node_seq = good_node_sequence(g.edge_references().map(|e| {
80        (
81            NodeIndex::new(e.source().index()),
82            NodeIndex::new(e.target().index()),
83        )
84    }));
85
86    g.edge_references()
87        .filter(move |e| node_seq[&e.source().index()] >= node_seq[&e.target().index()])
88}
89
90fn good_node_sequence(
91    edge_refs: impl Iterator<Item = (NodeIndex<usize>, NodeIndex<usize>)>,
92) -> HashMap<usize, usize> {
93    let mut nodes = FasNodeContainer { nodes: Vec::new() };
94    let mut buckets = Buckets {
95        sinks_or_isolated: NodeLinkedList::new(),
96        sources: NodeLinkedList::new(),
97        bidirectional_pve_dd: Vec::new(),
98        bidirectional_nve_dd: Vec::new(),
99    };
100    // Lookup of node indices from input graph to indices into `nodes`
101    let mut graph_ix_lookup = HashMap::new();
102
103    // Build node entries
104    for (from_g_ix, to_g_ix) in edge_refs {
105        let mut fas_node_entry = |g_ix: NodeIndex<usize>| -> FasNodeIndex {
106            match graph_ix_lookup.get(&g_ix) {
107                Some(fas_ix) => *fas_ix,
108                None => {
109                    let fas_ix = FasNodeIndex(nodes.nodes.len());
110
111                    nodes.nodes.push(LinkedListEntry::new(FasNode {
112                        graph_ix: g_ix,
113                        out_edges: Vec::new(),
114                        in_edges: Vec::new(),
115                        out_degree: 0,
116                        in_degree: 0,
117                    }));
118
119                    graph_ix_lookup.insert(g_ix, fas_ix);
120
121                    fas_ix
122                }
123            }
124        };
125
126        let from_fas_ix = fas_node_entry(from_g_ix);
127        let to_fas_ix = fas_node_entry(to_g_ix);
128
129        nodes[from_fas_ix].data().out_edges.push(to_fas_ix);
130        nodes[to_fas_ix].data().in_edges.push(from_fas_ix);
131    }
132
133    // Set initial in/out-degrees
134    for entry in nodes.nodes.iter_mut() {
135        let node = entry.data();
136        node.out_degree = node.out_edges.len();
137        node.in_degree = node.in_edges.len();
138    }
139
140    // Add nodes to initial lists
141    for i in 0..nodes.nodes.len() {
142        let fas_ix = FasNodeIndex(i);
143        buckets
144            .suitable_bucket(fas_ix, &mut nodes)
145            .push_front(fas_ix, &mut nodes);
146    }
147
148    let mut s_1 = VecDeque::new();
149    let mut s_2 = VecDeque::new();
150
151    loop {
152        let mut some_moved = false;
153
154        while let Some(sink_fas_ix) = buckets.sinks_or_isolated.pop(&mut nodes) {
155            some_moved = true;
156            buckets.update_neighbour_node_buckets(sink_fas_ix, &mut nodes);
157            s_2.push_front(nodes[sink_fas_ix].data().graph_ix);
158        }
159
160        while let Some(source_fas_ix) = buckets.sources.pop(&mut nodes) {
161            some_moved = true;
162            buckets.update_neighbour_node_buckets(source_fas_ix, &mut nodes);
163            s_1.push_back(nodes[source_fas_ix].data().graph_ix);
164        }
165
166        if let Some(list) = buckets
167            .bidirectional_pve_dd
168            .iter_mut()
169            .rev()
170            .chain(buckets.bidirectional_nve_dd.iter_mut())
171            .find(|b| b.start.is_some())
172        {
173            let highest_dd_fas_ix = list.pop(&mut nodes).unwrap();
174            some_moved = true;
175            buckets.update_neighbour_node_buckets(highest_dd_fas_ix, &mut nodes);
176            s_1.push_back(nodes[highest_dd_fas_ix].data().graph_ix);
177
178            Buckets::trim_bucket_list(&mut buckets.bidirectional_pve_dd);
179            Buckets::trim_bucket_list(&mut buckets.bidirectional_nve_dd);
180        }
181
182        if !some_moved {
183            break;
184        }
185    }
186
187    s_1.into_iter()
188        .chain(s_2)
189        .enumerate()
190        .map(|(seq_order, node_index)| (node_index.index(), seq_order))
191        .collect()
192}
193
194type NodeLinkedList = LinkedList<FasNode, FasNodeContainer, FasNodeIndex>;
195
196#[derive(Debug)]
197struct FasNodeContainer {
198    nodes: Vec<LinkedListEntry<FasNode, FasNodeIndex>>,
199}
200
201impl Index<FasNodeIndex> for FasNodeContainer {
202    type Output = LinkedListEntry<FasNode, FasNodeIndex>;
203
204    fn index(&self, index: FasNodeIndex) -> &Self::Output {
205        &self.nodes[index.0]
206    }
207}
208
209impl IndexMut<FasNodeIndex> for FasNodeContainer {
210    fn index_mut(&mut self, index: FasNodeIndex) -> &mut Self::Output {
211        &mut self.nodes[index.0]
212    }
213}
214
215#[derive(Debug)]
216struct Buckets {
217    sinks_or_isolated: NodeLinkedList,
218    sources: NodeLinkedList,
219    /// Bidirectional nodes with positive-or-0 delta degree
220    bidirectional_pve_dd: Vec<NodeLinkedList>,
221    /// Bidirectional nodes with negative delta degree (index 0 is -1 dd, 1 is -2 etc)
222    bidirectional_nve_dd: Vec<NodeLinkedList>,
223}
224
225#[derive(Clone, Copy, PartialEq, Debug)]
226struct FasNodeIndex(usize);
227
228/// Represents a node from the input graph, tracking its current delta degree
229#[derive(Debug)]
230struct FasNode {
231    /// Node index in input graph.
232    graph_ix: NodeIndex<usize>,
233
234    /// All outward edges from this node (not removed during processing)
235    out_edges: Vec<FasNodeIndex>,
236
237    /// All inward edges from this node (not removed during processing)
238    in_edges: Vec<FasNodeIndex>,
239
240    /// Current out-degree of this node (decremented during processing as connected nodes are
241    /// removed)
242    out_degree: usize,
243
244    /// Current in-degree of this node (decremented during processing as connected nodes are
245    /// removed)
246    in_degree: usize,
247}
248
249impl Buckets {
250    fn suitable_bucket(
251        &mut self,
252        ix: FasNodeIndex,
253        nodes: &mut FasNodeContainer,
254    ) -> &mut NodeLinkedList {
255        let node = nodes[ix].data();
256
257        if node.out_degree == 0 {
258            &mut self.sinks_or_isolated
259        } else if node.in_degree == 0 {
260            &mut self.sources
261        } else {
262            let delta_degree = node.out_degree as isize - node.in_degree as isize;
263
264            if delta_degree >= 0 {
265                let bucket_ix = delta_degree as usize;
266
267                if self.bidirectional_pve_dd.len() <= bucket_ix {
268                    self.bidirectional_pve_dd
269                        .resize_with(bucket_ix + 1, NodeLinkedList::new);
270                }
271
272                &mut self.bidirectional_pve_dd[bucket_ix]
273            } else {
274                let bucket_ix = (-delta_degree - 1) as usize;
275
276                if self.bidirectional_nve_dd.len() <= bucket_ix {
277                    self.bidirectional_nve_dd
278                        .resize_with(bucket_ix + 1, NodeLinkedList::new);
279                }
280
281                &mut self.bidirectional_nve_dd[bucket_ix]
282            }
283        }
284    }
285
286    fn update_neighbour_node_buckets(&mut self, ix: FasNodeIndex, nodes: &mut FasNodeContainer) {
287        for i in 0..nodes[ix].data().out_edges.len() {
288            let out_ix = nodes[ix].data().out_edges[i];
289
290            if out_ix == ix {
291                continue;
292            }
293
294            // Ignore nodes which have already been moved to the good sequence
295            if !nodes[out_ix].is_in_list() {
296                continue;
297            }
298
299            self.suitable_bucket(out_ix, nodes).remove(out_ix, nodes);
300
301            // Other node has lost an in-edge; reduce in-degree by 1
302            nodes[out_ix].data().in_degree -= 1;
303
304            self.suitable_bucket(out_ix, nodes)
305                .push_front(out_ix, nodes);
306        }
307
308        for i in 0..nodes[ix].data().in_edges.len() {
309            let in_ix = nodes[ix].data().in_edges[i];
310
311            if in_ix == ix {
312                continue;
313            }
314
315            // Ignore nodes which have already been moved to the good sequence
316            if !nodes[in_ix].is_in_list() {
317                continue;
318            }
319
320            self.suitable_bucket(in_ix, nodes).remove(in_ix, nodes);
321
322            // Other node has lost an out-edge; reduce out-degree by 1
323            nodes[in_ix].data().out_degree -= 1;
324
325            self.suitable_bucket(in_ix, nodes).push_front(in_ix, nodes);
326        }
327    }
328
329    fn trim_bucket_list(list: &mut Vec<NodeLinkedList>) {
330        let trunc_len = if let Some(highest_populated_index) =
331            (0..list.len()).rev().find(|i| list[*i].start.is_some())
332        {
333            highest_populated_index + 1
334        } else {
335            0
336        };
337
338        list.truncate(trunc_len);
339    }
340}
341
342mod linked_list {
343    use alloc::vec::Vec;
344    use core::{marker::PhantomData, ops::IndexMut};
345
346    #[derive(PartialEq, Debug)]
347    pub struct LinkedList<Data, Container, Ix> {
348        pub start: Option<Ix>,
349        marker: PhantomData<(Data, Container)>,
350    }
351
352    #[derive(Debug)]
353    pub struct LinkedListEntry<Data, Ix> {
354        pos: Option<LinkedListPosition<Ix>>,
355        data: Data,
356    }
357
358    #[derive(Debug)]
359    struct LinkedListPosition<Ix> {
360        prev: Option<Ix>,
361        next: Option<Ix>,
362    }
363
364    impl<Data, Ix> LinkedListEntry<Data, Ix> {
365        pub fn new(data: Data) -> Self {
366            LinkedListEntry { pos: None, data }
367        }
368
369        pub fn data(&mut self) -> &mut Data {
370            &mut self.data
371        }
372
373        pub fn is_in_list(&mut self) -> bool {
374            self.pos.is_some()
375        }
376
377        fn pos_mut(&mut self) -> &mut LinkedListPosition<Ix> {
378            self.pos
379                .as_mut()
380                .expect("expected linked list entry to have populated position")
381        }
382    }
383
384    impl<Data, Container, Ix> LinkedList<Data, Container, Ix>
385    where
386        Container: IndexMut<Ix, Output = LinkedListEntry<Data, Ix>>,
387        Ix: PartialEq + Copy,
388    {
389        pub fn new() -> Self {
390            LinkedList {
391                start: None,
392                marker: PhantomData,
393            }
394        }
395
396        pub fn push_front(&mut self, push_ix: Ix, container: &mut Container) {
397            if let Some(start_ix) = self.start {
398                let entry = &mut container[start_ix];
399                entry.pos_mut().prev = Some(push_ix);
400            }
401
402            let push_entry = &mut container[push_ix];
403            push_entry.pos = Some(LinkedListPosition {
404                next: self.start,
405                prev: None,
406            });
407
408            self.start = Some(push_ix);
409        }
410
411        pub fn pop(&mut self, container: &mut Container) -> Option<Ix> {
412            if let Some(remove_ix) = self.start {
413                self.remove(remove_ix, container);
414                Some(remove_ix)
415            } else {
416                None
417            }
418        }
419
420        /// `remove_ix` **must** be a member of the list headed by `self`
421        pub fn remove(&mut self, remove_ix: Ix, container: &mut Container) {
422            debug_assert!(
423                self.to_vec(container).contains(&remove_ix),
424                "node to remove should be member of current linked list"
425            );
426
427            let remove_entry = &mut container[remove_ix];
428            let ll_entry = remove_entry.pos.take().unwrap();
429
430            if let Some(prev_ix) = ll_entry.prev {
431                let prev_node = &mut container[prev_ix];
432                prev_node.pos_mut().next = ll_entry.next;
433            }
434
435            if let Some(next_ix) = ll_entry.next {
436                let next_node = &mut container[next_ix];
437                next_node.pos_mut().prev = ll_entry.prev;
438            }
439
440            // If the removed node was head of the list
441            if self.start == Some(remove_ix) {
442                self.start = ll_entry.next;
443            }
444        }
445
446        /// For debug purposes
447        fn to_vec(&self, container: &mut Container) -> Vec<Ix> {
448            let mut ixs = Vec::new();
449
450            let mut node_ix = self.start;
451
452            while let Some(n_ix) = node_ix {
453                ixs.push(n_ix);
454
455                node_ix = container[n_ix].pos_mut().next;
456            }
457
458            ixs
459        }
460    }
461}