code: ///////////////////////////////////////////////////////////////////////////////
  // For information as to what this class does, see the Javadoc, below.       //
  // Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006,       //
  // 2007, 2008, 2009, 2010, 2014, 2015 by Peter Spirtes, Richard Scheines, Joseph   //
  // Ramsey, and Clark Glymour.                                                //
  //                                                                           //
  // This program is free software; you can redistribute it and/or modify      //
  // it under the terms of the GNU General Public License as published by      //
  // the Free Software Foundation; either version 2 of the License, or         //
  // (at your option) any later version.                                       //
  //                                                                           //
  // This program is distributed in the hope that it will be useful,           //
  // but WITHOUT ANY WARRANTY; without even the implied warranty of            //
  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             //
  // GNU General Public License for more details.                              //
  //                                                                           //
  // You should have received a copy of the GNU General Public License         //
  // along with this program; if not, write to the Free Software               //
  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA //
  ///////////////////////////////////////////////////////////////////////////////
  
  package edu.cmu.tetrad.search;
  
  import edu.cmu.tetrad.graph.Graph;
  import edu.cmu.tetrad.graph.GraphUtils;
  import edu.cmu.tetrad.graph.Node;
  import edu.cmu.tetrad.util.ChoiceGenerator;
  
  import java.text.DecimalFormat;
  import java.text.NumberFormat;
  import java.util.*;
  
  // EXPERIMENTAL!!
  
  /**
   * A clean-up of Ricardo's IntSextad-based purify.
   *
   * @author Joe Ramsey
   */
  public class PurifySextadBased {
      private boolean outputMessage = true;
      private DeltaSextadTest sextadTest;
  
      private List<Integer> nodes;
      private Graph mim;
      private double alpha = 0.05;
  
      public PurifySextadBased(DeltaSextadTest sextadTest, double alpha) {
          this.sextadTest = sextadTest;
  
          this.nodes = new ArrayList<>();
  
          for (int i = 0; i < sextadTest.getVariables().size(); i++) {
              this.nodes.add(i);
          }
          this.alpha = alpha;
      }
  
      public List<List<Integer>> purify(List<List<Integer>> clustering) {
  
          // The input nodes may not be object identical to the ones from the IntSextad test, so we map them over then
          // back by their names.
          for (List<Integer> cluster : clustering) {
              clustering.add(cluster);
          }
  
          if (clustering.isEmpty()) {
              throw new NullPointerException("Clusters not specified.");
          }
  
          List<List<Integer>> result = combinedSearch(clustering);
          List<List<Integer>> convertedResult = new ArrayList<>();
  
          for (List<Integer> cluster : result) {
              convertedResult.add(cluster);
          }
  
          System.out.println(convertedResult);
  
          return convertedResult;
      }
  
      public void setTrueGraph(Graph mim) {
          this.mim = mim;
      }
  
      private List<List<Integer>> combinedSearch(List<List<Integer>> clustering) {
          Set<Integer> eliminated = new HashSet<>();
  
          Set<IntSextad> allImpurities = null;
          double cutoff = alpha;
          int count = 0;
  
          for (List<Integer> cluster : clustering) {
              System.out.println("Within cluster: " + ++count);
              Set<IntSextad> impurities = listSextads(cluster, eliminated, cutoff);
  
              if (impurities != null) {
                  if (allImpurities == null) {
                      allImpurities = new HashSet<>();
                  }
                  allImpurities.addAll(impurities);
              }
          }
  
          Set<IntSextad> impurities = listCrossConstructSextads(clustering, eliminated, cutoff);
  
          if (impurities != null) {
              if (allImpurities == null) {
                  allImpurities = new HashSet<>();
              }
              allImpurities.addAll(impurities);
          }
  
          if (allImpurities == null) {
              return new ArrayList<>();
          }
  
          NumberFormat nf = new DecimalFormat("0.####E00");
  
          while (true) {
              int max = 0;
              Integer maxNode = null;
              Map<Integer, Set<IntSextad>> impuritiesPerNode = getImpuritiesPerNode(allImpurities, eliminated);
  
              for (Integer node : nodes) {
                  if (impuritiesPerNode.get(node).size() > max) {
                      max = impuritiesPerNode.get(node).size();
                      maxNode = node;
                  }
              }
  
              if (max == 0) break;
  
              double minP = Double.POSITIVE_INFINITY;
              double maxP = Double.NEGATIVE_INFINITY;
  
              for (IntSextad IntSextad : impuritiesPerNode.get(maxNode)) {
                  double pValue = sextadTest.getPValue(IntSextad);
  
                  if (pValue < minP) {
                      minP = pValue;
                  }
  
                  if (pValue > maxP) {
                      maxP = pValue;
                  }
              }
  
              impuritiesPerNode.remove(maxNode);
              eliminated.add(maxNode);
              System.out.println("Eliminated " + maxNode + " impurities = " + max +
                      "q = " + nf.format(minP) + " maxP = " + nf.format(maxP));
          }
  
          return buildSolution(clustering, eliminated);
      }
  
      private Map<Integer, Set<IntSextad>> getImpuritiesPerNode(Set<IntSextad> allImpurities, Set<Integer> _eliminated) {
          Map<Integer, Set<IntSextad>> impuritiesPerNode = new HashMap<>();
  
          for (Integer node : nodes) {
              impuritiesPerNode.put(node, new HashSet<IntSextad>());
          }
  
          for (IntSextad IntSextad : allImpurities) {
              if (_eliminated.contains(IntSextad.getI())) {
                  continue;
              }
  
              if (_eliminated.contains(IntSextad.getJ())) {
                  continue;
              }
  
              if (_eliminated.contains(IntSextad.getK())) {
                  continue;
              }
  
              if (_eliminated.contains(IntSextad.getL())) {
                  continue;
              }
  
              if (_eliminated.contains(IntSextad.getM())) {
                  continue;
              }
  
              if (_eliminated.contains(IntSextad.getN())) {
                  continue;
              }
  
              impuritiesPerNode.get(IntSextad.getI()).add(IntSextad);
              impuritiesPerNode.get(IntSextad.getJ()).add(IntSextad);
              impuritiesPerNode.get(IntSextad.getK()).add(IntSextad);
              impuritiesPerNode.get(IntSextad.getL()).add(IntSextad);
              impuritiesPerNode.get(IntSextad.getM()).add(IntSextad);
              impuritiesPerNode.get(IntSextad.getN()).add(IntSextad);
          }
          return impuritiesPerNode;
      }
  
      private Set<IntSextad> listCrossConstructSextads(List<List<Integer>> clustering, Set<Integer> eliminated, double cutoff) {
          Set<IntSextad> allSextads = new HashSet<>();
          boolean countable = false;
  
          for (int p1 = 0; p1 < clustering.size(); p1++) {
              for (int p2 = p1 + 1; p2 < clustering.size(); p2++) {
                  List<Integer> cluster1 = clustering.get(p1);
                  List<Integer> cluster2 = clustering.get(p2);
  
                  if (cluster1.size() >= 5 && cluster2.size() >= 1) {
                      ChoiceGenerator gen1 = new ChoiceGenerator(cluster1.size(), 5);
                      int[] choice1;
  
                      while ((choice1 = gen1.next()) != null) {
                          ChoiceGenerator gen2 = new ChoiceGenerator(cluster2.size(), 1);
                          int[] choice2;
  
                          while ((choice2 = gen2.next()) != null) {
                              List<Integer> crossCluster = new ArrayList<>();
                              for (int i : choice1) crossCluster.add(cluster1.get(i));
                              for (int i : choice2) crossCluster.add(cluster2.get(i));
                              Set<IntSextad> Sextads = listSextads(crossCluster, eliminated, cutoff);
  
                              if (Sextads != null) {
                                  countable = true;
                                  allSextads.addAll(Sextads);
                              }
                          }
                      }
                  }
  
                  if (cluster2.size() >= 5 && cluster1.size() >= 1) {
                      ChoiceGenerator gen1 = new ChoiceGenerator(cluster2.size(), 5);
                      int[] choice1;
  
                      while ((choice1 = gen1.next()) != null) {
                          ChoiceGenerator gen2 = new ChoiceGenerator(cluster1.size(), 1);
                          int[] choice2;
  
                          while ((choice2 = gen2.next()) != null) {
                              List<Integer> crossCluster = new ArrayList<>();
                              for (int i : choice1) crossCluster.add(cluster2.get(i));
                              for (int i : choice2) crossCluster.add(cluster1.get(i));
  
                              Set<IntSextad> Sextads = listSextads(crossCluster, eliminated, cutoff);
  
                              if (Sextads != null) {
                                  countable = true;
                                  allSextads.addAll(Sextads);
                              }
                          }
                      }
                  }
  
  //                if (cluster1.size() >= 2 && cluster2.size() >= 2) {
  //                    ChoiceGenerator gen1 = new ChoiceGenerator(cluster1.size(), 2);
  //                    int[] choice1;
  //
  //                    while ((choice1 = gen1.next()) != null) {
  //                        ChoiceGenerator gen2 = new ChoiceGenerator(cluster2.size(), 2);
  //                        int[] choice2;
  //
  //                        while ((choice2 = gen2.next()) != null) {
  //                            List<Integer> crossCluster = new ArrayList<Integer>();
  //                            for (int i : choice1) crossCluster.add(cluster1.get(i));
  //                            for (int i : choice2) crossCluster.add(cluster2.get(i));
  //
  //                            Set<IntSextad> Sextads = listSextads2By2(crossCluster, eliminated, cutoff);
  //
  //                            if (Sextads != null) {
  //                                countable = true;
  //                                allSextads.addAll(Sextads);
  //                            }
  //                        }
  //                    }
  //                }
              }
          }
  
          return countable ? allSextads : null;
      }
  
  
      private Set<IntSextad> listSextads(List<Integer> cluster, Set<Integer> eliminated, double cutoff) {
          if (cluster.size() < 6) return null;
          cluster = new ArrayList<>(cluster);
          boolean countable = false;
  
          Set<IntSextad> Sextads = new HashSet<>();
          ChoiceGenerator gen = new ChoiceGenerator(cluster.size(), 6);
          int[] choice;
  
          while ((choice = gen.next()) != null) {
              int _i = choice[0];
              int _j = choice[1];
              int _k = choice[2];
              int _l = choice[3];
              int _m = choice[4];
              int _n = choice[5];
  
              int m1 = cluster.get(_i);
              int m2 = cluster.get(_j);
              int m3 = cluster.get(_k);
              int m4 = cluster.get(_l);
              int m5 = cluster.get(_m);
              int m6 = cluster.get(_n);
  
              if (eliminated.contains(m1) || eliminated.contains(m2) || eliminated.contains(m3) || eliminated.contains(m4)
                      || eliminated.contains(m5) || eliminated.contains(m6)) {
                  continue;
              }
  
              countable = true;
              double p1, p2, p3, p4, p5, p6, p7, p8, p9, p10;
  
              IntSextad t1 = new IntSextad(m1, m2, m3, m4, m5, m6);
              IntSextad t2 = new IntSextad(m1, m2, m4, m3, m5, m6);
              IntSextad t3 = new IntSextad(m1, m2, m5, m3, m4, m6);
              IntSextad t4 = new IntSextad(m1, m2, m6, m3, m4, m5);
              IntSextad t5 = new IntSextad(m1, m3, m4, m2, m5, m6);
              IntSextad t6 = new IntSextad(m1, m3, m5, m2, m4, m6);
              IntSextad t7 = new IntSextad(m1, m3, m6, m2, m4, m5);
              IntSextad t8 = new IntSextad(m1, m4, m5, m2, m3, m6);
              IntSextad t9 = new IntSextad(m1, m4, m6, m2, m3, m5);
              IntSextad t10 = new IntSextad(m1, m5, m6, m2, m3, m4);
  
              p1 = sextadTest.getPValue(t1);
              p2 = sextadTest.getPValue(t2);
              p3 = sextadTest.getPValue(t3);
              p4 = sextadTest.getPValue(t4);
              p5 = sextadTest.getPValue(t5);
              p6 = sextadTest.getPValue(t6);
              p7 = sextadTest.getPValue(t7);
              p8 = sextadTest.getPValue(t8);
              p9 = sextadTest.getPValue(t9);
              p10 = sextadTest.getPValue(t10);
  
              if (p1 < cutoff) {
                  Sextads.add(t1);
              }
  
              if (p2 < cutoff) {
                  Sextads.add(t2);
              }
  
              if (p3 < cutoff) {
                  Sextads.add(t3);
              }
  
              if (p4 < cutoff) {
                  Sextads.add(t4);
              }
  
              if (p5 < cutoff) {
                  Sextads.add(t5);
              }
  
              if (p6 < cutoff) {
                  Sextads.add(t6);
              }
  
              if (p7 < cutoff) {
                  Sextads.add(t7);
              }
  
              if (p8 < cutoff) {
                  Sextads.add(t8);
              }
              if (p9 < cutoff) {
                  Sextads.add(t9);
              }
  
              if (p10 < cutoff) {
                  Sextads.add(t10);
              }
  
          }
  
          return countable ? Sextads : null;
      }
  
  //    private Set<IntSextad> listSextads2By2(List<Integer> cluster, Set<Integer> eliminated, double cutoff) {
  //        if (cluster.size() < 4) return null;
  //        cluster = new ArrayList<Integer>(cluster);
  //        Set<IntSextad> Sextads = new HashSet<IntSextad>();
  //
  //        Node ci = cluster.get(0);
  //        Node cj = cluster.get(1);
  //        Node ck = cluster.get(2);
  //        Node cl = cluster.get(3);
  //
  //        if (eliminated.contains(ci) || eliminated.contains(cj) || eliminated.contains(ck) || eliminated.contains(cl)) {
  //            return null;
  //        }
  //
  //        double p3 = SextadTest.SextadPValue(nodes.indexOf(ci), nodes.indexOf(ck), nodes.indexOf(cl), nodes.indexOf(cj));
  ////        double p3 = SextadTest.SextadPValue(nodes.indexOf(ci), nodes.indexOf(cj), nodes.indexOf(cl), nodes.indexOf(ck));
  //
  //        if (p3 < cutoff) {
  //            Sextads.add(new IntSextad(ci, ck, cl, cj, p3));
  ////            Sextads.add(new IntSextad(ci, cj, cl, ck, p3));
  //        }
  //
  //        return Sextads;
  //    }
  
      private List<List<Integer>> buildSolution(List<List<Integer>> clustering, Set<Integer> eliminated) {
          List<List<Integer>> solution = new ArrayList<>();
  
          for (List<Integer> cluster : clustering) {
              List<Integer> _cluster = new ArrayList<>(cluster);
              _cluster.removeAll(eliminated);
              solution.add(_cluster);
          }
  
          return solution;
      }
  }
  
  
  