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 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
#[derive(Debug, PartialEq, Eq, Clone, Copy)] pub struct Node(usize); impl Node { pub fn to_usize(&self) -> usize { self.0 } } #[derive(Debug, PartialEq, Eq, Clone, Copy)] pub struct Edge(usize, usize); impl Edge { pub fn to_tuple(&self) -> (usize, usize) { (self.0, self.1) } } #[derive(Debug)] pub struct DiGraph { assoc: Vec<Vec<usize>>, } impl DiGraph { pub fn new() -> Self { Self { assoc: vec![], } } pub fn len(&self) -> usize { self.assoc.len() } pub fn node(&mut self) -> Node { let index = self.assoc.len(); self.assoc.push(vec![]); Node(index) } pub fn edge(&mut self, from: Node, to: Node) -> Edge { let from = from.0; let to = to.0; self.assoc[from].push(to); Edge(from, to) } pub fn has_edge(&self, from: Node, to: Node) -> bool { let (from, to) = (from.0, to.0); self.assoc[from].contains(&to) } pub fn get_node(&self, index: usize) -> Option<Node> { if index < self.len() { Some(Node(index)) } else { None } } pub fn get_edge(&self, from: usize, to: usize) -> Option<Edge> { if match (self.get_node(from), self.get_node(to)) { (Some(from), Some(to)) => self.has_edge(from, to), _ => false, } { Some(Edge(from, to)) } else { None } } pub fn cycle_from(&self, target: Node) -> bool { let target = target.0; let mut visited = vec![false; self.len()]; let mut stack = vec![target]; while let Some(current) = stack.pop() { visited[current] = true; for node in &self.assoc[current] { if !visited[*node] { stack.push(*node); } else if *node == target { return true } } } false } } #[cfg(test)] mod test { use super::*; #[test] fn cycle_from() { let mut graph = DiGraph::new(); let n0 = graph.node(); let n1 = graph.node(); graph.edge(n0, n1); graph.edge(n1, n0); assert!(graph.cycle_from(n0)); assert!(graph.cycle_from(n1)); } #[test] fn no_cycle_from() { let mut graph = DiGraph::new(); let n0 = graph.node(); let n1 = graph.node(); graph.edge(n0, n1); assert!(!graph.cycle_from(n0)); assert!(!graph.cycle_from(n1)); } #[test] fn cycle_not_containing_target() { let mut graph = DiGraph::new(); let n0 = graph.node(); let n1 = graph.node(); let n2 = graph.node(); graph.edge(n0, n1); graph.edge(n1, n0); graph.edge(n2, n0); graph.edge(n2, n1); assert!(graph.cycle_from(n0)); assert!(graph.cycle_from(n1)); assert!(!graph.cycle_from(n2)); } #[test] fn get_node() { let mut graph = DiGraph::new(); let n0 = graph.node(); let n1 = graph.node(); let n2 = graph.node(); assert_eq!(graph.get_node(0), Some(n0)); assert_eq!(graph.get_node(1), Some(n1)); assert_eq!(graph.get_node(2), Some(n2)); assert_eq!(graph.get_node(3), None); } #[test] fn get_edge() { let mut graph = DiGraph::new(); let n0 = graph.node(); let n1 = graph.node(); let e0 = graph.edge(n0, n1); assert_eq!(graph.get_edge(0, 1), Some(e0)); assert_eq!(graph.get_edge(1, 0), None); assert_eq!(graph.get_edge(1, 2), None); } }