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.
      Specified by:
      addBidirectedEdge in interface Graph
      Parameters:
      node1 - the first node to connect (a Node object)
      node2 - the second node to connect (a Node object)
      Returns:
      true if the bidirectional 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 connect (source node)
      node2 - the second node to connect (target node)
      Returns:
      true if the directed edge is 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 to connect (a Node object)
      node2 - the second node to connect (a Node object)
      Returns:
      true if the undirected edge is successfully added, false otherwise

    • 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 (a Node object)
      node2 - the second node to connect (a Node object)
      Returns:
      true if the edge was successfully added, false otherwise

    • 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 to be connected
      node2 - the second node to be connected
      Returns:
      true if the partially oriented edge is added successfully, false otherwise
      Throws:
      UnsupportedOperationException - if the graph is a directed acyclic graph (DAG)

    • addEdge

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

    • addNode

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

    • addPropertyChangeListener

      public void addPropertyChangeListener(PropertyChangeListener e)
      Adds a PropertyChangeListener to the underlying graph 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 given edge is present in the graph.
      Specified by:
      containsEdge in interface Graph
      Parameters:
      edge - the edge to check if present in the graph
      Returns:
      true if the edge is present in the graph, false otherwise

    • containsNode

      public boolean containsNode(Node node)
      Checks if the given Node object is contained in the graph.
      Specified by:
      containsNode in interface Graph
      Parameters:
      node - The Node object to check for containment. Must not be null.
      Returns:
      true if the Node object is contained in the graph, false otherwise.

    • equals

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

    • fullyConnect

      public void fullyConnect(Endpoint endpoint)
      Fully connects the given endpoint.
      Specified by:
      fullyConnect in interface Graph
      Parameters:
      endpoint - The endpoint to fully connect.
      Throws:
      UnsupportedOperationException - If the endpoint is a single endpoint type and cannot be fully connected.

    • reorientAllWith

      public void reorientAllWith(Endpoint endpoint)
      Reorients all edges in a Directed Acyclic Graph (DAG) with a single endpoint type.
      Specified by:
      reorientAllWith in interface Graph
      Parameters:
      endpoint - The type of endpoint to reorient all edges with. Must be an instance of `edu.cmu.tetrad.graph.Endpoint`.
      Throws:
      UnsupportedOperationException - if attempting to reorient all edges in a DAG with a single endpoint type.

    • 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 adjacent nodes
      Returns:
      a List of nodes that are adjacent to the given node

    • getChildren

      public List<Node> getChildren(Node node)
      Retrieves the children of a specified Node in the graph.
      Specified by:
      getChildren in interface Graph
      Parameters:
      node - The Node object whose children are to be retrieved.
      Returns:
      A List of Node objects representing the children of the specified node.

    • 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 nodes in the graph.
      Specified by:
      getEdge in interface Graph
      Parameters:
      node1 - a Node object representing the first node
      node2 - a Node object representing the second node
      Returns:
      the edge between node1 and node2, or null if no such edge exists

    • getDirectedEdge

      public Edge getDirectedEdge(Node node1, Node node2)
      Returns the directed edge between the given nodes, if one exists in the graph.
      Specified by:
      getDirectedEdge in interface Graph
      Parameters:
      node1 - the first Node object
      node2 - the second Node object
      Returns:
      the directed edge between the given nodes, or null if no edge exists

    • getEdges

      public Set<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 the specified nodes in the graph.
      Specified by:
      getEdges in interface Graph
      Parameters:
      node1 - the first node in the edge pair. Must not be null.
      node2 - the second node in the edge pair. Must not be null.
      Returns:
      a list of edges between the specified nodes. Returns an empty list if no edges are found.

    • getEdges

      public Set<Edge> getEdges()

      getEdges.

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

    • getEndpoint

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

    • getIndegree

      public int getIndegree(Node node)
      Returns the indegree of the specified node in the graph.
      Specified by:
      getIndegree in interface Graph
      Parameters:
      node - the node for which to find the indegree
      Returns:
      the indegree of the specified 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 - the node whose degree needs to be calculated
      Returns:
      the degree of the node

    • getNode

      public Node getNode(String name)
      Retrieves the node in the graph with the specified name.
      Specified by:
      getNode in interface Graph
      Parameters:
      name - a String object representing the name of the node
      Returns:
      the Node object found in the graph with the specified name

    • getNodes

      public List<Node> getNodes()

      getNodes.

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

    • setNodes

      public void setNodes(List<Node> nodes)
      Set the nodes of the graph.
      Specified by:
      setNodes in interface Graph
      Parameters:
      nodes - A list of Node objects representing the nodes to be set.

    • 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 - the node for which to retrieve the number of edges
      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 the given node.
      Specified by:
      getOutdegree in interface Graph
      Parameters:
      node - a Node object
      Returns:
      the outdegree of the node

    • getParents

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

    • isAdjacentTo

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

    • isChildOf

      public boolean isChildOf(Node node1, Node node2)
      Checks if the given node1 is a child of node2 in the graph.
      Specified by:
      isChildOf in interface Graph
      Parameters:
      node1 - the first Node object to be checked
      node2 - the second Node object to be checked against
      Returns:
      true if node1 is a child of node2, false otherwise

    • isParentOf

      public boolean isParentOf(Node node1, Node node2)
      Determines if a given node is a parent of another node in the graph.
      Specified by:
      isParentOf in interface Graph
      Parameters:
      node1 - the first node to be compared.
      node2 - the second node to be compared.
      Returns:
      true if node1 is a parent of node2, false otherwise.

    • isDefNoncollider

      public boolean isDefNoncollider(Node node1, Node node2, Node node3)
      Checks if three given nodes form a definite non-collider in a graph.
      Specified by:
      isDefNoncollider in interface Graph
      Parameters:
      node1 - the first node
      node2 - the second node
      node3 - the third node
      Returns:
      true if the three nodes form a definite non-collider, false otherwise

    • isDefCollider

      public boolean isDefCollider(Node node1, Node node2, Node node3)
      Checks if there is a definite collider between three nodes in the graph.
      Specified by:
      isDefCollider in interface Graph
      Parameters:
      node1 - the first node to check
      node2 - the second node to check
      node3 - the third node to check
      Returns:
      true if there is a definite collider, false otherwise

    • isExogenous

      public boolean isExogenous(Node node)
      Checks whether a given node is exogenous.
      Specified by:
      isExogenous in interface Graph
      Parameters:
      node - A Node object representing the node to be checked.
      Returns:
      True if the given node is exogenous, false otherwise.

    • getNodesInTo

      public List<Node> getNodesInTo(Node node, Endpoint n)
      Retrieves a list of nodes in the given graph that have edges pointing into the specified node and endpoint.
      Specified by:
      getNodesInTo in interface Graph
      Parameters:
      node - the node to check for incoming edges
      n - the endpoint to check for incoming edges
      Returns:
      a list of nodes with edges pointing into the specified node and endpoint

    • getNodesOutTo

      public List<Node> getNodesOutTo(Node node, Endpoint n)
      Retrieves a list of nodes that have outgoing edges to a specified node and endpoint.
      Specified by:
      getNodesOutTo in interface Graph
      Parameters:
      node - The node to which the outgoing edges lead.
      n - The endpoint to which the outgoing edges connect to the specified node.
      Returns:
      A list of nodes that have outgoing edges to the specified node and endpoint.

    • removeEdge

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

    • removeEdge

      public boolean removeEdge(Node node1, Node node2)
      Removes the edge between two nodes in the graph.
      Specified by:
      removeEdge in interface Graph
      Parameters:
      node1 - the first node to remove the edge from
      node2 - the second node to remove the edge to
      Returns:
      true if the edge was successfully removed, false otherwise

    • removeEdges

      public boolean removeEdges(Node node1, Node node2)
      Removes an edge between two nodes.
      Specified by:
      removeEdges in interface Graph
      Parameters:
      node1 - the first node
      node2 - the second node
      Returns:
      true if the edge was successfully removed, false otherwise

    • removeEdges

      public boolean removeEdges(Collection<Edge> edges)
      Removes the given edges from the graph.
      Specified by:
      removeEdges in interface Graph
      Parameters:
      edges - a collection of edges to be removed from the graph
      Returns:
      true if all the edges were successfully removed, false otherwise

    • removeNode

      public boolean removeNode(Node node)
      Removes the specified node from the graph.
      Specified by:
      removeNode in interface Graph
      Parameters:
      node - the node to be removed from the graph
      Returns:
      true if the node was successfully removed, false otherwise

    • removeNodes

      public boolean removeNodes(List<Node> nodes)
      Removes the specified nodes from the graph.
      Specified by:
      removeNodes in interface Graph
      Parameters:
      nodes - a List of nodes to remove
      Returns:
      true if the nodes were successfully removed, false otherwise

    • setEndpoint

      public boolean setEndpoint(Node from, Node to, Endpoint endPoint)
      Sets the endpoint of a directed edge between two nodes in a graph.
      Specified by:
      setEndpoint in interface Graph
      Parameters:
      from - the starting node of the edge
      to - the ending node of the edge
      endPoint - the endpoint of the directed edge
      Returns:
      true if the endpoint was successfully set, false otherwise

    • subgraph

      public Graph subgraph(List<Node> nodes)
      Returns a subgraph of the current graph consisting only of the specified nodes.
      Specified by:
      subgraph in interface Graph
      Parameters:
      nodes - a list of nodes to include in the subgraph
      Returns:
      a new Graph object representing the subgraph

    • 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 the given graph to the current graph.
      Specified by:
      transferNodesAndEdges in interface Graph
      Parameters:
      graph - the graph from which nodes and edges are to be pilfered
      Throws:
      IllegalArgumentException - if the graph is null, or if adding a node/edge fails
      NullPointerException - if no graph is provided

    • transferAttributes

      public void transferAttributes(Graph graph) throws IllegalArgumentException
      Transfers attributes from the given graph to the current graph.
      Specified by:
      transferAttributes in interface Graph
      Parameters:
      graph - a Graph object representing the graph from which attributes will be transferred
      Throws:
      IllegalArgumentException - if the graph is null

    • paths

      public Paths paths()

      paths.

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

    • isParameterizable

      public boolean isParameterizable(Node node)
      Checks if the given node is parameterizable.
      Specified by:
      isParameterizable in interface Graph
      Parameters:
      node - the node to be checked for parameterizability
      Returns:
      true if the node is parameterizable, false otherwise

    • 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, IndependenceTest test)
      Returns the sepset between two given nodes in the graph.
      Specified by:
      getSepset in interface Graph
      Parameters:
      n1 - the first node
      n2 - the second node
      test - the independence test to be used
      Returns:
      a set of nodes representing the sepset between n1 and n2

    • getAllAttributes

      public Map<String,Object> getAllAttributes()

      getAllAttributes.

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

    • getAttribute

      public Object getAttribute(String key)
      Retrieves the value associated with the given key in the attribute map.
      Specified by:
      getAttribute in interface Graph
      Parameters:
      key - the key of the attribute to be retrieved
      Returns:
      the value associated with the given key

    • removeAttribute

      public void removeAttribute(String key)
      Removes an attribute from the graph.
      Specified by:
      removeAttribute in interface Graph
      Parameters:
      key - the key of the attribute to remove

    • addAttribute

      public void addAttribute(String key, Object value)
      Adds an attribute to the graph.
      Specified by:
      addAttribute in interface Graph
      Parameters:
      key - the key of the attribute
      value - the value of the attribute

    • getAmbiguousTriples

      public Set<Triple> getAmbiguousTriples()
      Returns a set of ambiguous triples.
      Specified by:
      getAmbiguousTriples in interface Graph
      Returns:
      a set of ambiguous triples

    • setAmbiguousTriples

      public void setAmbiguousTriples(Set<Triple> triples)
      Sets the ambiguous triples for the object.
      Specified by:
      setAmbiguousTriples in interface Graph
      Parameters:
      triples - a set of Triple objects representing ambiguous triples

    • getUnderLines

      public Set<Triple> getUnderLines()
      Retrieves the set of underlined triples.
      Specified by:
      getUnderLines in interface Graph
      Returns:
      The set of underlined triples as a Set of Triple objects.

    • 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)
      Determines if a triple of nodes is ambiguous.
      Specified by:
      isAmbiguousTriple in interface Graph
      Parameters:
      x - the first node in the triple.
      y - the second node in the triple.
      z - the third node in the triple.
      Returns:
      true if the triple is ambiguous, false otherwise.

    • isUnderlineTriple

      public boolean isUnderlineTriple(Node x, Node y, Node z)
      Determines if a triple of nodes is underlined.
      Specified by:
      isUnderlineTriple in interface Graph
      Parameters:
      x - the first Node in the triple
      y - the second Node in the triple
      z - the third Node in the triple
      Returns:
      true if the triple is underlined, false otherwise

    • addAmbiguousTriple

      public void addAmbiguousTriple(Node x, Node y, Node z)
      Adds an ambiguous triple to the list of ambiguous triples. An ambiguous triple consists of three nodes: x, y, and z.
      Specified by:
      addAmbiguousTriple in interface Graph
      Parameters:
      x - the first node in the ambiguous triple
      y - the second node in the ambiguous triple
      z - the third node in the ambiguous triple

    • addUnderlineTriple

      public void addUnderlineTriple(Node x, Node y, Node z)
      Adds an underline triple to the current object.
      Specified by:
      addUnderlineTriple in interface Graph
      Parameters:
      x - The first Node object in the triple.
      y - The second Node object in the triple.
      z - The third Node object in the triple.

    • addDottedUnderlineTriple

      public void addDottedUnderlineTriple(Node x, Node y, Node z)
      Adds a dotted underline triple to the graph.
      Specified by:
      addDottedUnderlineTriple in interface Graph
      Parameters:
      x - The first node of the triple.
      y - The second node of the triple.
      z - The third node of the triple.

    • removeAmbiguousTriple

      public void removeAmbiguousTriple(Node x, Node y, Node z)
      Removes an ambiguous triple from the list of ambiguous triples.
      Specified by:
      removeAmbiguousTriple in interface Graph
      Parameters:
      x - The first node of the triple.
      y - The second node of the triple.
      z - The third node of the triple.

    • removeUnderlineTriple

      public void removeUnderlineTriple(Node x, Node y, Node z)
      Removes an underline triple from the list of underline triples.
      Specified by:
      removeUnderlineTriple in interface Graph
      Parameters:
      x - The first Node object in the underline triple.
      y - The second Node object in the underline triple.
      z - The third Node object in the underline triple.

    • removeDottedUnderlineTriple

      public void removeDottedUnderlineTriple(Node x, Node y, Node z)
      Removes a dotted underline triple from the set of triples.
      Specified by:
      removeDottedUnderlineTriple in interface Graph
      Parameters:
      x - the first node of the triple to be removed
      y - the second node of the triple to be removed
      z - the third node of the triple to be removed

    • setUnderLineTriples

      public void setUnderLineTriples(Set<Triple> triples)
      Sets the underlined triples.
      Specified by:
      setUnderLineTriples in interface Graph
      Parameters:
      triples - a set of triples to be set as underlined

    • setDottedUnderLineTriples

      public void setDottedUnderLineTriples(Set<Triple> triples)
      Sets the dotted underline triples for the given set of Triples. Clears the existing dotted underline triples and adds the new ones from the set.
      Specified by:
      setDottedUnderLineTriples in interface Graph
      Parameters:
      triples - a Set of Triples to set as dotted underline triples

    • removeTriplesNotInGraph

      public void removeTriplesNotInGraph()
      Removes triples from the graph that contain nodes not present in the graph or are not adjacent to each other.
      Specified by:
      removeTriplesNotInGraph in interface Graph