Developer Docs

Some notes on performance. Before doing any of these, please benchmark/profile the code, to see if it affects the performance.

Skipping validation

Every graph constructor takes validate::Bool. You can use validate=false if the algorithm is proven to give a valid graph type, e.g. dag_to_cpdag's last step.

CausalStructures._build_graph — Function

T(node_set, edges::Vector{CausalEdge}; validate::Bool = true) -> T

Every concrete graph type T (DAG, UG, PDAG, CPDAG, MPDAG, ADMG, AG, MAG, UNKNOWN, PAG) has this constructor, which builds a graph directly from a node set and an edge vector, bypassing the items... collection and the string DSL that the other constructor forms (T(items...), T(s::AbstractString)) go through to get there.

Pass validate = false to skip the structural check for performance reasons.

Examples

julia> DAG(Set([:A, :B]), [directed(:A, :B)])
DAG with 2 nodes and 1 edge:
  nodes: A, B
  edges:
    A --> B

julia> DAG(Set([:A, :B]), [directed(:A, :B), directed(:B, :A)]; validate = false)
DAG with 2 nodes and 2 edges:
  nodes: A, B
  edges:
    A --> B, B --> A

source

There's a stronger version of the same idea: constructing a graph directly from (edges, backend), bypassing build_backend too. This can be useful when the algorithm already has the information needed to construct the backend, so rebuilding it from scratch would be unnecessarily expensive.

For example, enumerate_dags assembles colptr/deg/rowval directly from index sets it already knows are sorted, rather than rebuilding the backend from scratch.

Index-based traversal

parents, children, spouses, and neighbors are the public API and work with Symbol node names. Internally, algorithm code should not call these in hot loops, since each call involves a dictionary lookup and an array allocation.

Instead, work directly with the backend using _parents_slice and related functions. These return a @view of node indices into the backend's CSR rowval array, avoiding the repeated lookups and allocations.

CausalStructures.bucket_slice — Function

bucket_slice(B, i, bucket) -> AbstractVector{Int}

Indices of node i's neighbors in relationship bucket, as a view into B.rowval. Not meaningful on its own: bucket numbers only make sense per backend type.

source

CausalStructures._all_nbrs_slice — Function

_all_nbrs_slice(B, i) -> AbstractVector{Int}

Indices of all of node i's neighbors, across every relationship bucket, as a view into B.rowval.

source

CausalStructures._parents_slice — Function

_parents_slice(B, i) -> AbstractVector{Int}

Indices of the parents of node i (p --> i), as a view into B.rowval.

source

CausalStructures._children_slice — Function

_children_slice(B, i) -> AbstractVector{Int}

Indices of the children of node i (i --> c), as a view into B.rowval.

source

CausalStructures._spouses_slice — Function

_spouses_slice(B, i) -> AbstractVector{Int}

Indices of the spouses of node i (i <-> s), as a view into B.rowval.

source

CausalStructures._undirected_slice — Function

_undirected_slice(B, i) -> AbstractVector{Int}

Indices of node i's undirected neighbors (i --- u), as a view into B.rowval.

source

CausalStructures._circle_children_slice — Function

_circle_children_slice(B::PAGBackend, i) -> AbstractVector{Int}

Indices of j with i o-> j, as a view into B.rowval.

source

CausalStructures._circle_parents_slice — Function

_circle_parents_slice(B::PAGBackend, i) -> AbstractVector{Int}

Indices of j with i <-o j, as a view into B.rowval.

source

CausalStructures._circle_undirected_out_slice — Function

_circle_undirected_out_slice(B::PAGBackend, i) -> AbstractVector{Int}

Indices of j with i o-- j, as a view into B.rowval.

source

CausalStructures._circle_undirected_in_slice — Function

_circle_undirected_in_slice(B::PAGBackend, i) -> AbstractVector{Int}

Indices of j with i --o j, as a view into B.rowval.

source

CausalStructures._circle_circle_slice — Function

_circle_circle_slice(B::PAGBackend, i) -> AbstractVector{Int}

Indices of j with i o-o j, as a view into B.rowval.

source