Skip to content

Graph SDG Module

This module supports Simple Dependency Graphs (SDGs) which are a general form of graph that has at most one edge between any pair of nodes.

The two endpoints of each edge can be a head ">", tail "-" or circle "o" (which means either head or tail).

This format can represent most dependency graph types including: - Markov Graphs - Directed Acyclic Graphs (DAGs) - Partially Directed Acyclic Graphs (PDAGs) - Maximal Ancestral Graphs (MAGs) - Partial Ancestral Graphs (PAGs)

Classes

SDG

Simple Dependency Graph class that supports multiple edge types.

Features:

  • Mixed edge types (directed, undirected, bidirected)
  • Node and edge validation
  • Graph manipulation and traversal
  • Adjacency matrix representation

Usage:

from causaliq_core.graph import SDG, EdgeType

# Create an SDG with mixed edges
nodes = ['A', 'B', 'C']
edges = [
    ('A', '->', 'B'),    # Directed edge
    ('B', '--', 'C'),    # Undirected edge
]
sdg = SDG(nodes, edges)

Reference

Simple Dependency Graph (SDG)

This module supports Simple Dependency Graphs (SDGs) which are a general form of graph that has at most one edge between any pair of nodes.

The two endpoints of each edge can be a head ">", tail "-" or circle "o" (which means either head or tail).

This format can represent most dependency graph types including
  • Markov Graphs
  • Directed Acyclic Graphs (DAGs)
  • Partially Directed Acyclic Graphs (PDAGs)
  • Maximal Ancestral Graphs (MAGs)
  • Partial Ancestral Graphs (PAGs)

Classes:

  • SDG –

    Base class for simple dependency graphs (one edge between vertices).

Classes

SDG 

SDG(nodes: List[str], edges: List[Tuple[str, str, str]])

Base class for simple dependency graphs (one edge between vertices).

Simple Dependency Graphs (SDGs) are a general form of graph that has at most one edge between any pair of nodes. The two endpoints of each edge can be a head ">", tail "-" or circle "o" (which means either head or tail).

This format can represent most dependency graph types including: - Markov Graphs - Directed Acyclic Graphs (DAGs) - Partially Directed Acyclic Graphs (PDAGs) - Maximal Ancestral Graphs (MAGs) - Partial Ancestral Graphs (PAGs)

Parameters:

  • nodes
    (List[str]) –

    Nodes present in the graph.

  • edges
    (List[Tuple[str, str, str]]) –

    Edges which define the graph connections as list of tuples: (node1, dependency symbol, node2).

Attributes:

  • nodes (List[str]) –

    Graph nodes in alphabetical order.

  • edges (Dict[Tuple[str, str], EdgeType]) –

    Graph edges {(node1, node2): EdgeType}.

  • is_directed (bool) –

    Graph only has directed (causal) edges.

  • is_partially_directed (bool) –

    Graph is partially directed.

  • parents (Dict[str, List[str]]) –

    Parents of node {node: [parents]}.

  • has_directed_cycles (bool) –

    Contains any directed cycles.

Raises:

  • TypeError –

    If nodes and edges are not both lists.

  • ValueError –

    If node or edge is invalid.

Parameters:

  • nodes
    (List[str]) –

    List of node names in the graph.

  • edges
    (List[Tuple[str, str, str]]) –

    List of edge tuples in format (node1, edge_type_symbol, node2).

Methods:

  • rename –

    Rename nodes in place according to name map.

  • partial_order –

    Return partial topological ordering for the directed part of a

  • is_DAG –

    Return whether graph is a Directed Acyclic Graph (DAG).

  • is_PDAG –

    Return whether graph is a Partially Directed Acyclic Graph (PDAG).

  • undirected_trees –

    Return undirected trees present in graph.

  • components –

    Return components present in graph.

  • number_components –

    Return number of components (including unconnected nodes) in graph.

  • to_adjmat –

    Return an adjacency matrix representation of the graph.

  • __str__ –

    Return a human-readable description of the graph.

  • __eq__ –

    Test if graph is identical to this one.

Functions
rename 
rename(name_map: Dict[str, str]) -> None

Rename nodes in place according to name map.

Parameters:

  • name_map (Dict[str, str]) –

    Name mapping {name: new name}. Must have mapping for every node.

Raises:

  • TypeError –

    With bad arg type.

  • ValueError –

    With bad arg values e.g. unknown node names.

partial_order classmethod 
partial_order(
    parents: Dict[str, List[str]],
    nodes: Optional[Union[List[str], Set[str]]] = None,
    new_arc: Optional[Tuple[str, str]] = None,
) -> Optional[List[Set[str]]]

Return partial topological ordering for the directed part of a graph.

The graph is specified by list of parents for each node.

Parameters:

  • parents (Dict[str, List[str]]) –

    Parents of each node {node: [parents]}.

  • nodes (Optional[Union[List[str], Set[str]]], default: None ) –

    Optional complete list of nodes including parentless ones for use if parents argument doesn't include them already.

  • new_arc (Optional[Tuple[str, str]], default: None ) –

    A new arc (n1, n2) to be added before order is evaluated. If the opposing arc is implied in parents then it is removed so that arc reversal is also supported. This argument facilitates seeing whether an arc addition or reversal would create a cycle.

Returns:

  • Optional[List[Set[str]]] –

    Nodes in a partial topological order as list of sets or None if

  • Optional[List[Set[str]]] –

    there is no ordering which means the graph is cyclic.

is_DAG 
is_DAG() -> bool

Return whether graph is a Directed Acyclic Graph (DAG).

Returns:

  • bool –

    True if graph is a DAG, False otherwise.

is_PDAG 
is_PDAG() -> bool

Return whether graph is a Partially Directed Acyclic Graph (PDAG).

Returns:

  • bool –

    True if graph is a PDAG, False otherwise.

undirected_trees 
undirected_trees() -> List[Set[Union[Tuple[str, str], Tuple[str, None]]]]

Return undirected trees present in graph.

Returns:

  • List[Set[Union[Tuple[str, str], Tuple[str, None]]]] –

    List of trees, each tree a set of tuples representing edges in tree

  • List[Set[Union[Tuple[str, str], Tuple[str, None]]]] –

    (n1, n2) or a single isolated node (n1, None).

components 
components() -> List[List[str]]

Return components present in graph.

Uses tree search algorithm to span the undirected graph to identify nodes in individual trees which are the spanning tree of each component.

Returns:

  • List[List[str]] –

    List of lists, each a list of sorted nodes in component.

number_components 
number_components() -> int

Return number of components (including unconnected nodes) in graph.

Returns:

  • int –

    Number of components.

to_adjmat 
to_adjmat() -> DataFrame

Return an adjacency matrix representation of the graph.

Returns:

  • DataFrame –

    Adjacency matrix as a pandas DataFrame.

__str__ 
__str__() -> str

Return a human-readable description of the graph.

Returns:

  • str –

    String description of graph.

__eq__ 
__eq__(other: object) -> bool

Test if graph is identical to this one.

Parameters:

  • other (object) –

    Graph to compare with self.

Returns:

  • bool –

    True if other is identical to self.