The AnnotatedGraph class

class refcycle.annotated_graph.AnnotatedGraph(vertices, edges)

A directed graph whose vertices and edges carry annotations.

The vertices and edges are instances of AnnotatedVertex and AnnotatedEdge respectively. Each such vertex or edge has both an integral id and a string annotation.

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.

property edges

Return collection of edges of the graph.

export_image(filename='refcycle.png', format=None, dot_executable='dot')

Export graph as an image.

This requires that Graphviz is installed and that the dot executable is in your path.

The filename argument specifies the output filename.

The format argument lets you specify the output format. It may be any format that dot understands, including extended format specifications like png:cairo. If omitted, the filename extension will be used; if no filename extension is present, png will be used.

The dot_executable argument lets you provide a full path to the dot executable if necessary.

export_json(filename)

Export graph in JSON form to the given file.

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.

classmethod from_json(json_graph)

Reconstruct the graph from a graph exported to JSON.

full_subgraph(vertices)

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

head(edge)

Return the head of the given edge.

classmethod import_json(filename)

Import graph from the given file. The file is expected to contain UTF-8 encoded JSON data.

in_edges(vertex)

Return a list of the edges entering this vertex.

out_edges(vertex)

Return a list of the edges leaving this 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.

tail(edge)

Return the tail of the given edge.

to_dot()

Produce a graph in DOT format.

to_json()

Convert to a JSON string.

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.

property vertices

Return collection of vertices of the graph.