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

/* Traverses a graph using the DepthFirstIterator class, with
   an attached TraversalListener and an additional stack for
   visited vertices.

   When TraversalListener first visits a node (by calling
   vertexTraversed()), the 'from' node of this node is 
   obtained from the stack, and used to add an edge to a
   gTree graph. Also, the node is pushed onto the stack.

   When TraveralListener finally departs a node (by calling
   vertexFinished()), the node is popped from the stack.

   By the end, gTree is a tree representing the depth-first
   traversal over the original graph.

   For a simpler depth-first traversal, see DGTraversal.java

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

import java.util.*;

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

import org.jgrapht.event.*;



public class DepthListener
                implements TraversalListener<String, DefaultEdge>
{
  private Graph<String, DefaultEdge> g;
  private Graph<String, DefaultEdge> gTree;  
                  // used to record the traversal over g

  private Stack<String> stk = new Stack<>();
                  // stores visited node IDs


  public DepthListener()
  {
    g = new DefaultDirectedGraph<>(DefaultEdge.class);
    gTree = new DefaultDirectedGraph<>(DefaultEdge.class);

    for(int i=0; i < 6; i++) {  // g and gTree have same vertices
      g.addVertex("v" + i);
      gTree.addVertex("v" + i);
    }

    g.addEdge("v0", "v1");  // only add edges to the g graph
    g.addEdge("v0", "v3");
    g.addEdge("v1", "v3");
    g.addEdge("v1", "v2");
    g.addEdge("v2", "v1");
    g.addEdge("v3", "v2");
    g.addEdge("v3", "v4");
    g.addEdge("v3", "v5");
    g.addEdge("v5", "v2");


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

    System.out.println("\nDepth first from v0");
    List<String> nodes = new ArrayList<>();
    DepthFirstIterator<String, DefaultEdge> dfi = 
                   new DepthFirstIterator<>(g, "v0"); 
    dfi.addTraversalListener(this);

    while (dfi.hasNext()) {
      String v = dfi.next();
      // System.out.print(v + " ");
       nodes.add(v);
    }
    System.out.println();
    System.out.println("\nNodes visited: " + nodes);

    JGTUtils.displayAsDOT("Depth first Tree", gTree);
  } // end of DepthListener()



  // implements TraversalListener ----------------

  public void connectedComponentStarted(
                         ConnectedComponentTraversalEvent ev)
  {  System.out.println("Traversal Started");  }
  

  public void connectedComponentFinished(
                    ConnectedComponentTraversalEvent ev)
  {  System.out.println("Traversal Finished");  }



  public void vertexTraversed(VertexTraversalEvent<String> ev)
  /* Node traversal is starting. 
     Get the 'from' node of this node from the stack, and use
     it to add an edge to gTree. Also push this node onto the
     stack.
  */
  {  String v = ev.getVertex();
    // System.out.println("Visiting " + v);
    if (!stk.empty()) {
      String fromVert = stk.peek();  // the vertex that we just came from
      System.out.println(fromVert + " - " + v);
      gTree.addEdge(fromVert, v); // add an edge to gTree
    }
    stk.push(v);
  } // end of vertexTraversed()



  public void vertexFinished(VertexTraversalEvent<String> ev)
  // node traversal is finished, so pop from stack
  {
    System.out.println("Finished " + ev.getVertex());
    stk.pop();
  }
  


  public void edgeTraversed​(EdgeTraversalEvent<DefaultEdge> ev)
  // edge traversal info isn't needed here
  {
   // DefaultEdge e = ev.getEdge();
   // System.out.println("Traversed: " + 
   //        g.getEdgeSource(e) + " - " + g.getEdgeTarget(e));
  }

  
  // ----------------------------------------------------

  public static void main(String[] args)
  {   new DepthListener();  }

}