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
14pub 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 let mut graph_ix_lookup = HashMap::new();
102
103 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 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 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_pve_dd: Vec<NodeLinkedList>,
221 bidirectional_nve_dd: Vec<NodeLinkedList>,
223}
224
225#[derive(Clone, Copy, PartialEq, Debug)]
226struct FasNodeIndex(usize);
227
228#[derive(Debug)]
230struct FasNode {
231 graph_ix: NodeIndex<usize>,
233
234 out_edges: Vec<FasNodeIndex>,
236
237 in_edges: Vec<FasNodeIndex>,
239
240 out_degree: usize,
243
244 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 if !nodes[out_ix].is_in_list() {
296 continue;
297 }
298
299 self.suitable_bucket(out_ix, nodes).remove(out_ix, nodes);
300
301 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 if !nodes[in_ix].is_in_list() {
317 continue;
318 }
319
320 self.suitable_bucket(in_ix, nodes).remove(in_ix, nodes);
321
322 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 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 self.start == Some(remove_ix) {
442 self.start = ll_entry.next;
443 }
444 }
445
446 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}