// Copyright 2003, Trustees of Indiana University
// Please see the license in the file ../LICENSE

public class bellman_ford_shortest_paths {
  public static
    <Vertex,
     Edge extends GraphEdge<Vertex>,
     EdgeIterator extends java.util.Iterator<Edge>,
     Distance,
     WeightMap extends ReadablePropertyMap,
     PredecessorMap extends ReadWritePropertyMap,
     DistanceMap extends ReadWritePropertyMap,
     DistanceCombine extends BinaryFunction,
     DistanceCompare extends StrictWeakOrdering>
  boolean bellman_ford_shortest_paths(EdgeListGraph<Vertex,Edge,EdgeIterator> g, int size, WeightMap w, PredecessorMap predecessor, DistanceMap distance, DistanceCombine combine, DistanceCompare compare) {
    boolean any_relaxed;
    for (int i = 0; i < size; ++i) {
      any_relaxed = false; // Optimization from BGL
      for (EdgeIterator e_iter = g.edges(); e_iter.hasNext();) {
	Edge e = e_iter.next();
	if(relax.relax(e, w, distance, predecessor, combine, compare)) {
	  any_relaxed = true;
	}
      }
      if (!any_relaxed) break;
    }
    for (EdgeIterator e_iter = g.edges(); e_iter.hasNext();) {
      Edge e = e_iter.next();
      if (compare.less(combine.op(w.get(e), distance.get(e.source())), distance.get(e.target()))) {
	return false;
      }
    }
    return true;
  }
}