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

/* An Euler path in a graph  visits every edge exactly once 
   (allowing for revisiting vertices). An Euler cycle is an 
   Euler path that starts and ends on the same vertex. 
     https://en.wikipedia.org/wiki/Eulerian_path

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

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

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

import org.jgrapht.alg.cycle.*;


public class EulerCycle
{

  public static void main(String[] args)
  {
    String[][] edges = {{"v1", "v2"}, {"v1", "v3"}, {"v1", "v4"},
             {"v1", "v5"}, {"v2", "v3"}, {"v2", "v4"}, {"v2", "v5"}, 
             {"v3", "v4"}, {"v3", "v6"}, {"v4", "v5"}, {"v5", "v6"}};
    Graph<String, DefaultEdge> g = JGTUtils.makeSimple(edges);

    // System.out.println("Graph:\n" + g + "\n");
    System.out.println("Adj List:\n" + JGTUtils.writeAdjList(g));
    System.out.println("No. of edges: " + g.edgeSet().size());
    JGTUtils.displayAsDOT(g);

    // simple test
    System.out.println("\nIs Eulerian? " + GraphTests.isEulerian(g));

    // get the cycle
    HierholzerEulerianCycle<String, DefaultEdge> ec = 
                                        new HierholzerEulerianCycle<>();
    System.out.println("\nIs Eulerian? " + ec.isEulerian(g));
    GraphPath<String, DefaultEdge> path = ec.getEulerianCycle(g);
    System.out.println("Euler cycle: " + path.getVertexList());
    System.out.println("No. of edges in cycle: " + path.getLength());
  } /* main */


}  // end of EulerCycle class