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.*;
  
  import java.util.*;
  
  
  /**
   * **************************************************************************************
   *
   * @author Trevor Burns
   * <p>
   * GraphChange is a data structure created mainly for use in the ION search algorithm. However, it models a general
   * concept: storage for a variety of seperate changes one could possibly apply to a PAG.
   * <p>
   * By convention, the NodePairs in the orients ArrayList are ordered such that Node1 is the "from" node and Node2 is the
   * "to" node (ie 1 o-> 2)
   */
  public class GraphChange {
      private List<Edge> removes;
      private List<Triple> colliders;
      private List<Triple> nonColliders;
      private List<NodePair> orients;
  
      /**
       * Default constructor, holds no changes.
       */
      public GraphChange() {
          removes = new ArrayList<>();
          colliders = new ArrayList<>();
          nonColliders = new ArrayList<>();
          orients = new ArrayList<>();
      }
  
      /**
       * Copy constructor.
       */
      public GraphChange(GraphChange source) {
          removes = new ArrayList<>(source.removes);
          colliders = new ArrayList<>(source.colliders);
          nonColliders = new ArrayList<>(source.nonColliders);
          orients = new ArrayList<>(source.orients);
      }
  
  
      /**
       * Absorbs all changes from the GraphChange other into the calling GraphChange.
       */
      public void union(GraphChange other) {
          removes.addAll(other.removes);
          colliders.addAll(other.colliders);
          nonColliders.addAll(other.nonColliders);
          orients.addAll(other.orients);
      }
  
  
      /**
       * Consistency check, nonexhaustive, but catches the most blatant inconsistencies.
       */
      public boolean isConsistent(GraphChange other) {
  
          /* checks same triples being marked as colliders and non colliders */
          for (Triple colide : this.colliders)
              if (other.nonColliders.contains(colide))
                  return false;
          for (Triple nonColide : this.nonColliders)
              if (other.colliders.contains(nonColide))
                  return false;
  
          Collection colidePairsOther = makePairs(other.colliders);
          Collection nonColidePairsOther = makePairs(other.nonColliders);
  
          /* checks for overlap between removes and noncolliders */
          for (Edge e : this.removes) {
              NodePair rem = new NodePair(e.getNode1(), e.getNode2());
              if (colidePairsOther.contains(rem) || nonColidePairsOther.contains(rem)
                      || other.orients.contains(rem))
                  return false;
          }
  
          Collection colidePairsThis = makePairs(this.colliders);
          Collection nonColidePairsThis = makePairs(this.nonColliders);
  
          /* checks for overlap between removes and colliders/orients*/
          for (Edge e : other.removes) {
              NodePair rem = new NodePair(e.getNode1(), e.getNode2());
              if (colidePairsThis.contains(rem) || nonColidePairsThis.contains(rem)
                      || this.orients.contains(rem))
                  return false;
          }
  
          return true;
      }
  
  
      /**
       * Outputs a new PAG, a copy of the input excepting the applied changes of this object. Will return null if some
       * change fails (ie an obscure inconsistensy).
       */
      public Graph applyTo(Graph graph) {
          Graph output = new EdgeListGraph(graph);
          output = makeNewEdges(output);
  
          for (Triple t : nonColliders)
              output.addUnderlineTriple(t.getX(), t.getY(), t.getZ());
  
          for (Edge e : removes)
              if (!output.removeEdge(e))
                  return null;
  
          Collection<OrderedNodePair> allOrients = makePairs(colliders);
          allOrients.addAll(pairToOrdered(orients));
  
          for (OrderedNodePair or : allOrients) {
              Node to = or.getSecond();
              Node from = or.getFirst();
  
              if (!output.setEndpoint(from, to, Endpoint.ARROW))
                  return null;
          }
  
          return output;
      }
  
  
      /**
       * Add another remove operation to the GraphChange.
       */
      public void addRemove(Edge removalEdge) {
          removes.add(removalEdge);
      }
  
  
      /**
       * Add another collider operation to the GraphChange.
       */
      public void addCollider(Triple colliderTrip) {
          colliders.add(colliderTrip);
      }
  
  
      /**
       * Add another non-collider operation to the GraphChange.
       */
      public void addNonCollider(Triple nonColliderTrip) {
          nonColliders.add(nonColliderTrip);
      }
  
  
      /**
       * Add another orient operation to the GraphChange.
       */
      public void addOrient(Node from, Node to) {
          orients.add(new NodePair(from, to));
      }
  
  
      /**
       * Contains is defined such that if the internal strucs of this GraphChange all individually contain the elements in
       * the corresponding strucs of GraphChange gc, then this "contains" gc.
       */
      public boolean contains(GraphChange gc) {
          if (!removes.containsAll(gc.removes)) return false;
          if (!colliders.containsAll(gc.colliders)) return false;
          if (!nonColliders.containsAll(gc.nonColliders)) return false;
          if (!orients.containsAll(gc.orients)) return false;
  
          return true;
      }
  
  
      /**
       * Anly outputs ops which have elements, not empty structures.
       */
      public String toString() {
          String ret = "[ ";
  //        ret = "\n" + super.toString();
          if (!removes.isEmpty())
              ret = ret + "\n removes: " + removes.toString();
          if (!colliders.isEmpty())
              ret = ret + "\n colliders: " + colliders.toString();
          if (!nonColliders.isEmpty())
              ret = ret + "\n nonColliders: " + nonColliders.toString();
          if (!orients.isEmpty())
              ret = ret + "\n orient: " + orients.toString();
          ret = ret + " ]";
          return ret;
      }
  
      /**
       * Return colliders
       */
      public List<Triple> getColliders() {
          return colliders;
      }
  
      /**
       * Return noncolliders
       */
      public List<Triple> getNoncolliders() {
          return nonColliders;
      }
  
      /**
       * Return removes
       */
      public List<Edge> getRemoves() {
          return removes;
      }
  
      /**
       * Return orients
       */
      public List<NodePair> getOrients() {
          return orients;
      }
  
  
      /**
       * Equals is defined such that if the internal strucs of this GraphChange all individually equal the corresponding
       * strucs of GraphChange gc, then this "equals" gc
       */
      public boolean equals(Object other) {
          if (!(other instanceof GraphChange))
              return false;
          GraphChange otherGC = (GraphChange) other;
  
          if (!otherGC.removes.equals(this.removes) ||
                  !otherGC.colliders.equals(this.colliders) ||
                  !otherGC.nonColliders.equals(this.nonColliders) ||
                  !otherGC.orients.equals(this.orients))
              return false;
  
          return true;
      }
  
  
      public int hashCode() {
          int hash = 1;
          hash *= 17 * removes.hashCode();
          hash *= 19 * colliders.hashCode();
          hash *= 7 * nonColliders.hashCode();
          hash *= 23 * orients.hashCode();
          return hash;
      }
  
  
      /**
       * ******************************************************************************** /* Private
       * /***********************************************************************************
       * <p>
       * <p>
       * /** creates OrderedNodePairs out of given List. For use in consistent and applyTo
       */
      private Collection<OrderedNodePair> makePairs(List<Triple> input) {
          HashSet<OrderedNodePair> outputPairs = new HashSet<>();
          for (Triple trip : input) {
              Node y = trip.getY();
              outputPairs.add(new OrderedNodePair(trip.getX(), y));
              outputPairs.add(new OrderedNodePair(trip.getZ(), y));
          }
          return outputPairs;
      }
  
      /**
       * Creates a List of OrderedNodePairs from a datastructure of NodePairs.
       */
      private Collection<OrderedNodePair> pairToOrdered(List<NodePair> orig) {
          List<OrderedNodePair> ordered = new ArrayList<>(orig.size());
  
          for (NodePair p : orig) {
              ordered.add(new OrderedNodePair(p.getFirst(), p.getSecond()));
          }
  
          return ordered;
      }
  
      /**
       * Takes a graph and recreates all edges. Used in order to copy a graph, because the copy constructor does not go
       * all the way down through the datastructures to make entirely new objects for everything
       */
      private Graph makeNewEdges(Graph graph) {
          Set<Edge> origEdges = graph.getEdges();
  
          for (Edge e : origEdges) {
              Edge newEdge = new Edge(e.getNode1(), e.getNode2(),
                      e.getEndpoint1(), e.getEndpoint2());
              graph.removeEdge(e);
              graph.addEdge(newEdge);
          }
  
          return graph;
      }
  
  
      /**
       * Almost a direct copy of edu.cmu.tetrad.graph.NodePair. While  NodePairs can be partially tricked into preserving
       * order of nodes, its .equals does not acknowledge said convention, thus the need for OrderedNodePairs on occasion
       */
      private class OrderedNodePair extends NodePair {
  
          public OrderedNodePair(Node first, Node second) {
              super(first, second);
          }
  
          public boolean equals(Object o) {
              if (o == this) {
                  return true;
              }
              if (!(o instanceof NodePair)) {
                  return false;
              }
              NodePair thatPair = (NodePair) o;
              return super.getFirst().equals(thatPair.getFirst())
                      && super.getSecond().equals(thatPair.getSecond());
  
          }
      }
  }
  
  
  
  