The IDirectedGraph abstract base class

class refcycle.i_directed_graph.IDirectedGraph

Abstract base class for directed graphs.

ancestors(start, generations=None)

Return the subgraph of all nodes from which the given vertex is reachable, including that vertex.

If specified, the optional generations argument specifies how many generations to limit to.

children(vertex)

Return the list of immediate children of the given vertex.

count_by(classifier)

Return a count of objects using the given classifier.

Here classifier should be a callable that accepts a single object from the graph and returns the “class” of that object, which should be a hashable value.

Returns a collections.Counter instance mapping classes to counts.

descendants(start, generations=None)

Return the subgraph of all nodes reachable from the given start vertex, including that vertex.

If specified, the optional generations argument specifies how many generations to limit to.

abstract property edges

Return a collection of the edges of the graph. The collection should support iteration and rapid containment testing.

find_by(predicate)

Return a list of all objects satisfying the given predicate.

Here predicate should be a callable that accepts a single object from the graph and returns a value that can be interpreted as a boolean.

abstract property full_subgraph

Return the subgraph of this graph whose vertices are the given ones and whose edges are all the edges of the original graph between those vertices.

abstract head(edge)

Return the head (target, destination) of the given edge.

abstract in_edges(vertex)

Return an iterable of the edges entering the given vertex.

abstract out_edges(vertex)

Return an iterable of the edges leaving the given vertex.

parents(vertex)

Return the list of immediate parents of this vertex.

references()

Return (tail, head) pairs for each edge in the graph.

shortest_cycle(start)

Find a shortest cycle including start.

Returns the subgraph consisting of the vertices in that cycle and (all) the edges between them.

Raises ValueError if no cycle including start exists.

shortest_path(start, end)

Find a shortest path from start to end.

Returns the subgraph consisting of the vertices in that path and (all) the edges between them.

Raises ValueError if no path from start to end exists.

source_components()

Return the strongly connected components not reachable from any other component. Any component in the graph is reachable from one of these.

strongly_connected_components()

Return list of strongly connected components of this graph.

Returns a list of subgraphs.

Algorithm is based on that described in “Path-based depth-first search for strong and biconnected components” by Harold N. Gabow, Inf.Process.Lett. 74 (2000) 107–114.

abstract tail(edge)

Return the tail (source) of the given edge.

classmethod vertex_dict()

Return an empty mapping whose keys are vertices.

Usually a plain dict is good enough; for the ObjectGraph we’ll override to use KeyTransformDict instead.

classmethod vertex_equal(vertex1, vertex2)

Criterion to use to determine whether two vertices are equal.

Usually we want to use simple equality here, but the for the ObjectGraph we’ll need to use identity.

classmethod vertex_set()

Return an empty object suitable for storing a set of vertices.

Usually a plain set will suffice, but for the ObjectGraph we’ll use an ElementTransformSet instead.

abstract property vertices

Return a collection of the vertices of the graph. The collection should support iteration and rapid containment testing.