// Planarity.java
// Timofey Chudakov and Contributors, 2021
// Modified by Andrew Davison, ad@coe.psu.ac.th, Jan. 2023

/* Use the BoyerMyrvoldPlanarityInspector class to test if a graph
  is planar (https://en.wikipedia.org/wiki/Planar_graph)

  If the graph is planar, the algorithm provides a graph embedding, 
  which utilizes a clockwise ordering of the edges of the graph. 
  This information is enough to draw its edges do that none 
  of them cross.

  showEmbedding() generates a circular layout for the embedding
  and prints the coordinates of the vertices inside a 10x10 box.
  This layout is *not* used to draw the graph.

  If the graph is not planar, then the algorithm provides a 
  Kuratowski subgraph as a certificate. 

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

import java.util.*;

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

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

import org.jgrapht.alg.drawing.*;
import org.jgrapht.alg.drawing.model.*;


public class Planarity
{

  public static void main(String[] args)
  {
    // uncomment one of the edges arrays...
/*
    String[][] edges = {{"h0", "water"}, {"h0", "gas"}, {"h0", "elec"},
                        {"h1", "water"}, {"h1", "gas"}, {"h1", "elec"},
                        {"h2", "water"}, {"h2", "gas"}, {"h2", "elec"}
                       };   // utilities example; not planar
*/
/*
    String[][] edges = {{"v0", "v1"}, {"v1", "v2"}, {"v2", "v3"},
                        {"v3", "v4"}, {"v0", "v2"}, {"v0", "v3"},
                        {"v3", "v1"}, {"v1", "v4"}};   // is planar
*/

    String[][] edges = {{"v0", "v1"}, {"v1", "v2"},   // is planar
                        {"v2", "v3"}, {"v3", "v4"},
                        {"v4", "v2"}, {"v1", "v5"}, 
                        {"v5", "v6"}, {"v6", "v7"}, 
                        {"v7", "v5"}};


    Graph<String, DefaultEdge> g = JGTUtils.makeSimple(edges);

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


    PlanarityTestingAlgorithm<String, DefaultEdge> pta =
                           new BoyerMyrvoldPlanarityInspector<>(g);
    boolean isPlanar = pta.isPlanar();
    System.out.println("Is planar? " + isPlanar);
    if (isPlanar) {
      PlanarityTestingAlgorithm.Embedding<String, DefaultEdge> embedding =
                                               pta.getEmbedding();
      showEmbedding(embedding);
    }
    else {  // not planar
      Graph<String, DefaultEdge> subdivision = 
                                pta.getKuratowskiSubdivision();
      System.out.println("Has a Kuratowski subdivision? " + 
                      GraphTests.isKuratowskiSubdivision(subdivision));
    }
  } /* main */



  private static void showEmbedding(
         PlanarityTestingAlgorithm.Embedding<String, DefaultEdge> embedding)
  /* print coordinates for a circular rendering of the embedded
     graph, along with the edges leaving each vertex.
  */
  {
    Graph<String, DefaultEdge> ge = embedding.getGraph();

    // generate circular layout to get vertex coordinates
    LayoutAlgorithm2D<String, DefaultEdge> alg =
                              new CircularLayoutAlgorithm2D<>(5); // radius
    MapLayoutModel2D<String> model = 
             new MapLayoutModel2D<>(Box2D.of(0, 0, 10, 10));
    alg.layout(ge, model);

    System.out.println("Embedded circular graph's edge sources:" );
    for (String vertex : ge.vertexSet()) {
      Point2D pt = model.get(vertex);
      System.out.printf("  %s (%.2f, %.2f): ", 
                              vertex, pt.getX(), pt.getY());
      List<DefaultEdge> edges = embedding.getEdgesAround(vertex);
      for (DefaultEdge edge : edges) {
        String sourceVert = ge.getEdgeSource(edge);
        if (sourceVert.equals(vertex))  
          // only print edge when vertex is the source
          System.out.print(sourceVert + "-" + 
                           ge.getEdgeTarget(edge) + "  ");
      }
      System.out.println();
    }
  } /* showEmbedding */


} // end of Planarity class