Package edu.cmu.tetrad.graph

Class EdgeListGraph

java.lang.Object
edu.cmu.tetrad.graph.EdgeListGraph
All Implemented Interfaces:
Graph, TripleClassifier, TetradSerializable, Serializable
public class EdgeListGraph extends Object implements Graph, TripleClassifier

Stores a graph a list of lists of edges adjacent to each node in the graph, with an additional list storing all of the edges in the graph. The edges are of the form N1 *-# N2. Multiple edges may be added per node pair to this graph, with the caveat that all edges of the form N1 *-# N2 will be considered equal. For example, if the edge X --> Y is added to the graph, another edge X --> Y may not be added, although an edge Y --> X may be added. Edges from nodes to themselves may also be added.> 0

Author:
josephramsey, Erin Korber additions summer 2004
See Also:

  • Constructor Details

    • EdgeListGraph

      public EdgeListGraph()
      Constructs a new (empty) EdgeListGraph.

    • EdgeListGraph

      public EdgeListGraph(Graph graph) throws IllegalArgumentException
      Constructs a EdgeListGraph using the nodes and edges of the given graph. If this cannot be accomplished successfully, an exception is thrown. Note that any graph constraints from the given graph are forgotten in the new graph.
      Parameters:
      graph - the graph from which nodes and edges are is to be extracted.
      Throws:
      IllegalArgumentException - if a duplicate edge is added.

    • EdgeListGraph

      public EdgeListGraph(EdgeListGraph graph) throws IllegalArgumentException
      Throws:
      IllegalArgumentException

    • EdgeListGraph

      public EdgeListGraph(List<Node> nodes)
      Constructs a new graph, with no edges, using the given variable names.

  • Method Details

    • serializableInstance

      public static EdgeListGraph serializableInstance()
      Generates a simple exemplar of this class to test serialization.

    • addDirectedEdge

      public boolean addDirectedEdge(Node node1, Node node2)
      Adds a directed edge to the graph from node A to node B.
      Specified by:
      addDirectedEdge in interface Graph
      Parameters:
      node1 - the "from" node.
      node2 - the "to" node.

    • addUndirectedEdge

      public boolean addUndirectedEdge(Node node1, Node node2)
      Adds an undirected edge to the graph from node A to node B.
      Specified by:
      addUndirectedEdge in interface Graph
      Parameters:
      node1 - the "from" node.
      node2 - the "to" node.

    • addNondirectedEdge

      public boolean addNondirectedEdge(Node node1, Node node2)
      Adds a nondirected edge to the graph from node A to node B.
      Specified by:
      addNondirectedEdge in interface Graph
      Parameters:
      node1 - the "from" node.
      node2 - the "to" node.

    • addPartiallyOrientedEdge

      public boolean addPartiallyOrientedEdge(Node node1, Node node2)
      Adds a partially oriented edge to the graph from node A to node B.
      Specified by:
      addPartiallyOrientedEdge in interface Graph
      Parameters:
      node1 - the "from" node.
      node2 - the "to" node.

    • addBidirectedEdge

      public boolean addBidirectedEdge(Node node1, Node node2)
      Adds a bidirected edge to the graph from node A to node B.
      Specified by:
      addBidirectedEdge in interface Graph
      Parameters:
      node1 - the "from" node.
      node2 - the "to" node.

    • isDefNoncollider

      public boolean isDefNoncollider(Node node1, Node node2, Node node3)
      IllegalArgument exception raised (by isDirectedFromTo(getEndpoint) or by getEdge) if there are multiple edges between any of the node pairs.
      Specified by:
      isDefNoncollider in interface Graph
      Returns:
      true if node 2 is a definite noncollider between 1 and 3

    • isDefCollider

      public boolean isDefCollider(Node node1, Node node2, Node node3)
      Description copied from interface: Graph
      Added by ekorber, 2004/6/9.
      Specified by:
      isDefCollider in interface Graph
      Returns:
      true if node 2 is a definite collider between 1 and 3

    • getChildren

      public List<Node> getChildren(Node node)
      Specified by:
      getChildren in interface Graph
      Returns:
      the list of children for a node.

    • getDegree

      public int getDegree()
      Specified by:
      getDegree in interface Graph
      Returns:
      the connectivity of the graph.

    • getEdge

      public Edge getEdge(Node node1, Node node2)
      Specified by:
      getEdge in interface Graph
      Returns:
      the edge connecting node1 and node2, provided a unique such edge exists.

    • getDirectedEdge

      public Edge getDirectedEdge(Node node1, Node node2)
      Specified by:
      getDirectedEdge in interface Graph
      Returns:
      the directed edge from node1 to node2, if there is one.

    • getParents

      public List<Node> getParents(Node node)
      Specified by:
      getParents in interface Graph
      Returns:
      the list of parents for a node.

    • getIndegree

      public int getIndegree(Node node)
      Specified by:
      getIndegree in interface Graph
      Returns:
      the number of edges into the given node.

    • getDegree

      public int getDegree(Node node)
      Specified by:
      getDegree in interface Graph
      Returns:
      the number of arrow endpoints adjacent to a node.

    • getOutdegree

      public int getOutdegree(Node node)
      Specified by:
      getOutdegree in interface Graph
      Returns:
      the number of edges out of the given node.

    • isAdjacentTo

      public boolean isAdjacentTo(Node node1, Node node2)
      Determines whether some edge or other exists between two nodes.
      Specified by:
      isAdjacentTo in interface Graph
      Returns:
      true iff node1 is adjacent to node2 in the graph.

    • isChildOf

      public boolean isChildOf(Node node1, Node node2)
      Determines whether one node is a child of another.
      Specified by:
      isChildOf in interface Graph
      Returns:
      true iff node1 is a child of node2 in the graph.

    • getSepset

      public Set<Node> getSepset(Node x, Node y)
      Specified by:
      getSepset in interface Graph

    • isMSeparatedFrom

      public boolean isMSeparatedFrom(Node x, Node y, Set<Node> z)
      Determines whether x and y are d-separated given z.
      Returns:
      True if the nodes in x are all d-separated from nodes in y given nodes in z, false if not.

    • isMSeparatedFrom

      public boolean isMSeparatedFrom(Set<Node> x, Set<Node> y, Set<Node> z)
      Determines whether two nodes are d-separated given z.
      Returns:
      True if the nodes in x are all d-separated from nodes in y given nodes in z, false if not.

    • isMSeparatedFrom

      public boolean isMSeparatedFrom(Set<Node> x, Set<Node> y, Set<Node> z, Map<Node,Set<Node>> ancestors)
      Determines whether two nodes are d-separated given z.
      Parameters:
      ancestors - A map of ancestors for each node.
      Returns:
      True if the nodes are d-separated given z, false if not.

    • isParentOf

      public boolean isParentOf(Node node1, Node node2)
      Determines whether one node is a parent of another.
      Specified by:
      isParentOf in interface Graph
      Parameters:
      node1 - the first node.
      node2 - the second node.
      Returns:
      true if node1 is a parent of node2, false if not.
      See Also:

    • transferNodesAndEdges

      public void transferNodesAndEdges(Graph graph) throws IllegalArgumentException
      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.
      Specified by:
      transferNodesAndEdges in interface Graph
      Parameters:
      graph - the graph from which nodes and edges are to be pilfered.
      Throws:
      IllegalArgumentException - This exception is thrown if adding some node or edge violates one of the basicConstraints of this graph.

    • transferAttributes

      public void transferAttributes(Graph graph) throws IllegalArgumentException
      Specified by:
      transferAttributes in interface Graph
      Throws:
      IllegalArgumentException

    • paths

      public Paths paths()
      Specified by:
      paths in interface Graph

    • isExogenous

      public boolean isExogenous(Node node)
      Determines whether a node in a graph is exogenous.
      Specified by:
      isExogenous in interface Graph
      Returns:
      true iff the given node is exogenous in the graph.

    • getAdjacentNodes

      public List<Node> getAdjacentNodes(Node node)
      Specified by:
      getAdjacentNodes in interface Graph
      Returns:
      the set of nodes adjacent to the given node. If there are multiple edges between X and Y, Y will show up twice in the list of adjacencies for X, for optimality; simply create a list an and array from these to eliminate the duplication.

    • removeEdge

      public boolean removeEdge(Node node1, Node node2)
      Removes the edge connecting the two given nodes.
      Specified by:
      removeEdge in interface Graph

    • getEndpoint

      public Endpoint getEndpoint(Node node1, Node node2)
      Specified by:
      getEndpoint in interface Graph
      Returns:
      the endpoint along the edge from node to node2 at the node2 end.

    • setEndpoint

      public boolean setEndpoint(Node from, Node to, Endpoint endPoint) throws IllegalArgumentException
      If there is currently an edge from node1 to node2, sets the endpoint at node2 to the given endpoint; if there is no such edge, adds an edge --# where # is the given endpoint. Setting an endpoint to null, provided there is exactly one edge connecting the given nodes, removes the edge. (If there is more than one edge, an exception is thrown.)
      Specified by:
      setEndpoint in interface Graph
      Throws:
      IllegalArgumentException - if the edge with the revised endpoint cannot be added to the graph.

    • getNodesInTo

      public List<Node> getNodesInTo(Node node, Endpoint endpoint)
      Nodes adjacent to the given node with the given proximal endpoint.
      Specified by:
      getNodesInTo in interface Graph

    • getNodesOutTo

      public List<Node> getNodesOutTo(Node node, Endpoint endpoint)
      Nodes adjacent to the given node with the given distal endpoint.
      Specified by:
      getNodesOutTo in interface Graph

    • addEdge

      public boolean addEdge(Edge edge)
      Adds an edge to the graph.
      Specified by:
      addEdge in interface Graph
      Parameters:
      edge - the edge to be added
      Returns:
      true if the edge was added, false if not.

    • addNode

      public boolean addNode(Node node)
      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.
      Specified by:
      addNode in interface Graph
      Parameters:
      node - the node to be added.
      Returns:
      true if the node was added, false if not.

    • getEdges

      public Set<Edge> getEdges()
      Specified by:
      getEdges in interface Graph
      Returns:
      the set of edges in the graph. No particular ordering of the edges in the list is guaranteed.

    • containsEdge

      public boolean containsEdge(Edge edge)
      Determines if the graph contains a particular edge.
      Specified by:
      containsEdge in interface Graph
      Returns:
      true iff the graph contain 'edge'.

    • containsNode

      public boolean containsNode(Node node)
      Determines whether the graph contains a particular node.
      Specified by:
      containsNode in interface Graph
      Returns:
      true iff the graph contains 'node'.

    • getEdges

      public List<Edge> getEdges(Node node)
      Specified by:
      getEdges in interface Graph
      Returns:
      the set of edges connected to a particular node. No particular ordering of the edges in the list is guaranteed.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object o)
      Description copied from interface: Graph
      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.
      Specified by:
      equals in interface Graph
      Overrides:
      equals in class Object
      Returns:
      true iff the given object is a graph that is equal to this graph, in the sense that it contains the same nodes and the edges are isomorphic.

    • fullyConnect

      public void fullyConnect(Endpoint endpoint)
      Resets the graph so that it is fully connects it using #-# edges, where # is the given endpoint.
      Specified by:
      fullyConnect in interface Graph

    • reorientAllWith

      public void reorientAllWith(Endpoint endpoint)
      Description copied from interface: Graph
      Reorients all edges in the graph with the given endpoint.
      Specified by:
      reorientAllWith in interface Graph

    • getNode

      public Node getNode(String name)
      Specified by:
      getNode in interface Graph
      Returns:
      the node with the given name, or null if no such node exists.

    • getNumNodes

      public int getNumNodes()
      Specified by:
      getNumNodes in interface Graph
      Returns:
      the number of nodes in the graph.

    • getNumEdges

      public int getNumEdges()
      Specified by:
      getNumEdges in interface Graph
      Returns:
      the number of edges in the (entire) graph.

    • getNumEdges

      public int getNumEdges(Node node)
      Specified by:
      getNumEdges in interface Graph
      Returns:
      the number of edges connected to a particular node in the graph.

    • getNodes

      public List<Node> getNodes()
      Specified by:
      getNodes in interface Graph
      Returns:
      the list of nodes for the graph.

    • setNodes

      public void setNodes(List<Node> nodes)
      Specified by:
      setNodes in interface Graph

    • clear

      public void clear()
      Removes all nodes (and therefore all edges) from the graph.
      Specified by:
      clear in interface Graph

    • removeEdge

      public boolean removeEdge(Edge edge)
      Removes an edge from the graph. (Note: It is dangerous to make a recursive call to this method (as it stands) from a method containing certain types of iterators. The problem is that if one uses an iterator that iterates over the edges of node A or node B, and tries in the process to remove those edges using this method, a concurrent modification exception will be thrown.)
      Specified by:
      removeEdge in interface Graph
      Parameters:
      edge - the edge to remove.
      Returns:
      true if the edge was removed, false if not.

    • removeEdges

      public boolean removeEdges(Collection<Edge> edges)
      Removes any relevant edge objects found in this collection. G
      Specified by:
      removeEdges in interface Graph
      Parameters:
      edges - the collection of edges to remove.
      Returns:
      true if any edges in the collection were removed, false if not.

    • removeEdges

      public boolean removeEdges(Node node1, Node node2)
      Removes all edges connecting node A to node B.
      Specified by:
      removeEdges in interface Graph
      Parameters:
      node1 - the first node.,
      node2 - the second node.
      Returns:
      true if edges were removed between A and B, false if not.

    • removeNode

      public boolean removeNode(Node node)
      Removes a node from the graph.
      Specified by:
      removeNode in interface Graph
      Returns:
      true if the node was removed, false if not.

    • removeNodes

      public boolean removeNodes(List<Node> newNodes)
      Removes any relevant node objects found in this collection.
      Specified by:
      removeNodes in interface Graph
      Parameters:
      newNodes - the collection of nodes to remove.
      Returns:
      true if nodes from the collection were removed, false if not.

    • toString

      public String toString()
      Specified by:
      toString in interface Graph
      Overrides:
      toString in class Object
      Returns:
      a string representation of the graph.

    • subgraph

      public Graph subgraph(List<Node> nodes)
      Description copied from interface: Graph
      Constructs and returns a subgraph consisting of a given subset of the nodes of this graph together with the edges between them.
      Specified by:
      subgraph in interface Graph

    • getEdges

      public List<Edge> getEdges(Node node1, Node node2)
      Specified by:
      getEdges in interface Graph
      Returns:
      the edges connecting node1 and node2.

    • getNodeNames

      public List<String> getNodeNames()
      Specified by:
      getNodeNames in interface Graph
      Returns:
      the names of the nodes, in the order of getNodes.

    • getPcs

      protected PropertyChangeSupport getPcs()
      Returns:
      this object.

    • isParameterizable

      public boolean isParameterizable(Node node)
      Specified by:
      isParameterizable in interface Graph
      Returns:
      true if the given node is parameterizable.

    • isTimeLagModel

      public boolean isTimeLagModel()
      Specified by:
      isTimeLagModel in interface Graph
      Returns:
      true if this is a time lag model, in which case getTimeLagGraph() returns the graph.

    • getTimeLagGraph

      public TimeLagGraph getTimeLagGraph()
      Specified by:
      getTimeLagGraph in interface Graph
      Returns:
      the underlying time lag model, if there is one; otherwise, returns null.

    • changeName

      public void changeName(String name, String newName)

    • getAllAttributes

      public Map<String,Object> getAllAttributes()
      Specified by:
      getAllAttributes in interface Graph

    • getAttribute

      public Object getAttribute(String key)
      Specified by:
      getAttribute in interface Graph

    • removeAttribute

      public void removeAttribute(String key)
      Specified by:
      removeAttribute in interface Graph

    • addAttribute

      public void addAttribute(String key, Object value)
      Specified by:
      addAttribute in interface Graph

    • addPropertyChangeListener

      public void addPropertyChangeListener(PropertyChangeListener l)
      Description copied from interface: Graph
      Adds a PropertyChangeListener to the graph.
      Specified by:
      addPropertyChangeListener in interface Graph

    • getAmbiguousTriples

      public Set<Triple> getAmbiguousTriples()
      Specified by:
      getAmbiguousTriples in interface Graph

    • setAmbiguousTriples

      public void setAmbiguousTriples(Set<Triple> triples)
      Specified by:
      setAmbiguousTriples in interface Graph

    • getUnderLines

      public Set<Triple> getUnderLines()
      Specified by:
      getUnderLines in interface Graph

    • getDottedUnderlines

      public Set<Triple> getDottedUnderlines()
      Specified by:
      getDottedUnderlines in interface Graph

    • isAmbiguousTriple

      public boolean isAmbiguousTriple(Node x, Node y, Node z)
      States whether r-s-r is an underline triple or not.
      Specified by:
      isAmbiguousTriple in interface Graph

    • isUnderlineTriple

      public boolean isUnderlineTriple(Node x, Node y, Node z)
      States whether r-s-r is an underline triple or not.
      Specified by:
      isUnderlineTriple in interface Graph

    • addAmbiguousTriple

      public void addAmbiguousTriple(Node x, Node y, Node z)
      Specified by:
      addAmbiguousTriple in interface Graph

    • addUnderlineTriple

      public void addUnderlineTriple(Node x, Node y, Node z)
      Specified by:
      addUnderlineTriple in interface Graph

    • addDottedUnderlineTriple

      public void addDottedUnderlineTriple(Node x, Node y, Node z)
      Specified by:
      addDottedUnderlineTriple in interface Graph

    • removeAmbiguousTriple

      public void removeAmbiguousTriple(Node x, Node y, Node z)
      Specified by:
      removeAmbiguousTriple in interface Graph

    • removeUnderlineTriple

      public void removeUnderlineTriple(Node x, Node y, Node z)
      Specified by:
      removeUnderlineTriple in interface Graph

    • removeDottedUnderlineTriple

      public void removeDottedUnderlineTriple(Node x, Node y, Node z)
      Specified by:
      removeDottedUnderlineTriple in interface Graph

    • setUnderLineTriples

      public void setUnderLineTriples(Set<Triple> triples)
      Specified by:
      setUnderLineTriples in interface Graph

    • setDottedUnderLineTriples

      public void setDottedUnderLineTriples(Set<Triple> triples)
      Specified by:
      setDottedUnderLineTriples in interface Graph

    • removeTriplesNotInGraph

      public void removeTriplesNotInGraph()
      Specified by:
      removeTriplesNotInGraph in interface Graph

    • getTriplesClassificationTypes

      public List<String> getTriplesClassificationTypes()
      Specified by:
      getTriplesClassificationTypes in interface TripleClassifier
      Returns:
      the names of the triple classifications. Coordinates with getTriplesList

    • getTriplesLists

      public List<List<Triple>> getTriplesLists(Node node)
      Specified by:
      getTriplesLists in interface TripleClassifier
      Returns:
      the list of triples corresponding to getTripleClassificationNames for the given node.