graphlib — Functionality to operate with graph-like structures¶

Source code:Lib/graphlib.py

classgraphlib.TopologicalSorter(graph=None)¶

Provides functionality to topologically sort a graph ofhashable nodes.

A topological order is a linear ordering of the vertices in a graph such thatfor every directed edge u -> v from vertex u to vertex v, vertex u comesbefore vertex v in the ordering. For instance, the vertices of the graph mayrepresent tasks to be performed, and the edges may represent constraints thatone task must be performed before another; in this example, a topologicalordering is just a valid sequence for the tasks. A complete topologicalordering is possible if and only if the graph has no directed cycles, thatis, if it is a directed acyclic graph.

If the optionalgraph argument is provided it must be a dictionaryrepresenting a directed acyclic graph where the keys are nodes and the valuesare iterables of all predecessors of that node in the graph (the nodes thathave edges that point to the value in the key). Additional nodes can be addedto the graph using theadd() method.

In the general case, the steps required to perform the sorting of a givengraph are as follows:

• Create an instance of theTopologicalSorter with an optionalinitial graph.

• Add additional nodes to the graph.

• Callprepare() on the graph.

• Whileis_active() isTrue, iterate overthe nodes returned byget_ready() andprocess them. Calldone() on each node as itfinishes processing.

In case just an immediate sorting of the nodes in the graph is required andno parallelism is involved, the convenience methodTopologicalSorter.static_order() can be used directly:

>>>graph={"D":{"B","C"},"C":{"A"},"B":{"A"}}>>>ts=TopologicalSorter(graph)>>>tuple(ts.static_order())('A', 'C', 'B', 'D')

The class is designed to easily support parallel processing of the nodes asthey become ready. For instance:

topological_sorter=TopologicalSorter()# Add nodes to 'topological_sorter'...topological_sorter.prepare()whiletopological_sorter.is_active():fornodeintopological_sorter.get_ready():# Worker threads or processes take nodes to work on off the# 'task_queue' queue.task_queue.put(node)# When the work for a node is done, workers put the node in# 'finalized_tasks_queue' so we can get more nodes to work on.# The definition of 'is_active()' guarantees that, at this point, at# least one node has been placed on 'task_queue' that hasn't yet# been passed to 'done()', so this blocking 'get()' must (eventually)# succeed.  After calling 'done()', we loop back to call 'get_ready()'# again, so put newly freed nodes on 'task_queue' as soon as# logically possible.node=finalized_tasks_queue.get()topological_sorter.done(node)

add(node,*predecessors)¶

Add a new node and its predecessors to the graph. Both thenode and allelements inpredecessors must behashable.

If called multiple times with the same node argument, the set ofdependencies will be the union of all dependencies passed in.

It is possible to add a node with no dependencies (predecessors is notprovided) or to provide a dependency twice. If a node that has not beenprovided before is included amongpredecessors it will be automaticallyadded to the graph with no predecessors of its own.

RaisesValueError if called afterprepare().

prepare()¶

Mark the graph as finished and check for cycles in the graph. If any cycleis detected,CycleError will be raised, butget_ready() can still be used to obtain as manynodes as possible until cycles block more progress. After a call to thisfunction, the graph cannot be modified, and therefore no more nodes can beadded usingadd().

AValueError will be raised if the sort has been started bystatic_order() orget_ready().

Changed in version 3.14:prepare() can now be called more than once as long as the sort hasnot started. Previously this raisedValueError.

is_active()¶

ReturnsTrue if more progress can be made andFalse otherwise.Progress can be made if cycles do not block the resolution and eitherthere are still nodes ready that haven’t yet been returned byTopologicalSorter.get_ready() or the number of nodes markedTopologicalSorter.done() is less than the number that have beenreturned byTopologicalSorter.get_ready().

The__bool__() method of this class defers tothis function, so instead of:

ifts.is_active():...

it is possible to simply do:

ifts:...

RaisesValueError if called without callingprepare() previously.

done(*nodes)¶

Marks a set of nodes returned byTopologicalSorter.get_ready() asprocessed, unblocking any successor of each node innodes for beingreturned in the future by a call toTopologicalSorter.get_ready().

RaisesValueError if any node innodes has already been marked asprocessed by a previous call to this method or if a node was not added tothe graph by usingTopologicalSorter.add(), if called withoutcallingprepare() or if node has not yet beenreturned byget_ready().

get_ready()¶

Returns atuple with all the nodes that are ready. Initially itreturns all nodes with no predecessors, and once those are marked asprocessed by callingTopologicalSorter.done(), further calls willreturn all new nodes that have all their predecessors already processed.Once no more progress can be made, empty tuples are returned.

RaisesValueError if called without callingprepare() previously.

static_order()¶

Returns an iterator object which will iterate over nodes in a topologicalorder. When using this method,prepare() anddone() should not be called. This method isequivalent to:

defstatic_order(self):self.prepare()whileself.is_active():node_group=self.get_ready()yield fromnode_groupself.done(*node_group)

The particular order that is returned may depend on the specific order inwhich the items were inserted in the graph. For example:

>>>ts=TopologicalSorter()>>>ts.add(3,2,1)>>>ts.add(1,0)>>>print([*ts.static_order()])[2, 0, 1, 3]>>>ts2=TopologicalSorter()>>>ts2.add(1,0)>>>ts2.add(3,2,1)>>>print([*ts2.static_order()])[0, 2, 1, 3]

This is due to the fact that “0” and “2” are in the same level in thegraph (they would have been returned in the same call toget_ready()) and the order between them isdetermined by the order of insertion.

If any cycle is detected,CycleError will be raised.

Added in version 3.9.