rs_graph/shortestpath/
moorebellmanford.rs

1// Copyright (c) 2016-2022 Frank Fischer <frank-fischer@shadow-soft.de>
2//
3// This program is free software: you can redistribute it and/or
4// modify it under the terms of the GNU General Public License as
5// published by the Free Software Foundation, either version 3 of the
6// License, or (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful, but
9// WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11// General Public License for more details.
12//
13// You should have received a copy of the GNU General Public License
14// along with this program.  If not, see  <http://www.gnu.org/licenses/>
15//
16
17#![allow(clippy::type_complexity)]
18
19use crate::num::traits::NumAssign;
20
21use crate::traits::{Graph, IndexDigraph, IndexGraph};
22
23/// The shortest-path algorithm by Moore-Bellman-Ford on a directed graph.
24///
25/// The function returns pair. The first element is the vector of the
26/// incoming edge for each (reachable) node. The second element a node
27/// on a negative cylce if it exists, otherwise it is `None`.
28///
29/// # Example
30///
31/// ```
32/// use rs_graph::{LinkedListGraph, Buildable, Builder, traits::*};
33/// use rs_graph::shortestpath::moorebellmanford;
34///
35/// let mut weights = vec![];
36/// let mut g = LinkedListGraph::<usize>::new_with(|b| {
37///     let nodes = b.add_nodes(7);
38///     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),
39///                      (4,3,8), (5,3,-1), (6,3,4), (6,4,6), (6,5,3)].iter()
40///     {
41///         b.add_edge(nodes[u], nodes[v]);
42///         weights.push(w);
43///     }
44/// });
45///
46/// let (pred, cycle) = moorebellmanford::directed(&g, |e| weights[g.edge_id(e)], g.id2node(6));
47/// assert_eq!(cycle, None);
48/// assert_eq!(pred[6], None);
49/// for &(u,p) in [(0,2), (1,0), (2,3), (4,1), (5,6)].iter() {
50///     assert_eq!(g.src(pred[u].unwrap()), g.id2node(p));
51/// }
52/// ```
53pub fn directed<'a, G, W, F>(g: &'a G, weights: F, src: G::Node<'a>) -> (Vec<Option<G::Edge<'a>>>, Option<G::Node<'a>>)
54where
55    G: 'a + IndexDigraph,
56    W: NumAssign + Ord + Copy,
57    F: Fn(G::Edge<'a>) -> W,
58{
59    let mut pred = vec![None; g.num_nodes()];
60    let mut dist = vec![W::zero(); g.num_nodes()];
61    let src = g.node_id(src);
62
63    dist[src] = W::zero();
64
65    for i in 0..g.num_nodes() {
66        let mut changed = false;
67        for e in g.edges() {
68            let (u, v) = (g.src(e), g.snk(e));
69            let uid = g.node_id(u);
70            let vid = g.node_id(v);
71
72            // skip source nodes that have not been seen, yet
73            if uid != src && pred[uid].is_none() {
74                continue;
75            }
76
77            let newdist = dist[uid] + weights(e);
78            if dist[vid] > newdist || pred[vid].is_none() {
79                dist[vid] = newdist;
80                pred[vid] = Some(e);
81                changed = true;
82
83                if i + 1 == g.num_nodes() {
84                    return (pred, Some(v));
85                }
86            }
87        }
88        if !changed {
89            break;
90        }
91    }
92
93    (pred, None)
94}
95
96/// The shortest-path algorithm by Moore-Bellman-Ford on an undirected graph.
97///
98/// The function returns pair. The first element is the vector of the
99/// incoming edge for each (reachable) node. The second element a node
100/// on a negative cylce if it exists, otherwise it is `None`.
101pub fn undirected<'a, G, W, F>(
102    g: &'a G,
103    weights: F,
104    src: G::Node<'a>,
105) -> (Vec<Option<G::Edge<'a>>>, Option<G::Node<'a>>)
106where
107    G: IndexGraph + Graph,
108    W: NumAssign + Ord + Copy,
109    F: Fn(G::Edge<'a>) -> W,
110{
111    let mut pred = vec![None; g.num_nodes()];
112    let mut dist = vec![W::zero(); g.num_nodes()];
113    let src = g.node_id(src);
114
115    dist[src] = W::zero();
116
117    for i in 0..g.num_nodes() {
118        let mut changed = false;
119        for e in g.edges() {
120            let (u, v) = g.enodes(e);
121            for &(u, v) in &[(u, v), (v, u)] {
122                // skip source nodes that have not been seen, yet
123                let uid = g.node_id(u);
124                let vid = g.node_id(v);
125                if uid != src && pred[uid].is_none() {
126                    continue;
127                }
128
129                let newdist = dist[uid] + weights(e);
130                if dist[vid] > newdist || pred[vid].is_none() {
131                    dist[vid] = newdist;
132                    pred[vid] = Some(e);
133                    changed = true;
134
135                    if i + 1 == g.num_nodes() {
136                        return (pred, Some(v));
137                    }
138                }
139            }
140        }
141        if !changed {
142            break;
143        }
144    }
145
146    (pred, None)
147}
rs_graph/shortestpath/moorebellmanford.rs

rs_graph/shortestpath/
moorebellmanford.rs
