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
#![no_std] use smallvec::SmallVec; type NodeIndex = usize; type Generation = usize; type NodeHandle = (NodeIndex, Generation); pub enum GraphError { GenerationMismatch, Unexpected, } pub struct Graph<T> { pub free: SmallVec<[NodeHandle; 128]>, pub nodes: SmallVec<[(Generation, Option<T>); 128]>, pub connections: SmallVec<[(NodeIndex, NodeIndex); 256]>, } impl<T> Graph<T> { pub fn insert(&mut self, value: T) -> NodeHandle { if self.free.len() == 0 { let index = self.nodes.len(); let gen = 0; self.nodes.push((gen, Some(value))); (index, gen) } else { let n = self.free.remove(0); let index = n.0; let gen = n.1; self.nodes[index] = (gen + 1, Some(value)); (n.0, gen + 1) } } pub fn directed_connect(&mut self, parent: NodeHandle, child: NodeHandle) { self.connections.push((parent.0, child.0)); } pub fn connect(&mut self, a: NodeHandle, b: NodeHandle) { self.connections.push((a.0, b.0)); self.connections.push((b.0, a.0)); } pub fn disconnect(&mut self, n: NodeHandle) { self.connections .retain(|&mut connection| (connection).0 != n.0 && (connection).1 != n.0); } pub fn is_connected(&mut self, a: NodeHandle, b: NodeHandle) -> bool { self.connections .iter() .find(|&connection| { (connection.0 == a.0 && connection.1 == b.0) || (connection.1 == a.0 && connection.0 == b.0) }) .is_some() } pub fn is_directed_connected(&mut self, parent: NodeHandle, child: NodeHandle) -> bool { self.connections .iter() .find(|&connection| connection.0 == parent.0 && connection.1 == child.0) .is_some() } pub fn remove(&mut self, n: NodeHandle) -> Result<T, GraphError> { let index = n.0; let gen = n.1; if self.nodes[index].0 == gen { self.disconnect(n); let mut r = (gen + 1, None); core::mem::swap(&mut self.nodes[index], &mut r); self.free.push(n); Ok(r.1.unwrap()) } else { Err(GraphError::GenerationMismatch) } } pub fn get(&self, n: NodeHandle) -> Result<&T, GraphError> { let index = n.0; let gen = n.1; if self.nodes[index].0 == gen { if let Some(value) = &self.nodes[index].1 { Ok(value) } else { Err(GraphError::Unexpected) } } else { Err(GraphError::GenerationMismatch) } } pub fn get_mut(&mut self, n: NodeHandle) -> Result<&mut T, GraphError> { let index = n.0; let gen = n.1; if self.nodes[index].0 == gen { if let Some(value) = &mut self.nodes[index].1 { Ok(value) } else { Err(GraphError::Unexpected) } } else { Err(GraphError::GenerationMismatch) } } }