Class GraphTransforms

java.lang.Object
edu.cmu.tetrad.graph.GraphTransforms
public class GraphTransforms extends Object
Transformations that transform one graph into another.
Version:
$Id: $Id
Author:
josephramsey

  • Method Summary

    Modifier and Type
    Method
    Description
    static Graph
    calcAdjacencyGraph(Graph dag)
    Calculates the adjacency graph for the given Directed Acyclic Graph (DAG).
    static Graph
    dagFromCpdag(Graph graph)
    Converts a completed partially directed acyclic graph (CPDAG) into a directed acyclic graph (DAG).
    static Graph
    dagFromCpdag(Graph graph, boolean verbose)
    Converts a completed partially directed acyclic graph (CPDAG) into a directed acyclic graph (DAG).
    static Graph
    dagFromCpdag(Graph graph, boolean meekPreventCycles, boolean verbose)
    Converts a completed partially directed acyclic graph (CPDAG) into a directed acyclic graph (DAG).
    static Graph
    dagFromCpdag(Graph graph, Knowledge knowledge)
    dagFromCpdag.
    static Graph
    dagFromCpdag(Graph cpdag, Knowledge knowledge, boolean verbose)
    Returns a random DAG from the given CPDAG.
    static Graph
    dagToCpdag(Graph dag)
    Returns the completed partially directed acyclic graph (CPDAG) for a given directed acyclic graph (DAG).
    static @NotNull Graph
    dagToMag(Graph dag)
    Converts a Directed Acyclic Graph (DAG) to a Maximal Ancestral Graph (MAG) by adding arrows to the edges.
    static @NotNull Graph
    dagToPag(Graph graph, boolean excludeSelectionBias)
    Converts a Directed Acyclic Graph (DAG) to a Partial Ancestral Graph (PAG) using the DagToPag algorithm.
    static Graph
    dagToPag(Graph graph, boolean excludeSelectionBias, int timeoutSeconds)
    Converts a Directed Acyclic Graph (DAG) to a Partial Ancestral Graph (PAG).
    static Graph
    dagToPag(Graph graph, Knowledge knowledge, boolean excludeSelectionBias, int recursiveDepth)
    Converts a Directed Acyclic Graph (DAG) to a Partial Ancestral Graph (PAG) using the provided DAG and knowledge.
    static Graph
    dcgToCcdPag(Graph graph)
    Returns the graph CCD is meant to recover from a directed cyclic graph (DCG): the cyclic PAG of its d-separation equivalence class, with CCD's underline and dotted-underline annotations.
    static List<Graph>
    generateCpdagDags(Graph cpdag, boolean orientBidirectedEdges)
    Generates the list of DAGs in the given cpdag.
    static List<Graph>
    getAllGraphsByDirectingUndirectedEdges(Graph skeleton)
    Returns a list of all possible graphs obtained by directing undirected edges in the given graph.
    static List<Graph>
    getDagsInCpdagMeek(Graph cpdag, Knowledge knowledge)
    Retrieves a list of directed acyclic graphs (DAGs) within the given completed partially directed acyclic graph (CPDAG) using the Meek rules.
    static Graph
    magToPag(Graph mag, boolean excludeSelectionBias, int recursiveDepth)
    Converts a maximal ancestral graph (MAG) into a partial ancestral graph (PAG).
    static Graph
    noUnshieldedColliderDag(Graph und)
    Orients an undirected chordal graph into a DAG with no unshielded colliders by directing every edge from the earlier to the later endpoint of a Maximum Cardinality Search order.
    static Graph
    randomZhangMagFromPag(Graph pag)
    Convenience overload with a fresh Random; use the seeded overload for reproducibility.
    static Graph
    randomZhangMagFromPag(Graph pag, Random random)
    Returns a random Zhang MAG of a PAG.
    static Graph
    revertToUnshieldedColliders(Graph graph, boolean circles)
    Reverts the provided graph to its unshielded colliders, with other endpoints oriented either as circles (PAG case) or tails (CPDAG case).
    static void
    transformCpdagIntoDag(Graph graph, Knowledge knowledge, boolean verbose)
    Transforms a completed partially directed acyclic graph (CPDAG) into a directed acyclic graph (DAG) by orienting the undirected edges in the CPDAG.
    static Graph
    zhangMagFromPag(Graph pag)
    Transforms a partial ancestral graph (PAG) into a maximal ancestral graph (MAG) using Zhang's 2008 Theorem 2.
    static Iterable<Graph>
    zhangMagsFromPag(Graph pag)
    Lazily enumerates the Zhang MAGs of a PAG: one MAG per consistent DAG orientation of the PAG's unoriented component.

    Methods inherited from class Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • dagFromCpdag

      public static Graph dagFromCpdag(Graph graph)
      Converts a completed partially directed acyclic graph (CPDAG) into a directed acyclic graph (DAG). If the given CPDAG is not a PDAG (Partially Directed Acyclic Graph), returns null.
      Parameters:
      graph - the CPDAG to be converted into a DAG
      Returns:
      a directed acyclic graph (DAG) obtained from the given CPDAG. If the given CPDAG is not a PDAG, returns null.

    • dagFromCpdag

      public static Graph dagFromCpdag(Graph graph, boolean verbose)
      Converts a completed partially directed acyclic graph (CPDAG) into a directed acyclic graph (DAG). If the given CPDAG is not a PDAG (Partially Directed Acyclic Graph), returns null.
      Parameters:
      graph - the CPDAG to be converted into a DAG
      verbose - whether to print verbose output
      Returns:
      a directed acyclic graph (DAG) obtained from the given CPDAG. If the given CPDAG is not a PDAG, returns null.

    • dagFromCpdag

      public static Graph dagFromCpdag(Graph graph, boolean meekPreventCycles, boolean verbose)
      Converts a completed partially directed acyclic graph (CPDAG) into a directed acyclic graph (DAG). If the given CPDAG is not a PDAG (Partially Directed Acyclic Graph), returns null.
      Parameters:
      graph - the CPDAG to be converted into a DAG
      meekPreventCycles - whether to prevent cycles using the Meek rules by orienting additional arbitrary unshielded colliders in the graph
      verbose - whether to print verbose output
      Returns:
      a directed acyclic graph (DAG) obtained from the given CPDAG. If the given CPDAG is not a PDAG, returns null.

    • dagFromCpdag

      public static Graph dagFromCpdag(Graph graph, Knowledge knowledge)

      dagFromCpdag.

      Parameters:
      graph - a Graph
      knowledge - a Knowledge
      Returns:
      a Graph object

    • dagFromCpdag

      public static Graph dagFromCpdag(Graph cpdag, Knowledge knowledge, boolean verbose)
      Returns a random DAG from the given CPDAG. If the given CPDAG is not a PDAG, returns null.
      Parameters:
      cpdag - the CPDAG
      knowledge - the knowledge
      verbose - whether to print verbose output.
      Returns:
      a DAG from the given CPDAG. If the given CPDAG is not a PDAG, returns null.

    • transformCpdagIntoDag

      public static void transformCpdagIntoDag(Graph graph, Knowledge knowledge, boolean verbose)
      Transforms a completed partially directed acyclic graph (CPDAG) into a directed acyclic graph (DAG) by orienting the undirected edges in the CPDAG.
      Parameters:
      graph - The original graph from which the CPDAG was derived.
      knowledge - The knowledge available to check if a potential DAG violates any constraints.
      verbose - Whether to print verbose output.

    • zhangMagFromPag

      public static Graph zhangMagFromPag(Graph pag)
      Transforms a partial ancestral graph (PAG) into a maximal ancestral graph (MAG) using Zhang's 2008 Theorem 2.
      Parameters:
      pag - The partially ancestral graph to transform.
      Returns:
      The maximally ancestral graph obtained from the PAG.

    • noUnshieldedColliderDag

      public static Graph noUnshieldedColliderDag(Graph und)
      Orients an undirected chordal graph into a DAG with no unshielded colliders by directing every edge from the earlier to the later endpoint of a Maximum Cardinality Search order. Reversed MCS is a perfect elimination order for chordal graphs (Tarjan and Yannakakis, 1984), so each vertex's earlier neighbors -- its parents under this orientation -- form a clique. Deterministic: ties broken by node name. If the input is NOT chordal (an invalid "PAG"), the result is still a DAG over the same skeleton but may contain unshielded colliders; callers wanting the guarantee should round-trip check.
      Parameters:
      und - the undirected graph (the circle component of a PAG).
      Returns:
      a DAG over the same skeleton whose parent sets are cliques.

    • zhangMagsFromPag

      public static Iterable<Graph> zhangMagsFromPag(Graph pag)
      Lazily enumerates the Zhang MAGs of a PAG: one MAG per consistent DAG orientation of the PAG's unoriented component. Identical to zhangMagFromPag(Graph) except that ConsistentDagIterator supplies EVERY no-unshielded-collider orientation of result.pcafci() in place of the single dagFromCpdag extension. Each MAG is a fresh copy of the component-stripped PAG with one orientation stamped in, so the shared template is never mutated.
      Parameters:
      pag - the PAG to transform (assumed a valid, completed PAG).
      Returns:
      a lazy iterable over the Zhang MAGs reachable from pag.

    • randomZhangMagFromPag

      public static Graph randomZhangMagFromPag(Graph pag, Random random)
      Returns a random Zhang MAG of a PAG. A uniformly shuffled seed order is passed through getValidOrder to get a random valid causal order of the PAG's unoriented component; that order orients the component into a consistent DAG; and, exactly as in zhangMagFromPag(Graph), those directed edges are stamped onto the component-stripped PAG.
      Parameters:
      pag - the PAG to transform (assumed a valid, completed PAG).
      random - source of randomness (seed it for reproducibility).
      Returns:
      a random Zhang MAG obtained from pag.

    • randomZhangMagFromPag

      public static Graph randomZhangMagFromPag(Graph pag)
      Convenience overload with a fresh Random; use the seeded overload for reproducibility.
      Parameters:
      pag - The PAG to find a random Zhang MAG in.
      Returns:
      this graph.

    • generateCpdagDags

      public static List<Graph> generateCpdagDags(Graph cpdag, boolean orientBidirectedEdges)
      Generates the list of DAGs in the given cpdag.
      Parameters:
      cpdag - a Graph object
      orientBidirectedEdges - a boolean
      Returns:
      a List object

    • getDagsInCpdagMeek

      public static List<Graph> getDagsInCpdagMeek(Graph cpdag, Knowledge knowledge)
      Retrieves a list of directed acyclic graphs (DAGs) within the given completed partially directed acyclic graph (CPDAG) using the Meek rules.
      Parameters:
      cpdag - The completed partially directed acyclic graph (CPDAG) from which to retrieve the DAGs.
      knowledge - The knowledge available to check if a potential DAG violates any constraints.
      Returns:
      A List of Graph objects representing the DAGs within the CPDAG.

    • getAllGraphsByDirectingUndirectedEdges

      public static List<Graph> getAllGraphsByDirectingUndirectedEdges(Graph skeleton)
      Returns a list of all possible graphs obtained by directing undirected edges in the given graph.
      Parameters:
      skeleton - the graph to transform
      Returns:
      a list of all possible graphs obtained by directing undirected edges

    • dagToCpdag

      public static Graph dagToCpdag(Graph dag)
      Returns the completed partially directed acyclic graph (CPDAG) for a given directed acyclic graph (DAG).
      Parameters:
      dag - The input DAG.
      Returns:
      The CPDAG resulting from applying Meek Rules to the input DAG.

    • dcgToCcdPag

      public static Graph dcgToCcdPag(Graph graph)
      Returns the graph CCD is meant to recover from a directed cyclic graph (DCG): the cyclic PAG of its d-separation equivalence class, with CCD's underline and dotted-underline annotations. It is computed by running CCD itself against an m-separation oracle on graph, which is what CCD converges to in the large-sample limit, in the same spirit as dagToPag(Graph, boolean) for the acyclic case.

      Unlike a DAG's PAG, this object cannot be read off the graph by local surgery, because a cycle makes pairs inseparable that are not adjacent in the DCG - Richardson's "virtual edges". Those edges are present here and absent from graph, which is why scoring CCD against the DCG itself understates it badly: on random 8-node, 10-edge DCGs the oracle PAG carries 2.76 more edges than the DCG on average, and a perfect CCD run scores only 0.387 endpoint-exact and 0.828 adjacency F1 when graded against the DCG.

      Valid for linear cyclic models with independent errors, where d-separation is the correct global Markov property (Spirtes, 1995). General (non-linear) cyclic models need sigma-separation instead, and this method does not apply to them.

      Parameters:
      graph - a directed graph, possibly cyclic.
      Returns:
      the cyclic PAG CCD should recover from it.
      See Also:

    • dagToPag

      public static Graph dagToPag(Graph graph, boolean excludeSelectionBias, int timeoutSeconds)
      Converts a Directed Acyclic Graph (DAG) to a Partial Ancestral Graph (PAG). This method executes the conversion process asynchronously and allows for a configurable timeout. If the conversion process exceeds the specified timeout or is interrupted, it throws a runtime exception.
      Parameters:
      graph - The input graph, represented as a Directed Acyclic Graph (DAG), to be converted to a PAG.
      excludeSelectionBias - A boolean flag indicating whether to exclude selection bias during the conversion process.
      timeoutSeconds - The maximum time, in seconds, to wait for the conversion process to complete.
      Returns:
      The resulting Partial Ancestral Graph (PAG) obtained by converting the input DAG.
      Throws:
      RuntimeException - If the conversion process times out, is interrupted, or encounters an exception.

    • dagToPag

      @NotNull public static @NotNull Graph dagToPag(Graph graph, boolean excludeSelectionBias)
      Converts a Directed Acyclic Graph (DAG) to a Partial Ancestral Graph (PAG) using the DagToPag algorithm.
      Parameters:
      graph - The input DAG to be converted.
      excludeSelectionBias - True to exclude selection bias, false otherwise.
      Returns:
      The resulting PAG obtained from the input DAG.

    • dagToPag

      public static Graph dagToPag(Graph graph, Knowledge knowledge, boolean excludeSelectionBias, int recursiveDepth)
      Converts a Directed Acyclic Graph (DAG) to a Partial Ancestral Graph (PAG) using the provided DAG and knowledge.
      Parameters:
      graph - The input Directed Acyclic Graph (DAG) to be converted.
      knowledge - Background knowledge used to guide the conversion process.
      excludeSelectionBias - True to exclude selection bias, false otherwise.
      recursiveDepth - Recursion depth to consider during PAG computation.
      Returns:
      The resulting Partial Ancestral Graph (PAG) obtained from the input DAG and knowledge.
      Throws:
      IllegalStateException - if a discriminating path cannot be found.

    • dagToMag

      @NotNull public static @NotNull Graph dagToMag(Graph dag)
      Converts a Directed Acyclic Graph (DAG) to a Maximal Ancestral Graph (MAG) by adding arrows to the edges.
      Parameters:
      dag - The input DAG to be converted.
      Returns:
      The resulting MAG obtained from the input DAG.

    • calcAdjacencyGraph

      public static Graph calcAdjacencyGraph(Graph dag)
      Calculates the adjacency graph for the given Directed Acyclic Graph (DAG).
      Parameters:
      dag - The input MAG.
      Returns:
      The adjacency graph represented by a Graph object.

    • revertToUnshieldedColliders

      public static Graph revertToUnshieldedColliders(Graph graph, boolean circles)
      Reverts the provided graph to its unshielded colliders, with other endpoints oriented either as circles (PAG case) or tails (CPDAG case). The operation orients a copy of the graph with no orientations, then iterates through the unshielded colliders (X --> Y <-- Z with ~adj(X, Z)) in the original graph and makes these orientations in the new graph.
      Parameters:
      graph - the input graph on which the operation is performed.
      circles - if other endpoints should otherwise be circles (PAG case), false if tails (CPDAG case).
      Returns:
      a new graph with the specified updates applied.

    • magToPag

      public static Graph magToPag(Graph mag, boolean excludeSelectionBias, int recursiveDepth)
      Converts a maximal ancestral graph (MAG) into a partial ancestral graph (PAG).
      Parameters:
      mag - the maximal ancestral graph (MAG) to be converted
      excludeSelectionBias - whether to exclude selection bias
      recursiveDepth - the maximum current depth of recursion in the conversion process
      Returns:
      the resulting partial ancestral graph (PAG)