1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
use fnv::FnvHashSet; use crate::biedgedgraph::BiedgedGraph; #[derive(Clone)] pub struct NetGraph { pub graph: BiedgedGraph, pub x: u64, pub y: u64, pub path: Vec<u64>, } #[derive(Debug, PartialEq)] enum Color { Black, Gray, } impl Color { fn toggle(&self) -> Self { match self { Color::Black => Color::Gray, Color::Gray => Color::Black, } } } impl NetGraph { pub fn is_acyclic(&self) -> bool { let graph = &self.graph.graph; let mut visited: FnvHashSet<u64> = FnvHashSet::default(); let mut in_path: FnvHashSet<u64> = FnvHashSet::default(); let mut stack: Vec<(Color, u64)> = Vec::new(); let mut acyclic = true; let x = self.x; let start_color = if graph.edges(x).any(|(_, _, w)| w.black > 0) { Color::Gray } else { Color::Black }; stack.push((start_color, x)); while let Some((last_color, current)) = stack.pop() { if !visited.contains(¤t) { visited.insert(current); in_path.insert(current); let edges: Vec<_> = graph .edges(current) .filter(|(_, _, w)| match last_color { Color::Black => w.gray > 0, Color::Gray => w.black > 0, }) .collect(); stack.push((last_color.toggle(), current)); for (_, adj, _) in edges { if in_path.contains(&adj) { acyclic = false; } else { stack.push((last_color.toggle(), adj)); } } } else if in_path.contains(¤t) { in_path.remove(¤t); } } acyclic } pub fn is_bridgeless(&self) -> bool { for node in self.graph.graph.nodes() { if node != self.x && node != self.y && self .graph .graph .edges(node) .find(|(_, _, w)| w.black == 1) .is_none() { return false; } } true } pub fn is_ultrabubble(&self) -> bool { self.is_bridgeless() & self.is_acyclic() } }