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

public class johnson_all_pairs_shortest_paths {
  public static
    <Vertex,
     Edge extends GraphEdge<Vertex>,
     VertexIterator extends java.util.Iterator<Vertex>,
     OutEdgeIterator extends java.util.Iterator<Edge>,
     EdgeIterator extends java.util.Iterator<Edge>,
     Distance,
     WeightMap extends ReadablePropertyMap,
     WeightMap2 extends ReadWritePropertyMap,
     DistanceMap extends ReadWritePropertyMap,
     DistanceMatrixElement extends ReadWritePropertyMap,
     DistanceMatrix extends ReadablePropertyMap,
     DistanceCombine extends BinaryFunction,
     DistanceCompare extends StrictWeakOrdering,
     DistanceNegate extends UnaryFunction>
  boolean johnson_all_pairs_shortest_paths(VertexListAndIncidenceAndEdgeListGraph<Vertex,Edge,VertexIterator,OutEdgeIterator,EdgeIterator> g, WeightMap w, WeightMap2 w2, DistanceMap distance, final DistanceMatrix distance_matrix, Distance zero, Distance inf, DistanceCombine combine, DistanceNegate negate, DistanceCompare compare) {
    // Set distance to all vertices to zero (emulates special "s" vertex used in CLR)
    for (VertexIterator vi = g.vertices(); vi.hasNext();) {
      Vertex v = vi.next();
      distance.set(v, zero);
    }

    // Do Bellman-Ford to get factors for reweighting
    boolean bf_worked = bellman_ford_shortest_paths.bellman_ford_shortest_paths(
      g, 
      g.num_vertices(),
      w, 
      new null_property_map<Vertex,Vertex>(), 
      distance, 
      combine,
      compare);

    if (!bf_worked) return false; // Negative-weight cycle

    // Set up reweighting
    for (EdgeIterator ei = g.edges(); ei.hasNext(); ) {
      Edge e = ei.next();
      w2.set(e, combine.op(combine.op(w.get(e), distance.get(e.source())), negate.op(distance.get(e.target()))));
    }

    // Do Dijkstra from each vertex
    for (VertexIterator vi = g.vertices(); vi.hasNext(); ) {
      final Vertex v = vi.next();
      final ReadWritePropertyMap<Vertex,Distance> dm = (ReadWritePropertyMap)distance_matrix.get(v);
      dijkstra_shortest_paths.dijkstra_shortest_paths(
	g, 
	v,
	new null_property_map<Vertex,Vertex>(),
	dm,
	w2,
	compare,
	combine,
	inf,
	zero);

      // Adjust returned distances to account for reweighting
      for (VertexIterator vi2 = g.vertices(); vi2.hasNext(); ) {
	Vertex v2 = vi2.next();
	dm.set(v2, (Distance)combine.op(combine.op(dm.get(v2), distance.get(v2)), negate.op(distance.get(v))));
      }
    }
    return true;
  }
}