ananke.graphs package

Submodules

ananke.graphs.admg module

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).

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]

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.

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 module

Class for Bidirected Graphs (BGs).

class ananke.graphs.bg.BG(vertices=[], bi_edges={}, **kwargs)[source]

Bases: ananke.graphs.admg.ADMG

ananke.graphs.cg module

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 module

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 module

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)[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.

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 module

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 module

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 module

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.

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 module

Class for Undirected Graphs (UGs).

class ananke.graphs.ug.UG(vertices=[], ud_edges={}, **kwargs)[source]

Bases: ananke.graphs.cg.CG

ananke.graphs.vertex module

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

Module contents