// BiPartite.java
// Dimitrios Michail, Alexandru Valeanu, 2021
// Modified by Andrew Davison, ad@coe.psu.ac.th, Jan. 2023

/* A bipartite graph has vertices which can be divided into 
   two disjoint and independent sets U and V, where every edge 
   connects a vertex in U to one in V.
      https://en.wikipedia.org/wiki/Bipartite_graph


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

import java.util.*;

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

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


public class Bipartite
{

  public static void main(String args[])
  {
    String[][] edges = {{"A", "B"}, {"A", "D"}, {"C", "B"}, {"C", "D"}};
    Graph<String, DefaultEdge> g = JGTUtils.makeDG(edges);  
                        // directed graph; unweighted

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

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

    // get the two parts
    BipartitePartitioning<String, DefaultEdge> bpp = 
                                new BipartitePartitioning<>(g);

    System.out.println("\nIs bipartite? " + bpp.isBipartite());
    PartitioningAlgorithm.Partitioning<String> part = bpp.getPartitioning();
    System.out.println(part);
    System.out.println("Is this a valid partition? " + 
                                   bpp.isValidPartitioning(part));
  } /* main */

}  // end of BiPartite class