Package edu.cmu.tetrad.graph

Class Dag

java.lang.Object
edu.cmu.tetrad.graph.Dag
All Implemented Interfaces:
Graph, TetradSerializable, Serializable
public final class Dag extends Object implements Graph
Represents a directed acyclic graph--that is, a graph containing only directed edges, with no cycles. Variables are permitted to be either measured or latent, with at most one edge per node pair, and no edges to self.
Version:
$Id: $Id
Author:
josephramsey
See Also:

  • Constructor Details

    • Dag

      public Dag()
      Constructs a new directed acyclic graph (DAG).

    • Dag

      public Dag(List<Node> nodes)

      Constructor for Dag.

      Parameters:
      nodes - a List object

    • Dag

      public Dag(Graph graph) throws IllegalArgumentException
      Constructs a new directed acyclic graph from the given graph object.
      Parameters:
      graph - the graph to base the new DAG on.
      Throws:
      IllegalArgumentException - if the given graph cannot for some reason be converted into a DAG.

  • Method Details

    • serializableInstance

      public static Dag serializableInstance()
      Generates a simple exemplar of this class to test serialization.
      Returns:
      a Dag object

    • addBidirectedEdge

      public boolean addBidirectedEdge(Node node1, Node node2)
      Adds a bidirectional edge between two nodes to the graph.
      Specified by:
      addBidirectedEdge in interface Graph
      Parameters:
      node1 - the first node to connect
      node2 - the second node to connect
      Returns:
      true if the edge was successfully added, false otherwise

    • addDirectedEdge

      public boolean addDirectedEdge(Node node1, Node node2)
      Adds a directed edge between two nodes.
      Specified by:
      addDirectedEdge in interface Graph
      Parameters:
      node1 - the first node to be connected (source node)
      node2 - the second node to be connected (target node)
      Returns:
      true if the directed edge was successfully added, false otherwise

    • addUndirectedEdge

      public boolean addUndirectedEdge(Node node1, Node node2)
      Adds an undirected edge between two nodes.
      Specified by:
      addUndirectedEdge in interface Graph
      Parameters:
      node1 - The first node involved in the edge.
      node2 - The second node involved in the edge.
      Returns:
      True if the edge was successfully added, false otherwise.
      Throws:
      UnsupportedOperationException - if the operation is disallowed for a Directed Acyclic Graph (DAG).

    • addNondirectedEdge

      public boolean addNondirectedEdge(Node node1, Node node2)
      Adds a nondirected edge between two nodes in the graph.
      Specified by:
      addNondirectedEdge in interface Graph
      Parameters:
      node1 - The first node to connect.
      node2 - The second node to connect.
      Returns:
      Returns true if the nondirected edge was added successfully.
      Throws:
      UnsupportedOperationException - Thrown if the graph is a directed acyclic graph (DAG).

    • addPartiallyOrientedEdge

      public boolean addPartiallyOrientedEdge(Node node1, Node node2)
      Adds a partially oriented edge between two nodes.
      Specified by:
      addPartiallyOrientedEdge in interface Graph
      Parameters:
      node1 - The first node involved in the edge. Must be a Node object.
      node2 - The second node involved in the edge. Must be a Node object.
      Returns:
      True if the edge was added successfully, false otherwise.
      Throws:
      UnsupportedOperationException - If the graph is a Directed Acyclic Graph (DAG), this operation is not allowed.

    • addEdge

      public boolean addEdge(Edge edge)
      Adds a directed edge to the DAG (Directed Acyclic Graph).
      Specified by:
      addEdge in interface Graph
      Parameters:
      edge - The Edge object to be added.
      Returns:
      Returns true if the edge was successfully added to the DAG, false otherwise.
      Throws:
      IllegalArgumentException - if the given edge is not a directed edge.
      IllegalArgumentException - if adding the edge would create a cycle in the DAG.

    • addNode

      public boolean addNode(Node node)
      Adds a node to the graph.
      Specified by:
      addNode in interface Graph
      Parameters:
      node - - The node to be added to the graph.
      Returns:
      true if the node was successfully added to the graph, false otherwise.

    • addPropertyChangeListener

      public void addPropertyChangeListener(PropertyChangeListener e)
      Adds a PropertyChangeListener to this object.
      Specified by:
      addPropertyChangeListener in interface Graph
      Parameters:
      e - the PropertyChangeListener to be added

    • clear

      public void clear()

      clear.

      Specified by:
      clear in interface Graph

    • containsEdge

      public boolean containsEdge(Edge edge)
      Checks if the graph contains the specified edge.
      Specified by:
      containsEdge in interface Graph
      Parameters:
      edge - the edge to be checked.
      Returns:
      true if the graph contains the edge, false otherwise.

    • containsNode

      public boolean containsNode(Node node)
      Checks if the specified node is contained in the graph.
      Specified by:
      containsNode in interface Graph
      Parameters:
      node - the node to check if contained in the graph
      Returns:
      true if the node is contained in the graph, false otherwise

    • equals

      public boolean equals(Object o)
      Compares this graph with the specified object for equality.
      Specified by:
      equals in interface Graph
      Overrides:
      equals in class Object
      Parameters:
      o - the object to be compared with this graph
      Returns:
      true if the specified object is equal to this graph, false otherwise

    • fullyConnect

      public void fullyConnect(Endpoint endpoint)
      This method fully connects a Directed Acyclic Graph (DAG) with a single endpoint type.
      Specified by:
      fullyConnect in interface Graph
      Parameters:
      endpoint - the endpoint to be fully connected
      Throws:
      UnsupportedOperationException - if the DAG has a single endpoint type

    • reorientAllWith

      public void reorientAllWith(Endpoint endpoint)
      Reorients all edges in a directed acyclic graph (DAG) with a single specified endpoint type.
      Specified by:
      reorientAllWith in interface Graph
      Parameters:
      endpoint - the endpoint type to reorient the edges with. It should be a valid Endpoint object.
      Throws:
      UnsupportedOperationException - if the DAG does not have a single endpoint type, i.e., it is not a DAG.

    • getAdjacentNodes

      public List<Node> getAdjacentNodes(Node node)
      Retrieves the adjacent nodes of a given node in the graph.
      Specified by:
      getAdjacentNodes in interface Graph
      Parameters:
      node - The node for which to retrieve the adjacent nodes.
      Returns:
      A list of adjacent nodes to the given node.

    • getChildren

      public List<Node> getChildren(Node node)
      Returns a list of children nodes for the given node.
      Specified by:
      getChildren in interface Graph
      Parameters:
      node - The node for which to retrieve the children.
      Returns:
      A list of children nodes.

    • getDegree

      public int getDegree()

      getDegree.

      Specified by:
      getDegree in interface Graph
      Returns:
      a int

    • getEdge

      public Edge getEdge(Node node1, Node node2)
      Retrieves the edge between two given nodes in the graph.
      Specified by:
      getEdge in interface Graph
      Parameters:
      node1 - The first node Node in the edge.
      node2 - The second node Node in the edge.
      Returns:
      The Edge between the given nodes.

    • getDirectedEdge

      public Edge getDirectedEdge(Node node1, Node node2)
      Retrieves the directed edge between two nodes in the graph.
      Specified by:
      getDirectedEdge in interface Graph
      Parameters:
      node1 - The first node.
      node2 - The second node.
      Returns:
      The directed edge between the two nodes, or null if there is no such edge.

    • getEdges

      public List<Edge> getEdges(Node node)
      Returns a list of edges connected to the given node.
      Specified by:
      getEdges in interface Graph
      Parameters:
      node - a Node object representing the node
      Returns:
      a list of Edge objects connected to the node

    • getEdges

      public List<Edge> getEdges(Node node1, Node node2)
      Returns a list of edges between two nodes.
      Specified by:
      getEdges in interface Graph
      Parameters:
      node1 - the first node
      node2 - the second node
      Returns:
      a list of edges between the two nodes

    • getEdges

      public Set<Edge> getEdges()

      getEdges.

      Specified by:
      getEdges in interface Graph
      Returns:
      a Set object

    • getEndpoint

      public Endpoint getEndpoint(Node node1, Node node2)
      Gets the endpoint between two nodes in the graph.
      Specified by:
      getEndpoint in interface Graph
      Parameters:
      node1 - the first node
      node2 - the second node
      Returns:
      the endpoint between the two nodes

    • getIndegree

      public int getIndegree(Node node)
      Returns the indegree of the given node in the graph.
      Specified by:
      getIndegree in interface Graph
      Parameters:
      node - the node whose indegree is to be determined
      Returns:
      the indegree of the given node

    • getDegree

      public int getDegree(Node node)
      Returns the degree of a given Node in the graph.
      Specified by:
      getDegree in interface Graph
      Parameters:
      node - a Node object representing the node
      Returns:
      an integer representing the degree of the node

    • getNode

      public Node getNode(String name)
      Retrieves a node from the graph by its name.
      Specified by:
      getNode in interface Graph
      Parameters:
      name - the name of the node to be retrieved
      Returns:
      the node object, or null if not found

    • getNodes

      public List<Node> getNodes()

      getNodes.

      Specified by:
      getNodes in interface Graph
      Returns:
      a List object

    • setNodes

      public void setNodes(List<Node> nodes)
      Sets the list of nodes in the graph.
      Specified by:
      setNodes in interface Graph
      Parameters:
      nodes - a list of nodes to be set in the graph. Must not be null.

    • getNodeNames

      public List<String> getNodeNames()

      getNodeNames.

      Specified by:
      getNodeNames in interface Graph
      Returns:
      a List object

    • getNumEdges

      public int getNumEdges()

      getNumEdges.

      Specified by:
      getNumEdges in interface Graph
      Returns:
      a int

    • getNumEdges

      public int getNumEdges(Node node)
      Returns the number of edges connected to the specified node.
      Specified by:
      getNumEdges in interface Graph
      Parameters:
      node - a Node object representing the node of interest
      Returns:
      the number of edges connected to the specified node

    • getNumNodes

      public int getNumNodes()

      getNumNodes.

      Specified by:
      getNumNodes in interface Graph
      Returns:
      a int

    • getOutdegree

      public int getOutdegree(Node node)
      Returns the outdegree of a given node.
      Specified by:
      getOutdegree in interface Graph
      Parameters:
      node - a Node object representing the node whose outdegree is to be retrieved
      Returns:
      an integer value representing the outdegree of the node

    • getParents

      public List<Node> getParents(Node node)
      Retrieves the parents of a given Node in the graph.
      Specified by:
      getParents in interface Graph
      Parameters:
      node - The Node for which to retrieve the parents.
      Returns:
      A List of Nodes representing the parents.

    • isAdjacentTo

      public boolean isAdjacentTo(Node node1, Node node2)
      Checks if two nodes are adjacent in the graph.
      Specified by:
      isAdjacentTo in interface Graph
      Parameters:
      node1 - The first node to check adjacency for. (NonNull)
      node2 - The second node to check adjacency for. (NonNull)
      Returns:
      true if the nodes are adjacent, false otherwise.

    • isChildOf

      public boolean isChildOf(Node node1, Node node2)

      isChildOf.

      Specified by:
      isChildOf in interface Graph
      Parameters:
      node1 - a Node object
      node2 - a Node object
      Returns:
      true iff node1 is a child of node2 in the graph.

    • isParentOf

      public boolean isParentOf(Node node1, Node node2)
      Determines whether node1 is a parent of node2.
      Specified by:
      isParentOf in interface Graph
      Parameters:
      node1 - a Node object
      node2 - a Node object
      Returns:
      a boolean

    • isDefNoncollider

      public boolean isDefNoncollider(Node node1, Node node2, Node node3)
      Added by ekorber, 2004/6/9.
      Specified by:
      isDefNoncollider in interface Graph
      Parameters:
      node1 - a Node object
      node2 - a Node object
      node3 - a Node object
      Returns:
      true if node 2 is a definite noncollider between 1 and 3

    • isDefCollider

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

    • isExogenous

      public boolean isExogenous(Node node)

      isExogenous.

      Specified by:
      isExogenous in interface Graph
      Parameters:
      node - a Node object
      Returns:
      true iff the given node is exogenous in the graph.

    • getNodesInTo

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

    • getNodesOutTo

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

    • removeEdge

      public boolean removeEdge(Edge edge)
      Removes the given edge from the graph.
      Specified by:
      removeEdge in interface Graph
      Parameters:
      edge - a Edge object
      Returns:
      true if the edge was removed, false if not.

    • removeEdge

      public boolean removeEdge(Node node1, Node node2)
      Removes the edge connecting the two given nodes, provided there is exactly one such edge.
      Specified by:
      removeEdge in interface Graph
      Parameters:
      node1 - a Node object
      node2 - a Node object
      Returns:
      a boolean

    • removeEdges

      public boolean removeEdges(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.
      Specified by:
      removeEdges in interface Graph
      Parameters:
      node1 - a Node object
      node2 - a Node object
      Returns:
      true if edges were removed, false if not.

    • removeEdges

      public boolean removeEdges(Collection<Edge> edges)
      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.
      Specified by:
      removeEdges in interface Graph
      Parameters:
      edges - a Collection object
      Returns:
      true if edges were added, false if not.

    • removeNode

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

    • removeNodes

      public boolean removeNodes(List<Node> nodes)
      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.
      Specified by:
      removeNodes in interface Graph
      Parameters:
      nodes - a List object
      Returns:
      true if nodes were added, false if not.

    • setEndpoint

      public boolean setEndpoint(Node from, Node to, Endpoint endPoint)
      Sets the endpoint type at the 'to' end of the edge from 'from' to 'to' to the given endpoint. Note: NOT CONSTRAINT SAFE
      Specified by:
      setEndpoint in interface Graph
      Parameters:
      from - a Node object
      to - a Node object
      endPoint - a Endpoint object
      Returns:
      a boolean

    • subgraph

      public Graph subgraph(List<Node> nodes)
      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
      Parameters:
      nodes - a List object
      Returns:
      a Graph object

    • toString

      public String toString()

      toString.

      Specified by:
      toString in interface Graph
      Overrides:
      toString in class Object
      Returns:
      a String object

    • 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.

    • transferAttributes

      public void transferAttributes(Graph graph) throws IllegalArgumentException

      transferAttributes.

      Specified by:
      transferAttributes in interface Graph
      Parameters:
      graph - a Graph object
      Throws:
      IllegalArgumentException - if any.

    • paths

      public Paths paths()

      paths.

      Specified by:
      paths in interface Graph
      Returns:
      a Paths object

    • isParameterizable

      public boolean isParameterizable(Node node)

      isParameterizable.

      Specified by:
      isParameterizable in interface Graph
      Parameters:
      node - a Node object
      Returns:
      true if the given node is parameterizable.

    • isTimeLagModel

      public boolean isTimeLagModel()

      isTimeLagModel.

      Specified by:
      isTimeLagModel in interface Graph
      Returns:
      a boolean

    • getTimeLagGraph

      public TimeLagGraph getTimeLagGraph()

      getTimeLagGraph.

      Specified by:
      getTimeLagGraph in interface Graph
      Returns:
      a TimeLagGraph object

    • getSepset

      public Set<Node> getSepset(Node n1, Node n2)

      getSepset.

      Specified by:
      getSepset in interface Graph
      Parameters:
      n1 - a Node object
      n2 - a Node object
      Returns:
      a Set object

    • getAllAttributes

      public Map<String,Object> getAllAttributes()

      getAllAttributes.

      Specified by:
      getAllAttributes in interface Graph
      Returns:
      a Map object

    • getAttribute

      public Object getAttribute(String key)

      getAttribute.

      Specified by:
      getAttribute in interface Graph
      Parameters:
      key - a String object
      Returns:
      a Object object

    • removeAttribute

      public void removeAttribute(String key)

      removeAttribute.

      Specified by:
      removeAttribute in interface Graph
      Parameters:
      key - a String object

    • addAttribute

      public void addAttribute(String key, Object value)

      addAttribute.

      Specified by:
      addAttribute in interface Graph
      Parameters:
      key - a String object
      value - a Object object

    • getAmbiguousTriples

      public Set<Triple> getAmbiguousTriples()

      Getter for the field ambiguousTriples.

      Specified by:
      getAmbiguousTriples in interface Graph
      Returns:
      a Set object

    • setAmbiguousTriples

      public void setAmbiguousTriples(Set<Triple> triples)

      setAmbiguousTriples.

      Specified by:
      setAmbiguousTriples in interface Graph
      Parameters:
      triples - a Set object

    • getUnderLines

      public Set<Triple> getUnderLines()

      getUnderLines.

      Specified by:
      getUnderLines in interface Graph
      Returns:
      a Set object

    • getDottedUnderlines

      public Set<Triple> getDottedUnderlines()

      getDottedUnderlines.

      Specified by:
      getDottedUnderlines in interface Graph
      Returns:
      a Set object

    • isAmbiguousTriple

      public boolean isAmbiguousTriple(Node x, Node y, Node z)
      States whether r-s-r is an underline triple or not.

      States whether r-s-r is an underline triple or not.

      Specified by:
      isAmbiguousTriple in interface Graph
      Parameters:
      x - a Node object
      y - a Node object
      z - a Node object
      Returns:
      a boolean

    • isUnderlineTriple

      public boolean isUnderlineTriple(Node x, Node y, Node z)
      States whether r-s-r is an underline triple or not.

      States whether r-s-r is an underline triple or not.

      Specified by:
      isUnderlineTriple in interface Graph
      Parameters:
      x - a Node object
      y - a Node object
      z - a Node object
      Returns:
      a boolean

    • addAmbiguousTriple

      public void addAmbiguousTriple(Node x, Node y, Node z)

      addAmbiguousTriple.

      Specified by:
      addAmbiguousTriple in interface Graph
      Parameters:
      x - a Node object
      y - a Node object
      z - a Node object

    • addUnderlineTriple

      public void addUnderlineTriple(Node x, Node y, Node z)

      addUnderlineTriple.

      Specified by:
      addUnderlineTriple in interface Graph
      Parameters:
      x - a Node object
      y - a Node object
      z - a Node object

    • addDottedUnderlineTriple

      public void addDottedUnderlineTriple(Node x, Node y, Node z)

      addDottedUnderlineTriple.

      Specified by:
      addDottedUnderlineTriple in interface Graph
      Parameters:
      x - a Node object
      y - a Node object
      z - a Node object

    • removeAmbiguousTriple

      public void removeAmbiguousTriple(Node x, Node y, Node z)

      removeAmbiguousTriple.

      Specified by:
      removeAmbiguousTriple in interface Graph
      Parameters:
      x - a Node object
      y - a Node object
      z - a Node object

    • removeUnderlineTriple

      public void removeUnderlineTriple(Node x, Node y, Node z)

      removeUnderlineTriple.

      Specified by:
      removeUnderlineTriple in interface Graph
      Parameters:
      x - a Node object
      y - a Node object
      z - a Node object

    • removeDottedUnderlineTriple

      public void removeDottedUnderlineTriple(Node x, Node y, Node z)

      removeDottedUnderlineTriple.

      Specified by:
      removeDottedUnderlineTriple in interface Graph
      Parameters:
      x - a Node object
      y - a Node object
      z - a Node object

    • setUnderLineTriples

      public void setUnderLineTriples(Set<Triple> triples)

      setUnderLineTriples.

      Specified by:
      setUnderLineTriples in interface Graph
      Parameters:
      triples - a Set object

    • setDottedUnderLineTriples

      public void setDottedUnderLineTriples(Set<Triple> triples)

      setDottedUnderLineTriples.

      Specified by:
      setDottedUnderLineTriples in interface Graph
      Parameters:
      triples - a Set object

    • removeTriplesNotInGraph

      public void removeTriplesNotInGraph()

      removeTriplesNotInGraph.

      Specified by:
      removeTriplesNotInGraph in interface Graph