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 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
//! # generic_graph //! //!`generic_graph` defines a series of traits for the implementation of either directed and //! non directed graphs. This library also provides a few default implementation if the programmer //! doesn't have special requirements for his graphs. //! //!All traits make large use of generic types, allowing for deep customization of the graph structure //! use std::hash::Hash; use std::ops::{Add, Sub}; pub mod adjacency_list; ///Generic behaviour of a vertex /// /// Key type (K) must implement Hash, Eq and Clone /// /// Value type is free pub trait Vertex<K, V> where K: Hash + Eq + Clone { fn get_value(&self) -> &V; fn get_mut_value(&mut self) -> &mut V; fn key(&self) -> K; } ///Generic behaviour of an edge /// ///Generic type C is the key type of the edge /// ///Generic type K is the key type of the vertexes connected by the edge /// ///Generic type W is pub trait Edge<K, W, C> where K: Hash + Eq + Clone, C: Hash + Eq + Clone, W: Add + Sub + Eq + Ord + Copy { fn get_weight(&self) -> W; fn set_weight(&mut self, weight: W); fn left(&self) -> &K; fn right(&self) -> &K; ///This pair must not be used as a key for the edge, this must instead be used to generate the key /// or to construct a new edge fn get_pair(&self) -> (&K, &K); ///An associated function constructing the edge key from a pair of /// vertex keys must be implemented for the edge tipe /// ///the key returned by the key(&self) method must correspond to the key generated by said function /// with the pair of keys returned by the method get_pair(&self) fn generate_key(pair: (&K, &K)) -> C; ///The key returned by this method must correspond to the key generated by passing the pair of keys /// returned by get_pair(&self) to rhe associated function generate_key(pair: (&T, &T)) fn key(&self) -> C; } ///This trait define the behaviour of a directed graph /// it requires the for vertexes (T), edges (E), vertex's keys (K), vertex's values (v), edge's weights (W) and edge's keys (C) pub trait DirectedGraph<T, E, K, V, W, C> where K: Hash + Eq + Clone, C: Hash + Eq + Clone, W: Add + Sub + Eq + Ord + Copy, T: Vertex<K, V>, E: Edge<K, W, C> { ///This method returns a boolean stating if exist an edge from the first vertex to the other fn adjacent(&self, from: &K, to: &K) -> bool; ///This method returns a vector containing the keys of all the vertexes reached by edges starting from the argument fn neighbors(&self, from: &K) -> Vec<&K>; ///This method returns a vector containing the keys of all the vertexes with by edges leading to the argument fn leading_to(&self, to: &K) -> Vec<&K>; ///This method returns a vector containing references to the keys of all vertexes in the graph fn get_all_keys(&self) -> Vec<&K>; ///This method returns a vector containing the pairs of all edges in the graph fn get_all_pairs(&self) -> Vec<(&K, &K)>; fn get_vertex(&self, key: &K) -> Option<&T>; fn get_mut_vertex(&mut self, key: &K) -> Option<&mut T>; fn get_edge(&self, pair: (&K, &K)) -> Option<&E>; fn get_mut_edge(&mut self, pair: (&K, &K)) -> Option<&mut E>; } ///This trait adds to a Directed graph the methods to add and remove edges pub trait VariableEdges<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C> where K: Hash + Eq + Clone, C: Hash + Eq + Clone, W: Add + Sub + Eq + Ord + Copy, T: Vertex<K, V>, E: Edge<K, W, C> { ///If an edge with an equal key is already present, the edge is updated (not the key) /// and the old edge is returned ad Ok(Some(old_edge)). If not present OK(None) is returned. /// ///If one or both of the concerned vertexes are missing an error will be returned containing /// an enum specifying which side is missing fn add_edge(&mut self, edge: E) -> Result<Option<E>, EdgeSide>; ///If the removed edge was present it's removed and returned as Some(edge). Otherwise None is returned fn remove_edge(&mut self, pair: (&K, &K)) -> Option<E>; } ///This trait adds to a Directed graph the methods to add and remove edges pub trait VariableVertexes<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C> where K: Hash + Eq + Clone, C: Hash + Eq + Clone, W: Add + Sub + Eq + Ord + Copy, T: Vertex<K, V>, E: Edge<K, W, C> { ///If a vertex with an equal key is already present, the vertex is updated (not the key) /// and the old vertex is returned ad Some(old_vertex). If not present None is returned. fn add_vertex(&mut self, vertex: T) -> Option<T>; ///If the removed vertex was present it's removed and returned as Some(vertex). Otherwise None is returned fn remove_vertex(&mut self, key: K) -> Option<T>; } ///This trait does not add methods. It just indicates that the graph is not directed. /// ///As such, the vectors returned by the method neighbors(&self, from: &K) and leading_to(&self, to: &K) /// contains the same keys, eventually in different order (Unless the graph muted between calls). /// ///Also the outcome the methods accepting a pair of keys (adjacent(...), get_edge(...), get_mutable_edge(...)) /// must not be influenced by the order of the keys. pub trait Graph<T, E, K, V, W, C>: DirectedGraph<T, E, K, V, W, C> where K: Hash + Eq + Clone, C: Hash + Eq + Clone, W: Add + Sub + Eq + Ord + Copy, T: Vertex<K, V>, E: Edge<K, W, C> {} ///A default implementation for vertexes. This implementation should be suitable for most of the /// problem one can encounter requiring graph. /// ///Contrary to other graph implementation this library does not expect the vertexes to store if they /// have been visited, or if they were marked. The reason for this is that the author believes such an /// information should be stored in a structure extern and independent to the graph, this to ensure /// consistency between threads and to allow different algorithms to use different structures according /// to their needs /// ///methods are self explanatory #[derive(Debug, Eq, PartialEq)] pub struct SimpleVertex<K: Hash + Eq + Clone, V> { key: K, value: V, } impl<K: Hash + Eq + Clone, V> SimpleVertex<K, V> { ///Creates a new instance of SimpleVertex pub fn new(key: K, value: V) -> SimpleVertex<K, V> { SimpleVertex { key, value, } } } ///`EdgeSide` is used to indicate which side of the edge caused an error. /// Usually returned as Result::Err(EdgeSide) by the VariableEdges::add_edge() method when /// it was impossible to add the edge due to the absence of one of the concerned vertexes. /// ///Can be used by user defined functions or types for error handling. #[derive(Debug, Eq, PartialEq)] pub enum EdgeSide { Left, Right, Both } ///`SimpleVertex` implement the Vertex trait maintaining the key type and the value type generics impl<K: Hash + Eq + Clone, V> Vertex<K, V> for SimpleVertex<K, V> { ///Get the value stored in a vertex fn get_value(&self) -> &V { &(self.value) } ///Get the value as mutable reference fn get_mut_value(&mut self) -> &mut V { &mut (self.value) } ///Returns the key of the vertex fn key(&self) -> K { self.key.clone() } } #[cfg(test)] mod tests { use super::*; #[test] fn simple_vertex_construction() { let vertex = SimpleVertex::new(1,0); assert_eq!(vertex, SimpleVertex {key: 1, value: 0}); } #[test] fn simple_vertex_getters() { let mut vertex = SimpleVertex::new(1,0); assert_eq!(vertex.get_value(), &0); assert_eq!(vertex.key(), 1); *vertex.get_mut_value() += 3; assert_eq!(vertex.get_value(), &3); } }