The ObjectGraph class

class refcycle.object_graph.ObjectGraph(objects=())[source]

Directed graph representing a collection of Python objects and the references between them.

An ObjectGraph can be constructed directly from an existing iterable collection of objects:

>>> from refcycle import ObjectGraph
>>> inner = [1, 2, 3]
>>> outer = [inner] * 3
>>> graph = ObjectGraph([outer, inner])
>>> graph
<refcycle.object_graph.ObjectGraph object of size 2 at 0x100470ed0>

This constructs a graph whose vertices are the two Python objects inner and outer. All references between the given objects are automatically added as graph edges.

The ObjectGraph acts as a container for those objects, much like a set:

>>> inner in graph
True
>>> 2 in graph
False
>>> len(graph)
2
>>> list(graph)
[[[1, 2, 3], [1, 2, 3], [1, 2, 3]], [1, 2, 3]]

We can find the referrers and referents of any particular object in the graph using the parents and children methods.

>>> graph.children(outer)
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]

Here we see inner occurring three times as a child of outer, because there are three distinct references from outer to inner.

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.

annotated()[source]

Annotate this graph, returning an AnnotatedGraph object with the same structure.

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.

count_by_typename()[source]

Classify objects by type name.

Returns a collections.Counter instance mapping type names to the number of objects obj in this graph for which type(obj).__name__ matches that type name.

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')[source]

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)[source]

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.

find_by_typename(typename)[source]

List of all objects whose type has the given name.

full_subgraph(objects)[source]

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)[source]

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

in_edges(vertex)[source]

Return a list of the edges entering this vertex.

out_edges(vertex)[source]

Return a list of the edges leaving this vertex.

owned_objects()[source]

List of gc-tracked objects owned by this ObjectGraph instance.

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)[source]

Return the tail (source) of the given edge.

to_dot()[source]

Produce a graph in DOT format.

to_json()[source]

Convert to a JSON string.

classmethod vertex_dict()[source]

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)[source]

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()[source]

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.