use crate::prelude::*;
use crate::visit::{IntoEdges, IntoNodeIdentifiers, NodeCount, NodeIndexable, VisitMap, Visitable};
use super::{FloatMeasure, NegativeCycle};
#[derive(Debug, Clone)]
pub struct Paths<NodeId, EdgeWeight> {
pub distances: Vec<EdgeWeight>,
pub predecessors: Vec<Option<NodeId>>,
}
pub fn bellman_ford<G>(
g: G,
source: G::NodeId,
) -> Result<Paths<G::NodeId, G::EdgeWeight>, NegativeCycle>
where
G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
G::EdgeWeight: FloatMeasure,
{
let ix = |i| g.to_index(i);
let (distances, predecessors) = bellman_ford_initialize_relax(g, source);
for i in g.node_identifiers() {
for edge in g.edges(i) {
let j = edge.target();
let w = *edge.weight();
if distances[ix(i)] + w < distances[ix(j)] {
return Err(NegativeCycle(()));
}
}
}
Ok(Paths {
distances,
predecessors,
})
}
pub fn find_negative_cycle<G>(g: G, source: G::NodeId) -> Option<Vec<G::NodeId>>
where
G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable + Visitable,
G::EdgeWeight: FloatMeasure,
{
let ix = |i| g.to_index(i);
let mut path = Vec::<G::NodeId>::new();
let (distance, predecessor) = bellman_ford_initialize_relax(g, source);
'outer: for i in g.node_identifiers() {
for edge in g.edges(i) {
let j = edge.target();
let w = *edge.weight();
if distance[ix(i)] + w < distance[ix(j)] {
let start = j;
let mut node = start;
let mut visited = g.visit_map();
loop {
let ancestor = match predecessor[ix(node)] {
Some(predecessor_node) => predecessor_node,
None => node, };
if ancestor == start {
path.push(ancestor);
break;
}
else if visited.is_visited(&ancestor) {
let pos = path
.iter()
.position(|&p| p == ancestor)
.expect("we should always have a position");
path = path[pos..path.len()].to_vec();
break;
}
path.push(ancestor);
visited.visit(ancestor);
node = ancestor;
}
break 'outer;
}
}
}
if !path.is_empty() {
path.reverse();
Some(path)
} else {
None
}
}
#[inline(always)]
fn bellman_ford_initialize_relax<G>(
g: G,
source: G::NodeId,
) -> (Vec<G::EdgeWeight>, Vec<Option<G::NodeId>>)
where
G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
G::EdgeWeight: FloatMeasure,
{
let mut predecessor = vec![None; g.node_bound()];
let mut distance = vec![<_>::infinite(); g.node_bound()];
let ix = |i| g.to_index(i);
distance[ix(source)] = <_>::zero();
for _ in 1..g.node_count() {
let mut did_update = false;
for i in g.node_identifiers() {
for edge in g.edges(i) {
let j = edge.target();
let w = *edge.weight();
if distance[ix(i)] + w < distance[ix(j)] {
distance[ix(j)] = distance[ix(i)] + w;
predecessor[ix(j)] = Some(i);
did_update = true;
}
}
}
if !did_update {
break;
}
}
(distance, predecessor)
}