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

fix(vertices)[source]

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

Parameters:vertices – name(s) 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.
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
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.
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.

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

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

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

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

Bases: object

Module contents