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.graph;
  
  import edu.cmu.tetrad.util.TetradSerializable;
  
  import java.beans.PropertyChangeListener;
  import java.util.Collection;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  
  /**
   * <p>Implements a graph capable of storing edges of type N1 *-# N2 where * and
   * # are endpoints of type Endpoint.</p> <p>We stipulate by extending
   * TetradSerializable that all graphs implementing this interface are
   * serializable. This is because for Tetrad they must be serializable. (For
   * randomUtil, in order to be able to cancelAll operations, they must be
   * serializable.)</p>
   *
   * @author Joseph Ramsey
   * @see Endpoint
   */
  public interface Graph extends TetradSerializable, TripleClassifier {
      long serialVersionUID = 23L;
  
      /**
       * Adds a bidirected edges <-> to the graph.
       */
      boolean addBidirectedEdge(Node node1, Node node2);
  
      /**
       * Adds a directed edge --> to the graph.
       */
      boolean addDirectedEdge(Node node1, Node node2);
  
      /**
       * Adds an undirected edge --- to the graph.
       */
      boolean addUndirectedEdge(Node node1, Node node2);
  
      /**
       * Adds an nondirected edges o-o to the graph.
       */
      boolean addNondirectedEdge(Node node1, Node node2);
  
      /**
       * Adds a partially oriented edge o-> to the graph.
       */
      boolean addPartiallyOrientedEdge(Node node1, Node node2);
  
      /**
       * Adds the specified edge to the graph, provided it is not already in the
       * graph.
       *
       * @return true if the edge was added, false if not.
       */
      boolean addEdge(Edge edge);
  
      /**
       * Adds a node to the graph. Precondition: The proposed name of the node
       * cannot already be used by any other node in the same graph.
       *
       * @return true if nodes were added, false if not.
       */
      boolean addNode(Node node);
  
      /**
       * Adds a PropertyChangeListener to the graph.
       */
      void addPropertyChangeListener(PropertyChangeListener e);
  
      /**
       * Removes all nodes (and therefore all edges) from the graph.
       */
      void clear();
  
      /**
       * Determines whether this graph contains the given edge.
       *
       * @return true iff the graph contain 'edge'.
       */
      boolean containsEdge(Edge edge);
  
      /**
       * Determines whether this graph contains the given node.
       *
       * @return true iff the graph contains 'node'.
       */
      boolean containsNode(Node node);
  
      /**
       * @return true iff there is a directed cycle in the graph.
       */
      boolean existsDirectedCycle();
  
      /**
       * @return true iff there is a directed path from node1 to node2 in the
       * graph.
       */
      boolean existsDirectedPathFromTo(Node node1, Node node2);
  
      /**
       * @return true iff there is a semi-directed path from node1 to something in
       * nodes2 in the graph
       */
      boolean existsUndirectedPathFromTo(Node node1, Node node2);
  
      /**
       * </p> A semi-directed path from A to B is an undirected path in which no
       * edge has an arrowhead pointing "back" towards A.
       *
       * @return true iff there is a semi-directed path from node1 to something in
       * nodes2 in the graph
       */
      boolean existsSemiDirectedPathFromTo(Node node1, Set<Node> nodes);
  
      /**
       * Determines whether an inducing path exists between node1 and node2, given
       * a set O of observed nodes and a set sem of conditioned nodes.
       *
       * @param node1 the first node.
       * @param node2 the second node.
       * @return true if an inducing path exists, false if not.
       */
      boolean existsInducingPath(Node node1, Node node2);
  
      /**
       * @return true iff a trek exists between two nodes in the graph.  A trek
       * exists if there is a directed path between the two nodes or else, for
       * some third node in the graph, there is a path to each of the two nodes in
       * question.
       */
      boolean existsTrek(Node node1, Node node2);
  
      /**
       * Determines whether this graph is equal to some other graph, in the sense
       * that they contain the same nodes and the sets of edges defined over these
       * nodes in the two graphs are isomorphic typewise. That is, if node A and B
       * exist in both graphs, and if there are, e.g., three edges between A and B
       * in the first graph, two of which are directed edges and one of which is
       * an undirected edge, then in the second graph there must also be two
       * directed edges and one undirected edge between nodes A and B.
       */
      boolean equals(Object o);
  
      /**
       * Removes all edges from the graph and fully connects it using #-# edges,
       * where # is the given endpoint.
       */
      void fullyConnect(Endpoint endpoint);
  
      /**
       * Reorients all edges in the graph with the given endpoint.
       */
      void reorientAllWith(Endpoint endpoint);
  
      /**
       * @return a mutable list of nodes adjacent to the given node.
       */
      List<Node> getAdjacentNodes(Node node);
  
      /**
       * @return a mutable list of ancestors for the given nodes.
       */
      List<Node> getAncestors(List<Node> nodes);
  
      /**
       * @return a mutable list of children for a node.
       */
      List<Node> getChildren(Node node);
  
      /**
       * @return the connectivity of the graph.
       */
      int getConnectivity();
  
      /**
       * @return a mutable list of descendants for the given nodes.
       */
      List<Node> getDescendants(List<Node> nodes);
  
      /**
       * @return the edge connecting node1 and node2, provided a unique such edge
       * exists.
       * @throws UnsupportedOperationException if the graph allows multiple edges
       *                                       between node pairs.
       */
      Edge getEdge(Node node1, Node node2);
  
      /**
       * @return the directed edge from node1 to node2, if there is one.
       * @throws UnsupportedOperationException if the graph allows multiple edges
       *                                       between node pairs.
       */
      Edge getDirectedEdge(Node node1, Node node2);
  
      /**
       * @return the list of edges connected to a particular node. No particular
       * ordering of the edges in the list is guaranteed.
       */
      List<Edge> getEdges(Node node);
  
      /**
       * @return the edges connecting node1 and node2.
       */
      List<Edge> getEdges(Node node1, Node node2);
  
      /**
       * @return the list of edges in the graph.  No particular ordering of the
       * edges in the list is guaranteed.
       */
      Set<Edge> getEdges();
  
      /**
       * @return the endpoint along the edge from node to node2 at the node2 end.
       */
      Endpoint getEndpoint(Node node1, Node node2);
  
      /**
       * @return a matrix of endpoints for the nodes in this graph, with nodes in
       * the same order as getNodes().
       */
      Endpoint[][] getEndpointMatrix();
  
      /**
       * @return the number of arrow endpoints adjacent to a node.
       */
      int getIndegree(Node node);
  
      /**
       * @return the number of arrow endpoints adjacent to a node.
       */
      int getDegree(Node node);
  
      /**
       * @return the node with the given string name.  In case of accidental
       * duplicates, the first node encountered with the given name is returned.
       * In case no node exists with the given name, null is returned.
       */
      Node getNode(String name);
  
      /**
       * @return the list of nodes for the graph.
       */
      List<Node> getNodes();
  
      /**
       * @return the names of the nodes, in the order of <code>getNodes</code>.
       */
      List<String> getNodeNames();
  
      /**
       * @return the number of edges in the (entire) graph.
       */
      int getNumEdges();
  
      /**
       * @return the number of edges in the graph which are connected to a
       * particular node.
       */
      int getNumEdges(Node node);
  
      /**
       * @return the number of nodes in the graph.
       */
      int getNumNodes();
  
      /**
       * @return the number of null endpoints adjacent to an edge.
       */
      int getOutdegree(Node node);
  
      /**
       * @return the list of parents for a node.
       */
      List<Node> getParents(Node node);
  
      /**
       * @return true iff node1 is adjacent to node2 in the graph.
       */
      boolean isAdjacentTo(Node node1, Node node2);
  
      /**
       * Determines whether one node is an ancestor of another.
       */
      boolean isAncestorOf(Node node1, Node node2);
  
      /**
       * added by ekorber, 2004/06/12
       *
       * @return true if node1 is a possible ancestor of node2.
       */
      boolean possibleAncestor(Node node1, Node node2);
  
      /**
       * @return true iff node1 is a child of node2 in the graph.
       */
      boolean isChildOf(Node node1, Node node2);
  
      /**
       * Determines whether node1 is a parent of node2.
       */
      boolean isParentOf(Node node1, Node node2);
  
      /**
       * Determines whether one node is a proper ancestor of another.
       */
      boolean isProperAncestorOf(Node node1, Node node2);
  
      /**
       * Determines whether one node is a proper decendent of another.
       */
      boolean isProperDescendentOf(Node node1, Node node2);
  
      /**
       * @return true iff node1 is a (non-proper) descendant of node2.
       */
      boolean isDescendentOf(Node node1, Node node2);
  
      /**
       * A node Y is a definite nondescendent of a node X just in case there is no
       * semi-directed path from X to Y.
       * <p>
       * added by ekorber, 2004/06/12.
       *
       * @return true if node 2 is a definite nondecendent of node 1
       */
      boolean defNonDescendent(Node node1, Node node2);
  
      /**
       * Added by ekorber, 2004/6/9.
       *
       * @return true if node 2 is a definite noncollider between 1 and 3
       */
      boolean isDefNoncollider(Node node1, Node node2, Node node3);
  
      /**
       * Added by ekorber, 2004/6/9.
       *
       * @return true if node 2 is a definite collider between 1 and 3
       */
      boolean isDefCollider(Node node1, Node node2, Node node3);
  
      /**
       * Determines whether one node is d-connected to another. According to
       * Spirtes, Richardson & Meek, two nodes are d- connected given some
       * conditioning set Z if there is an acyclic undirected path U between them,
       * such that every collider on U is an ancestor of some element in Z and
       * every non-collider on U is not in Z.  Two elements are d-separated just
       * in case they are not d-connected.  A collider is a node which two edges
       * hold in common for which the endpoints leading into the node are both
       * arrow endpoints.
       */
      boolean isDConnectedTo(Node node1, Node node2, List<Node> z);
  
      boolean isPattern();
  
      void setPattern(boolean pattern);
  
      boolean isPag();
  
      void setPag(boolean pag);
  
      /**
       * Determines whether one node is d-separated from another. Two elements are   E
       * d-separated just in case they are not d-connected.
       */
      boolean isDSeparatedFrom(Node node1, Node node2, List<Node> z);
  
      /**
       * Determines if nodes 1 and 2 are possibly d-connected given conditioning
       * set z.  A path U is possibly-d-connecting if every definite collider on U
       * is a possible ancestor of a node in z and every definite non-collider is
       * not in z.
       * <p>
       * added by ekorber, 2004/06/15.
       *
       * @return true iff nodes 1 and 2 are possibly d-connected given z
       */
      boolean possDConnectedTo(Node node1, Node node2, List<Node> z);
  
      /**
       * @return true iff there is a single directed edge from node1 to node2 in
       * the graph.
       */
      boolean isDirectedFromTo(Node node1, Node node2);
  
      /**
       * @return true iff there is a single undirected edge from node1 to node2 in
       * the graph.
       */
      boolean isUndirectedFromTo(Node node1, Node node2);
  
      /**
       * A directed edge A->B is definitely visible if there is a node C not
       * adjacent to B such that C*->A is in the PAG_of_the_true_DAG. Added by ekorber,
       * 2004/06/11.
       *
       * @return true if the given edge is definitely visible (Jiji, pg 25)
       * @throws IllegalArgumentException if the given edge is not a directed edge
       *                                  in the graph
       */
      boolean defVisible(Edge edge);
  
      /**
       * @return true iff the given node is exogenous in the graph.
       */
      boolean isExogenous(Node node);
  
      /**
       * Nodes adjacent to the given node with the given proximal endpoint.
       */
      List<Node> getNodesInTo(Node node, Endpoint n);
  
      /**
       * Nodes adjacent to the given node with the given distal endpoint.
       */
      List<Node> getNodesOutTo(Node node, Endpoint n);
  
      /**
       * Removes the given edge from the graph.
       *
       * @return true if the edge was removed, false if not.
       */
      boolean removeEdge(Edge edge);
  
      /**
       * Removes the edge connecting the two given nodes, provided there is
       * exactly one such edge.
       *
       * @throws UnsupportedOperationException if multiple edges between node
       *                                       pairs are not supported.
       */
      boolean removeEdge(Node node1, Node node2);
  
      /**
       * Removes all edges connecting node A to node B.  In most cases, this will
       * remove at most one edge, but since multiple edges are permitted in some
       * graph implementations, the number will in some cases be greater than
       * one.
       *
       * @return true if edges were removed, false if not.
       */
      boolean removeEdges(Node node1, Node node2);
  
      /**
       * Iterates through the list and removes any permissible edges found.  The
       * order in which edges are added is the order in which they are presented
       * in the iterator.
       *
       * @return true if edges were added, false if not.
       */
      boolean removeEdges(Collection<Edge> edges);
  
      /**
       * Removes a node from the graph.
       *
       * @return true if the node was removed, false if not.
       */
      boolean removeNode(Node node);
  
      /**
       * Iterates through the list and removes any permissible nodes found.  The
       * order in which nodes are removed is the order in which they are presented
       * in the iterator.
       *
       * @return true if nodes were added, false if not.
       */
      boolean removeNodes(List<Node> nodes);
  
      /**
       * Sets the endpoint type at the 'to' end of the edge from 'from' to 'to' to
       * the given endpoint.  Note: NOT CONSTRAINT SAFE
       */
      boolean setEndpoint(Node from, Node to, Endpoint endPoint);
  
      /**
       * Constructs and returns a subgraph consisting of a given subset of the
       * nodes of this graph together with the edges between them.
       */
      Graph subgraph(List<Node> nodes);
  
      /**
       * @return a string representation of the graph.
       */
      String toString();
  
      /**
       * Transfers nodes and edges from one graph to another.  One way this is
       * used is to change graph types.  One constructs a new graph based on the
       * old graph, and this method is called to transfer the nodes and edges of
       * the old graph to the new graph.
       *
       * @param graph the graph from which nodes and edges are to be pilfered.
       * @throws java.lang.IllegalArgumentException This exception is thrown if adding some node.
       */
      void transferNodesAndEdges(Graph graph) throws IllegalArgumentException;
  
      void transferAttributes(Graph graph) throws IllegalArgumentException;
      
      /**
       * @return the list of ambiguous triples associated with this graph. Triples <x, y, z> that no longer
       * lie along a path in the getModel graph are removed.
       */
      Set<Triple> getAmbiguousTriples();
  
      /**
       * @return the set of underlines associated with this graph. This is used currently by ION, DCI, and CCD.
       * It used to be used by FCI, but it not in the getModel form.  Triples <x, y, z> that no longer
       * lie along a path in the getModel graph are removed.
       */
      Set<Triple> getUnderLines();
  
      /**
       * @return the set of dotted underlines associated with this graph. This used to be used by FCI, but it is
       * not used in the getModel form. It is used by CCD.  Triples <x, y, z> that no longer
       * lie along a path in the getModel graph are removed.
       */
      Set<Triple> getDottedUnderlines();
  
      /**
       * @return true iff the triple <x, y, z> is set as ambiguous.  Triples <x, y, z> that no longer
       * lie along a path in the getModel graph are removed.
       */
      boolean isAmbiguousTriple(Node x, Node y, Node z);
  
      /**
       * @return true iff the triple <x, y, z> is set as underlined.  Triples <x, y, z> that no longer
       * lie along a path in the getModel graph are removed.
       */
      boolean isUnderlineTriple(Node x, Node y, Node z);
  
      /**
       * @return true iff the triple <x, y, z> is set as dotted underlined.   Triples <x, y, z> that no longer
       * lie along a path in the getModel graph are removed.
       */
      boolean isDottedUnderlineTriple(Node x, Node y, Node z);
  
      /**
       * Adds the triple <x, y, z> as an ambiguous triple in the graph.
       *
       * @throws IllegalArgumentException if <x, y, z> does not lie along a path in the graph.
       */
      void addAmbiguousTriple(Node x, Node y, Node Z);
  
      /**
       * Adds the triple <x, y, z> as an underline triple in the graph.
       *
       * @throws IllegalArgumentException if <x, y, z> does not lie along a path in the graph.
       */
      void addUnderlineTriple(Node x, Node y, Node Z);
  
      /**
       * Adds the triple <x, y, z> as a dotted underlined triple in the graph.
       *
       * @throws IllegalArgumentException if <x, y, z> does not lie along a path in the graph.
       */
      void addDottedUnderlineTriple(Node x, Node y, Node Z);
  
      /**
       * Removes the triple <x, y, z> from thet set of ambiguous triples.
       */
      void removeAmbiguousTriple(Node x, Node y, Node z);
  
      /**
       * Removes the triple <x, y, z> from the set of underlined triples.
       */
      void removeUnderlineTriple(Node x, Node y, Node z);
  
      /**
       * Removes the triple <x, y, z> from the set of dotted underlined triples.
       */
      void removeDottedUnderlineTriple(Node x, Node y, Node z);
  
      /**
       * Sets the list of ambiguous triples to the triples in the given set.
       *
       * @param triples The new set of ambiguous triples. This replaces the old list.
       * @throws IllegalArgumentException if any triple <x, y, z> in <code>triples</code> does not lie along a path in the graph.
       */
      void setAmbiguousTriples(Set<Triple> triples);
  
      /**
       * Sets the list of underlined triples to the triples in the given set.
       *
       * @param triples The new list of ambiguous triples. This replaces the old list.
       * @throws IllegalArgumentException if any triple <x, y, z> in <code>triples</code> does not lie along a path in the graph.
       */
      void setUnderLineTriples(Set<Triple> triples);
  
      /**
       * Sets the list of dotted underlined triples to the triples in the given set.
       *
       * @param triples The new list of dotted underlined triples. This replaces the old list.
       * @throws IllegalArgumentException if any triple <x, y, z> in <code>triples</code> does not lie along a path in the graph.
       */
      void setDottedUnderLineTriples(Set<Triple> triples);
  
      /**
       * @return a tier orderering, for acyclic graphs. Undefined for cyclic graphs.
       */
      List<Node> getCausalOrdering();
  
      /**
       * Sets an edge to be highlighted.
       */
      void setHighlighted(Edge edge, boolean highlighted);
  
      /**
       * @return true just in case the given edge is highlighted.
       * @throws IllegalArgumentException if the given edge is not in the graph.
       */
      boolean isHighlighted(Edge edge);
  
      /**
       * @return true if the given node is parameterizable.
       */
      boolean isParameterizable(Node node);
  
      /**
       * @return true if this is a time lag model, in which case getTimeLagGraph() returns the graph.
       */
      boolean isTimeLagModel();
  
      /**
       * @return the underlying time lag model, if there is one; otherwise, returns null.
       */
      TimeLagGraph getTimeLagGraph();
  
  
      void removeTriplesNotInGraph();
  
      List<Node> getSepset(Node n1, Node n2);
  
      void setNodes(List<Node> nodes);
      
      Map<String, Object> getAllAttributes();
      
      Object getAttribute(String key);
      
      void removeAttribute(String key);
      
      void addAttribute(String key, Object value);
  }
  
  
  
  
  
  