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

/* A Hamiltonian path in a graph visits each vertex exactly once. 
   A Hamiltonian cycle is a cycle that visits each vertex exactly once. 
      https://en.wikipedia.org/wiki/Hamiltonian_path

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

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

import java.util.*;

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

import org.jgrapht.alg.tour.*;
import org.jgrapht.alg.interfaces.*;

public class HamCycle
{

  public static void main(String[] args)
  {
    // uncomment one of the three edges arrays:

    String[][] edges = {{"a", "b"}, {"a", "c"}, {"b", "c"},
                        {"b", "d"}, {"c", "d"}, {"d", "a"}};  // has HC

/*
    String[][] edges = {{"a", "b"}, {"a", "c"}, {"b", "c"},
                        {"b", "e"}, {"c", "e"}, {"c", "d"},
                        {"d", "e"}, {"e", "f"}, {"d", "f"},
                        {"d", "a"}};   // has HC
*/
/*
    String[][] edges = {{"a", "b"}, {"b", "c"}, {"a", "g"},
                        {"b", "d"}, {"b", "f"}, {"c", "k"},
                        {"g", "d"}, {"d", "e"}, {"e", "f"},
                        {"f", "k"}, {"e", "h"}, {"e", "j"},
                        {"g", "h"}, {"h", "i"}, {"i", "j"},
                        {"j", "k"}, {"h", "l"}, {"j", "l"},
                        {"g", "m"}, {"k", "m"}};   // no HC
*/
    Graph<String, DefaultEdge> g = JGTUtils.makeSimple(edges);
    // System.out.println("Graph:\n" + g + "\n");
    JGTUtils.displayAsDOT(g);

    HamiltonianCycleAlgorithm<String, DefaultEdge> phc = 
                                          new HeldKarpTSP<>();
    try {
      GraphPath<String, DefaultEdge> gp = phc.getTour(g);
      if (gp == null)
        System.out.println("No Hamitonian cycle found");
      else
        System.out.println("Hamiltonian cycle: " + gp);
    }
    catch(IllegalArgumentException e)
    {  System.out.println(e.getMessage());  }

  } /* main */


}  // end of HamCycle class