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
use std::fmt; use std::fmt::Debug; /// This represents a sequence of nodes. The length is also saved, and when ```exists = false```, this means "there is no path". #[derive(Clone, Debug)] pub struct Path<T> { v: Vec<T>, len: usize, exists: bool, } impl<T> Path<T> { pub(crate) fn set_vector(&mut self, t: Vec<T>) { self.v = t } /// Returns the intermediate nodes on this path as a slice. pub fn get_slice<'a>(&'a self) -> &'a [T] { &self.v } /// Returns an iterator of the intermediat enodes on this path. pub fn iter<'a>(&'a self) -> impl DoubleEndedIterator<Item = &'a T> { self.v.iter() } /// Returns the length of this path. pub fn len(&self) -> usize { assert!(self.exists); self.len } /// Updates the length of this path. Also removes the "there is not path here"-flag. pub(crate) fn set_len(&mut self, v: usize) { self.len = v; self.exists = true; } /// Has this path finite length? pub fn exists(&self) -> bool { self.exists } } impl<T> AsRef<Vec<T>> for Path<T> { fn as_ref(&self) -> &Vec<T> { &self.v } } impl<T> Default for Path<T> { fn default() -> Self { use std::usize::MAX; Path { v: Vec::new(), len: MAX, exists: false, } } } /// This matrix is a solution to the APSP problem, calculated by the Floyd-Warshall algorithm. /// It contains the intermediate nodes on the shortest path between every two nodes. #[derive(Debug)] pub struct PathMatrix<T> { m: Box<[Path<T>]>, n: usize, } impl<T> PathMatrix<T> { /// Creates a new ```PathMatrix``` with the given dimension (n * n), where no paths were found yet. /// That means, no nodes are yet connected in this matrix. pub fn new(n: usize) -> PathMatrix<T> { let mut m = vec![]; let n_elems = 1 + n * (n - 1) / 2; for _ in 0..n_elems { m.push(Path::default()); } let m = m.into(); PathMatrix { m, n } } /// This method computes the "inner index" into the ```Vec``` by using the given X-Y-coordinates into the matrix. fn idx(&self, mut i: usize, mut j: usize) -> usize { // Because we're only supporting undirected graphs and we only fill one half of the matrix, // we can swap the two indices, so that i <= j. if i > j { ::std::mem::swap(&mut i, &mut j); } assert!(i <= j); if i == j { 0 } else { // i + self.n * j // This is for the old n x n matrix. // j + k + i if j < 3 { j + i } else { let k = j - 1; self.idx(0, j - 1) + k + i } } } /// This method returns the value at the given position. pub fn get_path_len(&self, i: usize, j: usize) -> usize { let idx = self.idx(i, j); self.m[idx].len() } /// This method returns the shortest path possible between i and i. pub fn get_path(&self, i: usize, j: usize) -> &Path<T> { let idx = self.idx(i, j); &self.m[idx] } /// This method returns the shortest path possible between i and i as an iterator. pub fn get_path_iter<'a>( &'a self, i: usize, j: usize, ) -> impl DoubleEndedIterator<Item = &'a T> { let idx = self.idx(i, j); self.m[idx].iter() } /// If the matrix contains a path between i and j (which means, it has a set length), this returns true. pub fn does_path_exist(&self, i: usize, j: usize) -> bool { let idx = self.idx(i, j); self.m[idx].exists() } /// Returns a mutable reference to the path object for the two given nodes. pub(crate) fn get_path_mut(&mut self, i: usize, j: usize) -> &mut Path<T> { let idx = self.idx(i, j); &mut self.m[idx] } /// This method updates the value at the given position. pub fn set_path_len(&mut self, i: usize, j: usize, v: usize) { let idx = self.idx(i, j); self.m[idx].set_len(v); } } // impl<T> Debug for PathMatrix<T> // where // T: Debug, // { // fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { // use std::result::Result; // for j in 0..self.n { // let from = j * self.n; // let to = j * self.n + j + 1; // writeln!(f, "{:?}", &self.m[from..to])? // } // Result::Ok(()) // } // } // /// This matrix is a solution to the APSP problem, calculated by the Floyd-Warshall algorithm. It contains the length of the shortest path for every pair of nodes in a given graph. // pub struct DistanceMatrix { // m: Box<[usize]>, // n: usize, // } // impl DistanceMatrix { // /// Creates a new ```DistanceMatrix``` with the given dimension (n * n). // pub(crate) fn new(n: usize) -> DistanceMatrix { // use std::usize::MAX; // let m = vec![MAX; n * n].into(); // DistanceMatrix { m, n } // } // /// This method computes the "inner index" into the ```Vec``` by using the given X-Y-coordinates into the matrix. // fn idx(&self, mut i: usize, mut j: usize) -> usize { // // We only fill one half of the matrix. // if i > j { // ::std::mem::swap(&mut i, &mut j); // } // assert!(i <= j); // i + self.n * j // } // /// This method returns the value at the given position. // pub fn get(&self, i: usize, j: usize) -> usize { // let idx = self.idx(i, j); // self.m[idx] // } // /// This method updates the value at the given position. // pub fn set(&mut self, i: usize, j: usize, v: usize) { // let idx = self.idx(i, j); // self.m[idx] = v; // } // } // impl fmt::Debug for DistanceMatrix { // fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { // use std::result::Result; // for j in 0..self.n { // let from = j * self.n; // let to = j * self.n + j + 1; // writeln!(f, "{:?}", &self.m[from..to])? // } // Result::Ok(()) // } // }