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
// Copyright (c) 2016-2020 Frank Fischer <frank-fischer@shadow-soft.de> // // This program is free software: you can redistribute it and/or // modify it under the terms of the GNU General Public License as // published by the Free Software Foundation, either version 3 of the // License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/> // #![allow(clippy::type_complexity)] use crate::num::traits::NumAssign; use crate::traits::{Graph, IndexDigraph, IndexGraph}; use crate::vec::NodeVec; /// The shortest-path algorithm by Moore-Bellman-Ford on a directed graph. /// /// The function returns pair. The first element is the vector of the /// incoming edge for each (reachable) node. The second element a node /// on a negative cylce if it exists, otherwise it is `None`. /// /// # Example /// /// ``` /// use rs_graph::{LinkedListGraph, Buildable, Builder, EdgeVec, traits::*}; /// use rs_graph::shortestpath::moorebellmanford; /// /// let mut weights = vec![]; /// let mut g = LinkedListGraph::<usize>::new_with(|b| { /// let nodes = b.add_nodes(7); /// for &(u,v,w) in [(0,1,-8), (1,4,-3), (2,0,2), (2,1,1), (2,5,-3), (3,1,0), (3,2,5), /// (4,3,8), (5,3,-1), (6,3,4), (6,4,6), (6,5,3)].iter() /// { /// b.add_edge(nodes[u], nodes[v]); /// weights.push(w); /// } /// }); /// /// let (pred, cycle) = moorebellmanford::directed(&g, |e| weights[g.edge_id(e)], g.id2node(6)); /// assert_eq!(cycle, None); /// assert_eq!(pred[g.id2node(6)], None); /// for &(u,p) in [(0,2), (1,0), (2,3), (4,1), (5,6)].iter() { /// assert_eq!(g.src(pred[g.id2node(u)].unwrap()), g.id2node(p)); /// } /// ``` pub fn directed<'a, G, W, F>(g: &'a G, weights: F, src: G::Node) -> (NodeVec<&'a G, Option<G::Edge>>, Option<G::Node>) where G: 'a + IndexDigraph<'a>, W: NumAssign + Ord + Copy, F: Fn(G::Edge) -> W, { let mut pred = NodeVec::new(g, None); let mut dist = NodeVec::new(g, W::zero()); dist[src] = W::zero(); for i in 0..g.num_nodes() { let mut changed = false; for e in g.edges() { let (u, v) = (g.src(e), g.snk(e)); // skip source nodes that have not been seen, yet if u != src && pred[u].is_none() { continue; } let newdist = dist[u] + weights(e); if dist[v] > newdist || pred[v].is_none() { dist[v] = newdist; pred[v] = Some(e); changed = true; if i + 1 == g.num_nodes() { return (pred, Some(v)); } } } if !changed { break; } } (pred, None) } /// The shortest-path algorithm by Moore-Bellman-Ford on an undirected graph. /// /// The function returns pair. The first element is the vector of the /// incoming edge for each (reachable) node. The second element a node /// on a negative cylce if it exists, otherwise it is `None`. pub fn undirected<'a, G, W, F>(g: &'a G, weights: F, src: G::Node) -> (NodeVec<&'a G, Option<G::Edge>>, Option<G::Node>) where G: 'a + IndexGraph<'a> + Graph<'a>, W: NumAssign + Ord + Copy, F: Fn(G::Edge) -> W, { let mut pred = NodeVec::new(g, None); let mut dist = NodeVec::new(g, W::zero()); dist[src] = W::zero(); for i in 0..g.num_nodes() { let mut changed = false; for e in g.edges() { let (u, v) = g.enodes(e); for &(u, v) in &[(u, v), (v, u)] { // skip source nodes that have not been seen, yet if u != src && pred[u].is_none() { continue; } let newdist = dist[u] + weights(e); if dist[v] > newdist || pred[v].is_none() { dist[v] = newdist; pred[v] = Some(e); changed = true; if i + 1 == g.num_nodes() { return (pred, Some(v)); } } } } if !changed { break; } } (pred, None) }