ananke.graphs

ananke.graphs.admg

Class for acyclic directed mixed graphs (ADMGs) and conditional ADMGs (CADMGs).

class ananke.graphs.admg.ADMG(vertices=[], di_edges={}, bi_edges={}, **kwargs)[source]

Bases: ananke.graphs.sg.SG

Class for creating and manipulating (conditional) acyclic directed mixed graphs (ADMGs/CADMGs).

canonical_dag(cardinality: Optional[Union[int, str]] = None)[source]

Computes the canonical DAG from the ADMG by inserting a variable in place of each bidirected edge.

For each bidirected edge ‘X <-> Y’, the inserted variable will take names of the form ‘U_XY’, the original bidirected edge is removed, and new directed edges ‘U_X_Y -> Y’ and ‘U_X_Y -> X’ are inserted. The variable names are in lexicographic order.

Params cardinality: The cardinality of the inserted variables
Returns: A directed acyclic graph
Return type: DAG

fixable(vertices)[source]

Check if there exists a valid fixing order and return such an order in the form of a list, else returns an empty list.

Parameters: vertices – set of vertices to check fixability for.
Returns: a boolean indicating whether the set was fixable and a valid fixing order as a stack.

property fixed

Returns all fixed nodes in the graph.

Returns

get_intrinsic_sets()[source]

Computes intrinsic sets (and returns the fixing order for each intrinsic set).

Returns: list of intrinsic sets and fixing orders used to reach each one

get_intrinsic_sets_and_heads()[source]

Computes intrinsic sets mapped to a tuple of heads and tails of that intrinsic set, and fixing orders for each one.

Returns: tuple of dict of intrinsic sets to heads and tails, and fixing orders for each intrinsic set

is_ancestral_subgraph(other)[source]

Check that this graph is an ancestral subgraph of the other. An ancestral subgraph over variables S and intervention b G(S(b)) of a larger graph G(V(b)) is defined as a subgraph, such that ancestors of each node s in S with respect to the graph G(V(b_i)) are contained in S.

Parameters: other – an object of the ADMG class.
Returns: boolean indicating whether the statement is True or not.

is_subgraph(other)[source]

Check that this graph is a subgraph of other, meaning it has a subset of edges and nodes of the other.

Parameters: other – an object of the ADMG class.
Returns: boolean indicating whether the statement is True or not.

latent_projection(retained_vertices)[source]

Computes latent projection.

Parameters: retained_vertices – list of vertices to retain after latent projection
Returns: Latent projection containing retained vertices

m_separated(X, Y, separating_set=[])[source]

Computes m-separation for set X and set Y given separating_set

Parameters

X – first vertex set
Y – second vertex set
separating_set – separating set

Returns

boolean result of m-separation

markov_blanket(vertices)[source]

Get the Markov blanket of a set of vertices.

Parameters: vertices – iterable of vertex names.
Returns: set corresponding to Markov blanket.

markov_pillow(vertices, top_order)[source]

Get the Markov pillow of a set of vertices. That is, the Markov blanket of the vertices given a valid topological order on the graph.

Parameters

vertices – iterable of vertex names.
top_order – a valid topological order.

Returns

set corresponding to Markov pillow.

maximal_arid_projection()[source]

Get the maximal arid projection that encodes the same conditional independences and Vermas as the original ADMG. This operation is described in Acyclic Linear SEMs obey the Nested Markov property by Shpitser et al 2018.

Returns: An ADMG corresponding to the maximal arid projection.

mb_shielded()[source]

Check if the ADMG is a Markov blanket shielded ADMG. That is, check if two vertices are non-adjacent only when they are absent from each others’ Markov blankets.

Returns: boolean indicating if it is mb-shielded or not.

nonparametric_saturated()[source]

Check if the nested Markov model implied by the ADMG is nonparametric saturated. The following is an implementation of Algorithm 1 in Semiparametric Inference for Causal Effects in Graphical Models with Hidden Variables (Bhattacharya, Nabi & Shpitser 2020) which was shown to be sound and complete for this task.

Returns: boolean indicating if it is nonparametric saturated or not.

reachable_closure(vertices)[source]

Obtain reachable closure for a set of vertices.

Parameters: vertices – set of vertices to get reachable closure for.
Returns: set corresponding to the reachable closure, the fixing order for vertices outside of the closure, and the CADMG corresponding to the closure.

subgraph(vertices)[source]

Computes subgraph given a set of vertices.

Recomputes districts, since these may change when vertices are removed.

Parameters: vertices – iterable of vertices
Returns: subgraph

exception ananke.graphs.admg.UndefinedADMGOperation(*args, **kwargs)[source]: Bases: Exception

ananke.graphs.admg.latent_project_single_vertex(vertex, graph)[source]

Latent project one vertex from graph

Parameters

vertex – Name of vertex to be projected
graph – ADMG

Returns

ananke.graphs.bg

Class for Bidirected Graphs (BGs).

class ananke.graphs.bg.BG(vertices=[], bi_edges={}, **kwargs)[source]: Bases: ananke.graphs.admg.ADMG

ananke.graphs.cg

Class for Lauritzen-Wermuth-Frydenberg chain graphs (LWF-CGs/CGs).

class ananke.graphs.cg.CG(vertices=[], di_edges={}, ud_edges={}, **kwargs)[source]

Bases: ananke.graphs.sg.SG

boundary(vertices)[source]

Get the boundary of a set of vertices defined as the block and parents of the block.

Parameters: vertices – iterable of vertex names.
Returns: set corresponding to the boundary.

ananke.graphs.dag

Class for Directed Acyclic Graphs (DAGs).

class ananke.graphs.dag.DAG(vertices=[], di_edges={}, **kwargs)[source]

Bases: ananke.graphs.admg.ADMG, ananke.graphs.cg.CG

d_separated(X, Y, separating_set=[])[source]

Computes d-separation for set X and set Y given separating_set

Parameters

X – first vertex set
Y – second vertex set
separating_set – separating set, default list()

Returns

boolean result of d-separation

exception ananke.graphs.dag.UndefinedDAGOperation[source]: Bases: Exception

ananke.graphs.graph

Base class for all graphs.

TODO: Add error checking

class ananke.graphs.graph.Graph(vertices=[], di_edges={}, bi_edges={}, ud_edges={}, **kwargs)[source]

Bases: object

add_biedge(sib1, sib2)[source]

Add a bidirected edge to the graph.

Parameters

sib1 – endpoint 1 of edge.
sib2 – endpoint 2 of edge.

Returns

None.

add_diedge(parent, child)[source]

Add a directed edge to the graph.

Parameters

parent – tail of edge.
child – head of edge.

Returns

None.

add_udedge(neb1, neb2)[source]

Add an undirected edge to the graph.

Parameters

neb1 – endpoint 1 of edge.
neb2 – endpoint 2 of edge.

Returns

None.

add_vertex(name, cardinality=None, **kwargs)[source]

Add a vertex to the graph.

Parameters: name – name of vertex.
Returns: None.

ancestors(vertices)[source]

Get the ancestors of a vertex or set of vertices.

Parameters: vertices – single vertex name or iterable of vertex names to find ancestors for.
Returns: set of ancestors.

children(vertices)[source]

Get children of a vertex or set of vertices.

Parameters: vertices – iterable of vertex names.
Returns: set of children.

copy()[source]: Returns copy of a graph

delete_biedge(sib1, sib2)[source]

Delete given bidirected edge from the graph.

Parameters

sib1 – endpoint 1 of edge.
sib2 – endpoint 2 of edge.

Returns

None.

delete_diedge(parent, child)[source]

Deleted given directed edge from the graph.

Parameters

parent – tail of edge.
child – head of edge.

Returns

None.

delete_udedge(neb1, neb2)[source]

Delete given undirected edge from the graph.

Parameters

neb1 – endpoint 1 of edge.
neb2 – endpoint 2 of edge.

Returns

None.

delete_vertex(name)[source]

Delete a vertex from the graph. Additionally removes any edges from other vertices into the given vertex

Parameters: name – name of vertex.
Returns: None.

descendants(vertices)[source]

Get the descendants of a vertex or set of vertices.

Parameters: vertices – single vertex name or iterable of vertex names to find descendants for.
Returns: set of descendants.

directed_paths(source, sink)[source]

Get all directed paths between sets of source vertices and sink vertices.

Parameters

source – a set of vertices that serve as the source.
sink – a set of vertices that serve as the sink.

Returns

list of directed paths.

draw(direction=None)[source]

Visualize the graph.

:return : dot language representation of the graph.

has_biedge(sib1, sib2)[source]

Check existence of a bidirected edge.

Parameters

sib1 – endpoint 1 of edge.
sib2 – endpoint 2 of edge.

Returns

boolean result of existence.

has_udedge(neb1, neb2)[source]

Check existence of an undirected edge.

Parameters

neb1 – endpoint 1 of edge.
neb2 – endpoint 2 of edge.

Returns

boolean result of existence.

neighbors(vertices)[source]

Get neighbors of a vertex or set of vertices.

Parameters: vertices – iterable of vertex names.
Returns: set of neighbors.

parents(vertices)[source]

Get parents of a vertex or set of vertices.

Parameters: vertices – iterable of vertex names.
Returns: set of parents.

pre(vertices, top_order)[source]

Find all nodes prior to the given set of vertices under a topological order.

Parameters

vertices – iterable of vertex names.
top_order – a valid topological order.

Returns

list corresponding to the order up until the given vertices.

siblings(vertices)[source]

Get siblings of a vertex or set of vertices.

Parameters: vertices – vertex name or iterable of vertex names.
Returns: set of neighbors.

subgraph(vertices)[source]

Return a subgraph on the given vertices (i.e. a graph containing only the specified vertices and edges between them).

Parameters: vertices – set containing names of vertices in the subgraph.
Returns: a new Graph object corresponding to the subgraph.

topological_sort()[source]

Perform a topological sort from roots (parentless nodes) to leaves, as ordered by directed edges on the graph.

Returns: list corresponding to a valid topological order.

ananke.graphs.ig

Class for Intrinsic Graphs (IGs) – a mixed graph used to compute intrinsic sets of an ADMG in polynomial time.

class ananke.graphs.ig.IG(admg)[source]

Bases: ananke.graphs.graph.Graph

add_new_biedges(s)[source]

Naive O(|I(G)| choose 2) implementation. Must ensure that biedges not added to ancestors.

Parameters: s – Frozen set corresponding to the new vertex.
Returns: None.

bidirected_connected(s1, s2)[source]

Check if two sets are bidirected connected in the original ADMG

Parameters

s1 – First set corresponding to a vertex in the IG.
s2 – Second set corresponding to a vertex in the IG.

Returns

boolean corresponding to connectedness.

get_heads_tails()[source]

Iterate through all intrinsic sets and get the recursive heads and tails.

Returns: List of tuples corresponding to (head, tail).

get_intrinsic_sets()[source]

Get all intrinsic sets for given ADMG.

Returns

maintain_subset_relation(s)[source]: Add di edges to a newly inserted vertex s so as to maintain the subset relation. :param s: Frozenset corresponding to the new vertex. :return: None.

merge(s1, s2)[source]

Merge operation on two sets s1 and s2 to give a (possibly) new intrinsic set s3.

Parameters

s1 – First set corresponding to a vertex in the IG.
s2 – Second set corresponding to a vertex in the IG.

Returns

None.

ananke.graphs.missing_admg

Class for missing data acyclic directed mixed graphs

class ananke.graphs.missing_admg.MissingADMG(vertices=[], di_edges={}, bi_edges={}, **kwargs)[source]

Bases: ananke.graphs.admg.ADMG

draw(direction=None)[source]

Visualize the graph.

:return : dot language representation of the graph.

ananke.graphs.sg

Class for segregated graphs (SGs).

class ananke.graphs.sg.SG(vertices=[], di_edges={}, bi_edges={}, ud_edges={}, **kwargs)[source]

Bases: ananke.graphs.graph.Graph

add_biedge(sib1, sib2, recompute=True)[source]

Add a bidirected edge to the graph. Overridden to recompute districts.

Parameters

sib1 – endpoint 1 of edge.
sib2 – endpoint 2 of edge.
recompute – boolean indicating whether districts should be recomputed.

Returns

None.

add_udedge(neb1, neb2, recompute=True)[source]

Add an undirected edge to the graph. Overridden to recompute blocks

Parameters

neb1 – endpoint 1 of edge.
neb2 – endpoint 2 of edge.
recompute – boolean indicating whether blocks should be recomputed.

Returns

None.

block(vertex)[source]

Returns the block of a vertex.

Parameters: vertex – name of the vertex.
Returns: set corresponding to block.

property blocks

Returns list of all blocks in the graph.

Returns: list of sets corresponding to blocks in the graph.

delete_biedge(sib1, sib2, recompute=True)[source]

Delete given bidirected edge from the graph. Overridden to recompute districts.

Parameters

sib1 – endpoint 1 of edge.
sib2 – endpoint 2 of edge.
recompute – boolean indicating whether districts should be recomputed.

Returns

None.

delete_udedge(neb1, neb2, recompute=True)[source]

Delete given undirected edge from the graph. Overridden to recompute blocks.

Parameters

neb1 – endpoint 1 of edge.
neb2 – endpoint 2 of edge.
recompute – boolean indicating whether blocks should be recomputed.

Returns

None.

district(vertex)[source]

Returns the district of a vertex.

Parameters: vertex – name of the vertex.
Returns: set corresponding to district.

property districts

Returns list of all districts in the graph.

Returns: list of sets corresponding to districts in the graph.

fix(vertices)[source]

Perform the graphical operation of fixing on a set of vertices.

Does not check that vertices are fixable.

Parameters: vertices – iterable of vertices to be fixed.
Returns: None.

fixable(vertices)[source]

Check if there exists a valid fixing order and return such an order in the form of a list, else returns an empty list.

Parameters: vertices – set of vertices to check fixability for.
Returns: a boolean indicating whether the set was fixable and a valid fixing order as a stack.

ananke.graphs.ug

Class for Undirected Graphs (UGs).

class ananke.graphs.ug.UG(vertices=[], ud_edges={}, **kwargs)[source]: Bases: ananke.graphs.cg.CG

ananke.graphs.vertex

Class to represent vertex of a graphical model.

The vertex class should be general enough to fit into any kind of graphical model – UGs, DAGs, CGs, ADMGs, CPDAGs, CADMGs etc.

class ananke.graphs.vertex.Vertex(name, fixed=False, cardinality=2, attributes=None)[source]: Bases: object