utils.graph

Dependency graph implementation.

Module Contents

Classes

DOT() Constants related to the dot format.
CycleError() A cycle was detected in an acyclic graph.
DependencyGraph(self,it=None,formatter=None) A directed acyclic graph of objects and their dependencies.
GraphFormatter(self,root=None,type=None,id=None,indent=0,inw=None,**scheme) Format dependency graphs.
class DOT

Constants related to the dot format.

class CycleError

A cycle was detected in an acyclic graph.

class DependencyGraph(it=None, formatter=None)

A directed acyclic graph of objects and their dependencies.

Supports a robust topological sort to detect the order in which they must be handled.

Takes an optional iterator of (obj, dependencies) tuples to build the graph from.

Warning:
Does not support cycle detection.
__init__(it=None, formatter=None)
add_arc(obj)

Add an object to the graph.

add_edge(A, B)

Add an edge from object A to object B.

I.e. A depends on B.

connect(graph)

Add nodes from another graph.

topsort()

Sort the graph topologically.

Returns:
List: of objects in the order in which they must be handled.
valency_of(obj)

Return the valency (degree) of a vertex in the graph.

update(it)

Update graph with data from a list of (obj, deps) tuples.

edges()

Return generator that yields for all edges in the graph.

_khan62()

Perform Khan’s simple topological sort algorithm from ‘62.

See https://en.wikipedia.org/wiki/Topological_sorting

_tarjan72()

Perform Tarjan’s algorithm to find strongly connected components.

See Also:
:wikipedia:`Tarjan%27s_strongly_connected_components_algorithm`
to_dot(fh, formatter=None)

Convert the graph to DOT format.

Arguments:

fh (IO): A file, or a file-like object to write the graph to. formatter (celery.utils.graph.GraphFormatter): Custom graph

formatter to use.
format(obj)
__iter__()
__getitem__(node)
__len__()
__contains__(obj)
_iterate_items()
__repr__()
repr_node(obj, level=1, fmt="{0}({1})")
class GraphFormatter(root=None, type=None, id=None, indent=0, inw=None, **scheme)

Format dependency graphs.

__init__(root=None, type=None, id=None, indent=0, inw=None, **scheme)
attr(name, value)
attrs(d, scheme=None)
head(**attrs)
tail()
label(obj)
node(obj, **attrs)
terminal_node(obj, **attrs)
edge(a, b, **attrs)
_enc(s)
FMT(fmt, *args, **kwargs)
draw_edge(a, b, scheme=None, attrs=None)
draw_node(obj, scheme=None, attrs=None)