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

using GCollections;

public class null_property_map<A,B>: ReadWritePropertyMap<A,B> {
  public B this[A a] {
    get {throw new System.Exception();}
    set {}
  }
}

public class johnson_all_pairs_shortest_paths {
  public static bool go
    <Graph,
     Vertex,
     Edge,
     VertexIterator,
     OutEdgeIterator,
     EdgeIterator,
     Distance,
     WeightMap,
     WeightMap2,
     DistanceMap,
     DistanceMatrixElement,
     DistanceMatrix,
     DistanceCombine,
     DistanceCompare,
     DistanceNegate>
  (Graph g, WeightMap w, WeightMap2 w2, DistanceMap distance, DistanceMatrix distance_matrix, Distance zero, Distance inf, DistanceCombine combine, DistanceNegate negate, DistanceCompare compare)
  where Graph: VertexListAndIncidenceAndEdgeListGraph<Vertex,Edge,VertexIterator,OutEdgeIterator,EdgeIterator>,
	Edge: GraphEdge<Vertex>,
	VertexIterator: IEnumerable<Vertex>,
	OutEdgeIterator: IEnumerable<Edge>,
	EdgeIterator: IEnumerable<Edge>,
	WeightMap: ReadablePropertyMap<Edge, Distance>,
	WeightMap2: ReadWritePropertyMap<Edge, Distance>,
	DistanceMap: ReadWritePropertyMap<Vertex, Distance>,
	DistanceMatrixElement: ReadWritePropertyMap<Vertex, Distance>,
	DistanceMatrix: ReadablePropertyMap<Vertex, DistanceMatrixElement>,
	DistanceCombine: BinaryFunction<Distance>,
	DistanceCompare: StrictWeakOrdering<Distance>,
	DistanceNegate: UnaryFunction<Distance> {
    // Set distance to all vertices to zero (emulates special "s" vertex used in CLR)
    for (IEnumerator<Vertex> vi = g.vertices().GetEnumerator(); vi.MoveNext();) {
      Vertex v = vi.Current;
      ((ReadWritePropertyMap<Vertex,Distance>)distance)[v] = zero;
    }

    // Do Bellman-Ford to get factors for reweighting
    bool bf_worked = bellman_ford_shortest_paths.go<
      Graph,
      Vertex,
      Edge,
      EdgeIterator,
      Distance,
      WeightMap,
      null_property_map<Vertex,Vertex>,
      DistanceMap,
      DistanceCombine,
      DistanceCompare>
    (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 (IEnumerator<Edge> ei = g.edges().GetEnumerator(); ei.MoveNext();) {
      Edge e = ei.Current;
      ((ReadWritePropertyMap<Edge,Distance>)w2)[e] = combine.op(combine.op(((ReadablePropertyMap<Edge,Distance>)w)[e], ((ReadWritePropertyMap<Vertex,Distance>)distance)[e.source]), negate.op(((ReadWritePropertyMap<Vertex,Distance>)distance)[e.target]));
    }

    // Do Dijkstra from each vertex
    for (IEnumerator<Vertex> vi = g.vertices().GetEnumerator(); vi.MoveNext();) {
      Vertex v = vi.Current;
      DistanceMatrixElement dm = ((ReadablePropertyMap<Vertex,DistanceMatrixElement>)distance_matrix)[v];
      dijkstra_shortest_paths.go<
	Graph,
	Vertex,
	Edge,
	VertexIterator,
	OutEdgeIterator,
	WeightMap2,
	DistanceMatrixElement,
	Distance,
	null_property_map<Vertex,Vertex>,
	DistanceCombine,
	DistanceCompare>
      (g, v, new null_property_map<Vertex,Vertex>(), dm, w2, compare, combine, inf, zero);

      // Adjust returned distances to account for reweighting
      for (IEnumerator<Vertex> vi2 = g.vertices().GetEnumerator(); vi2.MoveNext();) {
	Vertex v2 = vi2.Current;
	((ReadWritePropertyMap<Vertex,Distance>)dm)[v2] = combine.op(combine.op(((ReadWritePropertyMap<Vertex,Distance>)dm)[v2], ((ReadWritePropertyMap<Vertex,Distance>)distance)[v2]), negate.op(((ReadWritePropertyMap<Vertex,Distance>)distance)[v]));
      }
    }
    return true;
  }
}