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

// dijkstra_shortest_paths algorithm from BFS

import java.lang.*;

public class dijkstra_shortest_paths {
  public static <
    Vertex,
    Edge extends GraphEdge<Vertex>,
    VertexIterator extends java.util.Iterator<Vertex>,
    OutEdgeIterator extends java.util.Iterator<Edge>,
    WeightMap extends ReadablePropertyMap<Edge,Distance>,
    DistanceMap extends ReadWritePropertyMap<Vertex,Distance>,
    Distance,
    PredecessorMap extends ReadWritePropertyMap<Vertex,Vertex>,
    DistanceCombine extends BinaryFunction<Distance>,
    DistanceCompare extends StrictWeakOrdering<Distance>>
  void dijkstra_shortest_paths(VertexListAndIncidenceGraph<Vertex,Edge,VertexIterator,OutEdgeIterator> g, Vertex s, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, DistanceCompare compare, DistanceCombine combine, Distance inf, Distance zero) {
    for(VertexIterator u_iter = g.vertices(); u_iter.hasNext(); ) {
      Vertex u = u_iter.next();
      distance.set(u, inf);
      predecessor.set(u, u);
    }
    distance.set(s, zero);

    indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare> icmp 
      = new indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare>(distance, compare);
    mutable_queue<Vertex, indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare>> Q 
      = new mutable_queue<Vertex, indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare>>(icmp);

    dijkstra_visitor<VertexListAndIncidenceGraph<Vertex,Edge,VertexIterator,OutEdgeIterator>, mutable_queue<Vertex, indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare>>, WeightMap, PredecessorMap, DistanceMap, DistanceCombine, DistanceCompare, Vertex, Edge, Distance> vis 
      = new dijkstra_visitor<VertexListAndIncidenceGraph<Vertex,Edge,VertexIterator,OutEdgeIterator>, mutable_queue<Vertex, indirect_cmp<Vertex, Distance, DistanceMap, DistanceCompare>>, WeightMap, PredecessorMap, DistanceMap, DistanceCombine, DistanceCompare, Vertex, Edge, Distance>(Q, weight, predecessor, distance, combine, compare, zero);

    hash_property_map<Vertex, java.lang.Integer> color
      = new hash_property_map<Vertex, java.lang.Integer>();

    // Initialize color map
    for (VertexIterator i = g.vertices(); i.hasNext();) {
      Vertex v = i.next();
      color.set(v, ColorValue.white());
    }

    graph_search.graph_search(
      g,
      s,
      vis,
      color,
      Q);
  }
}