// DetectCycles.java
// Rob Janes and Contributors, 2021
// Modified by Andrew Davison, ad@coe.psu.ac.th, Jan. 2023

/* Create two versions of a directed graph, one without cycles, and one
   with cycles, and then detect them. If there are no cycles, then the
   graph's nodes are printed in topological order.

   For related code, see EulerCycle.java and HamCycle.java

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

import java.util.*;

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

import org.jgrapht.alg.cycle.*;
import org.jgrapht.traverse.*;


public class DetectCycles
{

  public static void main(String[] args)
  {
    System.out.println("\nGraph with cycles");
    reportCycles(true);

    System.out.println("\nGraph without cycles");
    reportCycles(false);
  } /* main */


  private static void reportCycles(boolean createCycles)
  {
    Graph<String, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);
    g.addVertex("a");
    g.addVertex("b");
    g.addVertex("c");
    g.addVertex("d");
    g.addVertex("e");

    g.addEdge("b", "a");
    g.addEdge("c", "b");
    if (createCycles)
      g.addEdge("a", "c");

    g.addEdge("e", "d");
    if (createCycles)
      g.addEdge("d", "e");

    JGTUtils.displayAsDOT("Has cycles: " + createCycles, g);

    // Check for cycles
    CycleDetector<String, DefaultEdge> cycleDetector = new CycleDetector<>(g);
    if (cycleDetector.detectCycles()) {
      System.out.println("Cycles detected");

      // Get all vertices involved in the cycles
      Set<String> cycleVerts = cycleDetector.findCycles();

      // find disjoint cycles
      while (!cycleVerts.isEmpty()) {
        System.out.print(" Cycle:");

        // Get a vertex involved in a vertCyc
        Iterator<String> iter = cycleVerts.iterator();
        String vertCyc = iter.next();

        // Get all vertices involved with this vertex
        Set<String> subCycle = cycleDetector.findCyclesContainingVertex(vertCyc);
        for (String v : subCycle) {
          System.out.print("  " + v);
          // Remove vertex so that this cycle is not encountered again
          cycleVerts.remove(v);
        }
        System.out.println();
      }
    }
    else {      // output vertices topologically ordered
      System.out.println("No cycles detected");
      TopologicalOrderIterator<String, DefaultEdge> oIter = 
                              new TopologicalOrderIterator<>(g);
      System.out.print(" Topological Ordering:");
      while (oIter.hasNext())
        System.out.print("  " + oIter.next());
      System.out.println();
    }
  } /* reportCycles */

}  // end of DetectCycles class