// DGTraversal.java
// Andrew Davison, ad@coe.psu.ac.th, Jan. 2023

/* Traverses a graph in two ways, using the
   DepthFirstIterator and BreadthFirstIterator classes.

   For a more complex depth first traversal, 
   see DepthListener.java

   BFSShortestPath is used to get a shortest path in the BFF tree.
   For more shortest path algorithms, see DGShortest.java.

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

import java.util.*;

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

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


public class DGTraversal
{

  public static void main(String[] args)
  {
   // two graph examples; uncomment one of them...
/*
    Graph<String, DefaultEdge> g = 
                new DefaultDirectedGraph<>(DefaultEdge.class);
    for(int i=0; i < 10; i++)
      g.addVertex("v" + i);

    g.addEdge("v1", "v2");  // unweighted
    g.addEdge("v2", "v4");
    g.addEdge("v4", "v3");
    g.addEdge("v3", "v1");
    g.addEdge("v5", "v4");
    g.addEdge("v5", "v6");
    g.addEdge("v6", "v7");
    g.addEdge("v7", "v5");
    g.addEdge("v8", "v5");
    g.addEdge("v9", "v8");
*/

    String[][] edges = {{"v0", "v1"}, {"v0", "v3"}, {"v1", "v3"},
                        {"v1", "v2"}, {"v2", "v1"}, {"v3", "v2"},
                        {"v3", "v4"}, {"v3", "v5"}, {"v5", "v2"}};
    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(g);

    System.out.println("\nDepth first traversal from v0");
    Iterator<String> dfi = new DepthFirstIterator<>(g, "v0");  // "v9"
    while (dfi.hasNext())
      System.out.print(dfi.next() + " ");
    System.out.println();

    System.out.println("\nBreadth first traversal from v0");
    Iterator<String> bfi = new BreadthFirstIterator<>(g, "v0");  // v9
    while (bfi.hasNext()) 
      System.out.print(bfi.next() + " ");
    System.out.println();

    // for more shortest path algorithms, see DGShortest.java
    SingleSourcePaths<String, DefaultEdge> ssPaths = 
                   new BFSShortestPath<>(g).getPaths("v0");
    GraphPath<String, DefaultEdge> path05 = ssPaths.getPath("v5");
    System.out.println("\nShortest BFF path v0 -> v5: " + 
                                   path05.getVertexList());

  } // end of main()

}  // end of DGTraversal class