API reference

andrey.GraphStructure#

class andrey.GraphStructure[source]#

A learned graph: its nodes, and a mark at each end of every edge.

A method returns one as StructureOutput.structure; from_numpy, from_edges, from_networkx, and from_pcalg build one from an existing graph. kind says how to read the edges:

  • "dag": every edge is directed, with no directed cycles.

  • "cpdag": an equivalence class of DAGs; an undirected edge -- can point either way.

  • "pag": an equivalence class that allows hidden variables; a circle o is an unresolved endpoint, and <-> is a relation through hidden causes.

  • "digraph": directed edges that may form cycles and self-loops, such as the graph for a positive lag of a TemporalStructure. Here the pair (2, 2) is two directed edges, i -> j and j -> i.

A cell M[i, j] of to_numpy() is the mark at node i on its edge with j: 0 absent, 1 tail, 2 arrowhead, 3 circle (andrey.core.NULL, TAIL, ARROW, CIRCLE). endpoints(i, j) reads one edge, and oriented_edges() lists every edge as (source, target, type). oriented_edges(), to_edges(), and to_scipy_sparse() scale to large graphs; to_numpy() and adjacency build a dense (n, n) array on each call. The graph is read-only.

classmethod from_numpy(M, *, kind=None, labels=None, allow_self_loops=False, node_types=None)[source]#

Build a graph from an (n, n) endpoint-mark matrix, the inverse of to_numpy.

Parameters:

  • M (ndarray) – Endpoint marks: M[i, j] is the mark at node i on its edge with j, 0 absent, 1 tail, 2 arrowhead, 3 circle. i -> j is M[i, j] = 1 and M[j, i] = 2. Every edge needs a mark in both cells.

  • kind (Literal['dag', 'cpdag', 'pag', 'digraph'] | None) – Graph type. None infers "pag" from any circle or (2, 2) pair, else "cpdag" from any (1, 1) pair, else "dag"; it never infers "digraph", so pass it for a graph with 2-cycles. The marks are not checked against kind; call validate().

  • labels (tuple[str, ...] | None) – Node names, one per node, each taken as text, str(label); None numbers the nodes from 0.

  • allow_self_loops (bool) – Accept self-loops on the diagonal. A self-loop M[i, i] = 2 is a variable’s effect on its own future, in the graph for a positive lag of a TemporalStructure; 2 is the only self-loop mark.

  • node_types (ndarray | None) – 0 for an observed node and 1 for a latent one (andrey.core.OBSERVED, LATENT); None when every node is observed.

Returns:

The graph.

Return type:

GraphStructure

Raises:

ValueError – If kind is not one of the four kinds, M is not square, has a nonzero diagonal without allow_self_loops or a diagonal value other than 0 or 2 with it, holds a value outside 0..3, has a mark in M[i, j] but not in M[j, i], labels does not have n entries or has two that are equal as text, such as 1 and "1", or node_types is not shape (n,).

classmethod from_edges(edges, *, n_nodes, kind=None, labels=None)[source]#

Build a graph from an edge list, the inverse of to_edges.

Parameters:

  • edges (ndarray) – Structured array with fields i, j, mark_i, mark_j (dtype andrey.core.EDGE_DTYPE), one row per edge; mark_i is the mark at i and mark_j the mark at j. A row with i == j is a self-loop.

  • n_nodes (int) – Number of nodes, including nodes without edges.

  • kind (Literal['dag', 'cpdag', 'pag', 'digraph'] | None) – Graph type; None infers it as from_numpy does.

  • labels (tuple[str, ...] | None) – Node names, one per node, each taken as text, str(label); None numbers the nodes from 0.

Returns:

The graph.

Return type:

GraphStructure

Raises:

  • ValueError – If a mark is outside 0..3, a row has a mark at one end only, or labels does not have n_nodes entries or has two that are equal as text.

  • IndexError – If edges is not a structured array with those fields, or names a node outside range(n_nodes).

classmethod from_networkx(g, *, kind=None)[source]#

Build a graph from a NetworkX graph, the inverse of to_networkx.

Each edge (u, v) is read from its endpoints=(mark at u, mark at v) attribute. An edge without the attribute is u -> v. Two such edges u -> v and v -> u give the mark pair (2, 2), so pass kind="digraph" to read them as a 2-cycle rather than a pag bidirected edge. Self-loops are kept. Nodes are indexed in insertion order; unless they are exactly 0, 1, ..., n - 1 in that order, each node becomes a label, converted to str.

Parameters:

  • g (DiGraph) – The graph to read.

  • kind (Literal['dag', 'cpdag', 'pag', 'digraph'] | None) – Graph type; None infers it as from_numpy does.

Returns:

The graph.

Return type:

GraphStructure

Raises:

ValueError – If an endpoints mark is outside 0..3, an edge has a mark at one end only, or two nodes are equal as text, such as 1 and "1".

classmethod from_pcalg(amat, kind, *, labels=None)[source]#

Build a graph from the adjacency matrix amat that R’s pcalg package uses.

pcalg records a PAG, and a MAG, as amat.pag: amat[a, b] is the mark at the column node b on the edge between a and b, 0 no edge, 1 circle, 2 arrowhead, 3 tail. It records a DAG or CPDAG as amat.cpdag: a -> b is amat[b, a] = 1 with amat[a, b] = 0, at the child’s row, and a -- b is 1 in both cells. This reads either, the inverse of to_pcalg.

Parameters:

  • amat (ArrayLike) – The pcalg matrix, such as fit@amat from fci or as(fit, "amat") from pc.

  • kind (Literal['dag', 'cpdag', 'pag']) – How pcalg coded the graph: "pag" reads amat.pag (a MAG too), and "cpdag" and "dag" read amat.cpdag.

  • labels (tuple[str, ...] | None) – Node names, one per node, each taken as text, str(label); None numbers the nodes from 0.

Returns:

The graph, of kind.

Return type:

GraphStructure

Raises:

ValueError – If kind is not "dag", "cpdag", or "pag", amat is not square, has a nonzero diagonal, holds a value other than 0, 1, 2, 3 for a "pag" or 0 and 1 otherwise, or, for a "pag", has a mark in amat[a, b] but not in amat[b, a]. Also if the edges are not allowed for kind, such as an undirected edge in a "dag", or labels does not have n entries or has two that are equal as text.

Examples

>>> import numpy as np
>>> from andrey import GraphStructure
>>> amat = np.array([[0, 0, 0], [0, 0, 0], [1, 1, 0]])  # 0 -> 2 <- 1, child's row 2
>>> GraphStructure.from_pcalg(amat, "cpdag").oriented_edges()
[(0, 2, 'directed'), (1, 2, 'directed')]
property kind: Literal['dag', 'cpdag', 'pag', 'digraph']#

"dag", "cpdag", "pag", or "digraph" (cycles allowed).

Type:

Graph type

property node_types: ndarray | None#

Per-node codes, 0 observed and 1 latent, or None when every node is observed.

gin sets it for the latent nodes it adds (andrey.core.OBSERVED, LATENT).

property adjacency: ndarray#

The endpoint-mark matrix, the same as to_numpy(); see to_numpy for the codes.

Each access builds a new dense (n, n) array; for a large graph use oriented_edges, to_edges, or to_scipy_sparse.

to_numpy(*, dtype=<class 'numpy.int8'>)[source]#

Return the endpoint marks as a dense (n, n) array.

A cell M[i, j] is the mark at node i on its edge with j: 0 absent, 1 tail, 2 arrowhead, 3 circle. i -> j has M[i, j] = 1 and M[j, i] = 2. Each call builds a new array.

Parameters:

dtype (DTypeLike) – Data type of the returned array.

Returns:

The endpoint-mark matrix.

Return type:

ndarray

to_scipy_sparse()[source]#

Return the endpoint marks as a scipy.sparse.csr_array, without a dense array.

Returns:

The to_numpy matrix in sparse form; memory grows with the number of edges.

Return type:

csr_array

to_networkx(*, multigraph=False)[source]#

Return the graph as a NetworkX graph whose edges carry their marks.

Each arc (u, v) has the attribute endpoints=(mark at u, mark at v). For a dag, cpdag, or pag, each edge is one arc from the lower to the higher node index whatever its direction, so read endpoints or use oriented_edges(). A digraph runs each arc from tail to arrowhead and gives a 2-cycle both arcs, so NetworkX cycle functions see its cycles. A MultiDiGraph also adds the reverse arc for <-> and o-o. Nodes are named by labels when set, else numbered from 0. from_networkx reads the result back.

Parameters:

multigraph (bool) – Return a MultiDiGraph for any kind; a pag always gets one.

Returns:

A MultiDiGraph for a pag or with multigraph=True, else a DiGraph.

Return type:

DiGraph | MultiDiGraph

to_pcalg()[source]#

Return the adjacency matrix amat that R’s pcalg package uses for this kind of graph.

A pag is written as pcalg’s amat.pag: amat[a, b] is the mark at the column node b on the edge between a and b, 0 no edge, 1 circle, 2 arrowhead, 3 tail. A dag or cpdag is written as amat.cpdag: a -> b is amat[b, a] = 1 with amat[a, b] = 0, at the child’s row, and a -- b is 1 in both cells. from_pcalg reads the result back. Each call builds a new array.

Returns:

The pcalg matrix, int8.

Return type:

ndarray

Raises:

ValueError – If the graph is a digraph, which pcalg has no matrix for, has a self-loop, or has an edge its kind does not allow (validate() lists them).

Examples

>>> from andrey import GraphStructure
>>> import numpy as np
>>> M = np.array([[0, 1], [2, 0]])  # 0 -> 1
>>> GraphStructure.from_numpy(M, kind="dag").to_pcalg().tolist()
[[0, 0], [1, 0]]
to_edges()[source]#

Return the derived typed edge list, one row per edge i <= j.

Returns:

Structured array (dtype andrey.core.EDGE_DTYPE) with fields i, j, mark_i, mark_j, one row per edge with i <= j; mark_i is the mark at i. A row with i == j is a self-loop.

Return type:

ndarray

oriented_edges(*, index=False)[source]#

Return one (source, target, type) row per edge, oriented by its marks.

A directed edge runs from its tail to its arrowhead whatever the node order, and nodes are named by labels when the graph has them. andrey run prints the same rows.

Parameters:

index (bool) – Return node indices even when the graph has labels.

Returns:

Rows follow to_edges order. A digraph 2-cycle yields two directed rows, lower-to-higher node index first, then the reverse. type is one of:

  • directed: source -> target; a self-loop has source == target.

  • partially_directed: source o-> target.

  • partially_undirected: source -o target, a tail at source and a circle at target.

  • undirected: source -- target.

  • bidirected: source <-> target in a pag.

  • circle: source o-o target.

The three symmetric types list the lower node index first.

Return type:

list[tuple[str | int, str | int, str]]

Examples

>>> import numpy as np
>>> from andrey import GraphStructure
>>> M = np.array([[0, 2], [1, 0]])  # the arrowhead is at node 0
>>> GraphStructure.from_numpy(M, labels=("wet", "rain")).oriented_edges()
[('rain', 'wet', 'directed')]
neighbors(i)[source]#

Return the nodes that share an edge with node i, whatever the marks.

For a dag or cpdag each call scans every edge; to visit every node, use to_scipy_sparse().

Parameters:

i (int) – Node index.

Returns:

The adjacent node indices, ascending and read-only; includes i if it has a self-loop.

Return type:

ndarray

endpoints(i, j)[source]#

Return the endpoint marks on edge i-j. O(log deg).

Parameters:

  • i (int) – First node index.

  • j (int) – Second node index.

Returns:

(mark at i, mark at j): 1 tail, 2 arrowhead, 3 circle; (0, 0) when there is no edge.

Return type:

tuple[int, int]

validate()[source]#

Check that every edge’s marks are allowed for kind.

It does not check a dag for directed cycles, or that a cpdag or pag is a completed equivalence class.

Raises:

ValueError – If a circle appears outside a pag, a dag or cpdag has an edge with two arrowheads, a dag or digraph has an undirected edge, or an edge has a mark at one end only.

Return type:

None