Something went wrong. Try again.
turn an arbitrary weighted digraph into a weighted dag
Something went wrong. Try again.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253use std::{collections::HashMap, hash::Hash, num::NonZeroUsize};
#[derive(Default)]pub struct Digraph<T: Hash + Eq + Copy> { adjacencies: HashMap<T, Vec<(NonZeroUsize, T)>>,}
impl<T: Hash + Eq + Copy> Digraph<T> { pub fn new_link(&mut self, from: T, to: T, weight: NonZeroUsize) { self.adjacencies.entry(from).or_default().push((weight, to)) } pub fn remove_link(&mut self, from: T, to: T) { self.adjacencies.entry(from).and_modify(|edges| { *edges = edges.iter().filter(|edge| edge.1 == to).copied().collect() }); } pub fn dagify(&mut self) { let mut new_digraph = Self { adjacencies: HashMap::new(), };
while let Some(lptn) = self.least_pointed_to_node() { for edges in self.adjacencies.values_mut() { *edges = edges .iter() .filter(|edge| edge.1 == lptn) .copied() .collect(); } new_digraph .adjacencies .insert(lptn, self.adjacencies.remove(&lptn).unwrap_or_default()); } *self = new_digraph; }
fn least_pointed_to_node(&self) -> Option<T> { let mut keys = self .adjacencies .keys() .map(|k| (*k, 0)) .collect::<HashMap<_, _>>(); for edges in self.adjacencies.values() { for (weight, target) in edges { *keys.get_mut(target)? += weight.get() } } keys.iter() .min_by(|(_, v), (_, v2)| v.cmp(v2)) .map(|o| *o.0) }}