// DGShortest.java
// Minh Van Nguyen, John V Sichi, Tom Larkworthy, and Contributors, 2021
// Modified by Andrew Davison, ad@coe.psu.ac.th, Jan. 2023

/* Examples of three shortest path algorithms:
    * Dijkstra
    * Bellman-Ford
    * Floyd-Warshall

   Alse see DGTraversal.java, where BFSShortestPath is used.

  Usage:
    > compile DGShortest.java
    > run DGShortest
*/

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.graph.*;

import org.jgrapht.alg.shortestpath.*;
import org.jgrapht.alg.interfaces.*;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm.*;



public class DGShortest
{

  public static void main(String args[])
  {
    unweighted();
    weighted();
  }  // end of main()



  private static void unweighted()
  {
    System.out.println("-------------- unweighted -------------\n");

    String[][] edges = {{"a", "b"}, {"b", "d"}, {"d", "c"},
                        {"c", "a"}, {"e", "d"}, {"e", "f"},
                        {"f", "g"}, {"g", "e"}, {"h", "e"}, 
                        {"i", "h"}};
    Graph<String, DefaultEdge> g = JGTUtils.makeDG(edges);  
                        // directed graph; unweighted


    // System.out.println("Graph:\n" + g + "\n");
    System.out.println("Adj List:\n" + JGTUtils.writeAdjList(g));
    JGTUtils.displayAsDOT("unweighted", g);


    System.out.println("\nDijkstra Shortest path from i to c:");
    DijkstraShortestPath<String, DefaultEdge> dij =
                                new DijkstraShortestPath<>(g);
    SingleSourcePaths<String, DefaultEdge> paths = dij.getPaths("i");
    System.out.println("  " + paths.getPath("c"));

    System.out.println("Dijkstra Shortest path from c to i:");
    paths = dij.getPaths("c");
    System.out.println("  " + paths.getPath("i"));   // no such path

    System.out.println("\nBellman-Ford shortest path for i to c:");
    BellmanFordShortestPath<String, DefaultEdge> bell =
                          new BellmanFordShortestPath<>(g);
    System.out.println("  " + bell.getPath("i", "c").getVertexList() );

  } /* unweighted */



  private static void weighted()
  {
    System.out.println("\n -------------- weighted -------------\n");

    Graph<String, WeightedEdge> g =
      new SimpleDirectedWeightedGraph<>(WeightedEdge.class);

    Graphs.addAllVertices(g, Arrays.asList(
              "a", "b", "c", "d", "e", "f", "g", "h", "i"));

    Graphs.addEdge(g, "a", "b", 5);
    Graphs.addEdge(g, "b", "d", 2);
    Graphs.addEdge(g, "d", "c", 3);
    Graphs.addEdge(g, "c", "a", 2);
    Graphs.addEdge(g, "e", "d", 5);
    Graphs.addEdge(g, "e", "f", 2);
    Graphs.addEdge(g, "f", "g", 3);
    Graphs.addEdge(g, "g", "e", 2);
    Graphs.addEdge(g, "h", "e", 3);
    Graphs.addEdge(g, "i", "h", 2);

    JGTUtils.displayAsDOT("weighted", g);

    FloydWarshallShortestPaths<String, WeightedEdge> fw =
      new FloydWarshallShortestPaths<>(g);

    GraphPath<String, WeightedEdge> path = fw.getPath("i", "c");

    System.out.println("\nFloyd-Warshall for i to c:\n  " +
            path.getVertexList() + "; weights: " + 
            path + "; sum: " + path.getWeight());

  }  // end of weighted

}