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
- 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.
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
ananke.graphs.dag
Class for Directed Acyclic Graphs (DAGs).
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.
- 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.
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).
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
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.