DAGraph¶

class imgreg.util.graph.DAGraph(vertex_parent_dict: Dict[Hashable, Set[Hashable]], invert=False)[source]¶

Bases: object

Collection of functions for directed acyclic graphs.

This class implements functions for directed acyclic graphs 1 2. The graph is stored in a dictionary, where the keys define the identifiers for the vertices and the value contains the set of parents. This implementation is motivated for handling generic problems where dependencies appear (see dependency graphs 3).

This module is for experimental use only, more extensive graph libraries for python are available under 5 6 7 8.

Parameters

vertex_parent_dictdict[str, set[Hashable]]: A dictionary mapping each vertex to all of its parents. It is assumed, that the input is a directed acyclic graph (connected or disconnected). Cycle Detection is not performed on the input.
invertboolean: invert the edges of the input graph

Notes

A directed graph is an ordered pair $G=\left(V,E\right)$ , where

$V$ is a set of vertices (also nodes or points)
$E\subseteq\left\{ (x,y)\mid(x,y)\in V^{2}\;\textrm{ and }\;x\neq y\right\}$ is a set of ordered pairs of vertices called edges.

To represent a graph, DAGraph takes a single python dictionary as input, where $\mathtt{key},\,parent\in V$ and

$\mathtt{value}=pa\left(\mathtt{key}\right)=\left\{ \left\{ parent\right\} | \left(\mathtt{key},parent\right)\in E\right\}$

References

Methods

`__init__`(vertex_parent_dict[, invert])	Initialize self.
`ascendants`(vertex)	Given vertex, return a set containing all its ascendants 4.
`children`(vertex[, order])	Given vertex, return a set containing all its children.
`descendants`(vertex)	Given vertex, return a set containing all descendants 4.
`parents`(vertex[, order])	Given vertex, return a set containing all its parents.

Attributes

`vertex_ascendants_dict`	Get a dictionary mapping each vertex to all of its ascendants 4.
`vertex_parent_dict`	Get a dictionary mapping each vertex to all of its parents.

ascendants(vertex: Hashable) → Set[Hashable][source]¶

Given vertex, return a set containing all its ascendants 4.

Returns

Set: Set of ascendants

children(vertex: Hashable, order: int = 1) → Set[Hashable][source]¶

Given vertex, return a set containing all its children.

Returns

Set: Set of children

descendants(vertex: Hashable) → Set[Hashable][source]¶

Given vertex, return a set containing all descendants 4.

Returns

Set: Set of descendants

parents(vertex: Hashable, order=1) → Set[Hashable][source]¶

Given vertex, return a set containing all its parents.

Returns

Set: Set of parent

property vertex_ascendants_dict¶

Get a dictionary mapping each vertex to all of its ascendants 4.

Returns

dict: vertex : Set of vertices

property vertex_parent_dict¶

Get a dictionary mapping each vertex to all of its parents.

Returns

dict: vertex : Set of vertices