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

using GCollections;

public class bellman_ford_shortest_paths {
  public static bool
    go<Graph,
       Vertex,
       Edge,
       EdgeIterator,
       Distance,
       WeightMap,
       PredecessorMap,
       DistanceMap,
       DistanceCombine,
       DistanceCompare>
  (Graph g, int size, WeightMap w, PredecessorMap predecessor, DistanceMap distance, DistanceCombine combine, DistanceCompare compare)
  where Graph: EdgeListGraph<Vertex,Edge,EdgeIterator>,
	Edge: GraphEdge<Vertex>,
	EdgeIterator: IEnumerable<Edge>,
	WeightMap: ReadablePropertyMap<Edge,Distance>,
	PredecessorMap: ReadWritePropertyMap<Vertex,Vertex>,
	DistanceMap: ReadWritePropertyMap<Vertex,Distance>,
	DistanceCombine: BinaryFunction<Distance>,
	DistanceCompare: StrictWeakOrdering<Distance> {
    bool any_relaxed;
    for (int i = 0; i < size; ++i) {
      any_relaxed = false; // Optimization from BGL
      for (IEnumerator<Edge> e_iter = g.edges().GetEnumerator(); e_iter.MoveNext();) {
	Edge e = e_iter.Current;
	if(relax.go<Vertex,Edge,WeightMap,Distance,DistanceMap,PredecessorMap,DistanceCombine,DistanceCompare>(e, w, distance, predecessor, combine, compare)) {
	  any_relaxed = true;
	}
      }
      if (!any_relaxed) break;
    }
    for (IEnumerator<Edge> e_iter = g.edges().GetEnumerator(); e_iter.MoveNext();) {
      Edge e = e_iter.Current;
      if (compare.less(combine.op(((ReadablePropertyMap<Edge,Distance>)w)[e], ((ReadWritePropertyMap<Vertex,Distance>)distance)[e.source]), ((ReadWritePropertyMap<Vertex,Distance>)distance)[e.target])) {
	return false;
      }
    }
    return true;
  }
}