the node this class is augmenting number of predecessors generally 0 when this value falls to 0 and is returned by getready this is set to nodeout and when the node is marked done by a call to done set to nodedone list of successor nodes the list can contain duplicated elements as long as they re all reflected in the successor s npredecessors attribute subclass of valueerror raised by topologicalsorter prepare if cycles exist in the working graph if multiple cycles exist only one undefined choice among them will be reported and included in the exception the detected cycle can be accessed via the second element in the args attribute of the exception instance and consists in a list of nodes such that each node is in the graph an immediate predecessor of the next node in the list in the reported list the first and the last node will be the same to make it clear that it is cyclic provides functionality to topologically sort a graph of hashable nodes def initself graphnone self node2info self readynodes none self npassedout 0 self nfinished 0 if graph is not none for node predecessors in graph items self addnode predecessors def getnodeinfoself node if result self node2info getnode is none self node2infonode result nodeinfonode return result def addself node predecessors if self readynodes is not none raise valueerrornodes cannot be added after a call to prepare create the node predecessor edges nodeinfo self getnodeinfonode nodeinfo npredecessors lenpredecessors create the predecessor node edges for pred in predecessors predinfo self getnodeinfopred predinfo successors appendnode def prepareself if self readynodes is not none raise valueerrorcannot prepare more than once self readynodes i node for i in self node2info values if i npredecessors 0 readynodes is set before we look for cycles on purpose if the user wants to catch the cycleerror that s fine they can continue using the instance to grab as many nodes as possible before cycles block more progress cycle self findcycle if cycle raise cycleerrorfnodes are in a cycle cycle def getreadyself if self readynodes is none raise valueerrorprepare must be called first get the nodes that are ready and mark them result tupleself readynodes n2i self node2info for node in result n2inode npredecessors nodeout clean the list of nodes that are ready and update the counter of nodes that we have returned self readynodes clear self npassedout lenresult return result def isactiveself if self readynodes is none raise valueerrorprepare must be called first return self nfinished self npassedout or boolself readynodes def boolself return self isactive def doneself nodes if self readynodes is none raise valueerrorprepare must be called first n2i self node2info for node in nodes check if we know about this node it was added previously using add if nodeinfo n2i getnode is none raise valueerrorfnode node r was not added using add if the node has not being returned marked as ready previously inform the user stat nodeinfo npredecessors if stat nodeout if stat 0 raise valueerror fnode node r was not passed out still not ready elif stat nodedone raise valueerrorfnode node r was already marked done else assert false fnode node r unknown status stat mark the node as processed nodeinfo npredecessors nodedone go to all the successors and reduce the number of predecessors collecting all the ones that are ready to be returned in the next getready call for successor in nodeinfo successors successorinfo n2isuccessor successorinfo npredecessors 1 if successorinfo npredecessors 0 self readynodes appendsuccessor self nfinished 1 def findcycleself n2i self node2info stack itstack seen set node2stacki for node in n2i if node in seen continue while true if node in seen if we have seen already the node and is in the current stack we have found a cycle if node in node2stacki return stacknode2stackinode node else go on to get next successor else seen addnode itstack appenditern2inode successors next node2stackinode lenstack stack appendnode backtrack to the topmost stack entry with at least another successor while stack try node itstack1 break except stopiteration del node2stackistack pop itstack pop else break return none def staticorderself self prepare while self isactive nodegroup self getready yield from nodegroup self donenodegroup classgetitem classmethodgenericalias the node this class is augmenting number of predecessors generally 0 when this value falls to 0 and is returned by get_ready this is set to _node_out and when the node is marked done by a call to done set to _node_done list of successor nodes the list can contain duplicated elements as long as they re all reflected in the successor s npredecessors attribute subclass of valueerror raised by topologicalsorter prepare if cycles exist in the working graph if multiple cycles exist only one undefined choice among them will be reported and included in the exception the detected cycle can be accessed via the second element in the args attribute of the exception instance and consists in a list of nodes such that each node is in the graph an immediate predecessor of the next node in the list in the reported list the first and the last node will be the same to make it clear that it is cyclic provides functionality to topologically sort a graph of hashable nodes add a new node and its predecessors to the graph both the node and all elements in predecessors must be hashable if called multiple times with the same node argument the set of dependencies will be the union of all dependencies passed in it is possible to add a node with no dependencies predecessors is not provided as well as provide a dependency twice if a node that has not been provided before is included among predecessors it will be automatically added to the graph with no predecessors of its own raises valueerror if called after prepare create the node predecessor edges create the predecessor node edges mark the graph as finished and check for cycles in the graph if any cycle is detected cycleerror will be raised but get_ready can still be used to obtain as many nodes as possible until cycles block more progress after a call to this function the graph cannot be modified and therefore no more nodes can be added using add ready_nodes is set before we look for cycles on purpose if the user wants to catch the cycleerror that s fine they can continue using the instance to grab as many nodes as possible before cycles block more progress return a tuple of all the nodes that are ready initially it returns all nodes with no predecessors once those are marked as processed by calling done further calls will return all new nodes that have all their predecessors already processed once no more progress can be made empty tuples are returned raises valueerror if called without calling prepare previously get the nodes that are ready and mark them clean the list of nodes that are ready and update the counter of nodes that we have returned return true if more progress can be made and false otherwise progress can be made if cycles do not block the resolution and either there are still nodes ready that haven t yet been returned by get_ready or the number of nodes marked done is less than the number that have been returned by get_ready raises valueerror if called without calling prepare previously marks a set of nodes returned by get_ready as processed this method unblocks any successor of each node in nodes for being returned in the future by a call to get_ready raises exec valueerror if any node in nodes has already been marked as processed by a previous call to this method if a node was not added to the graph by using add or if called without calling prepare previously or if node has not yet been returned by get_ready check if we know about this node it was added previously using add if the node has not being returned marked as ready previously inform the user mark the node as processed go to all the successors and reduce the number of predecessors collecting all the ones that are ready to be returned in the next get_ready call if we have seen already the node and is in the current stack we have found a cycle else go on to get next successor backtrack to the topmost stack entry with at least another successor returns an iterable of nodes in a topological order the particular order that is returned may depend on the specific order in which the items were inserted in the graph using this method does not require to call prepare or done if any cycle is detected exc cycleerror will be raised
from types import GenericAlias

__all__ = ["TopologicalSorter", "CycleError"]

_NODE_OUT = -1
_NODE_DONE = -2


class _NodeInfo:
    __slots__ = "node", "npredecessors", "successors"

    def __init__(self, node):
        
        self.node = node
        self.npredecessors = 0
        self.successors = []


class CycleError(ValueError):
    
    pass


class TopologicalSorter:
    

    def __init__(self, graph=None):
        self._node2info = {}
        self._ready_nodes = None
        self._npassedout = 0
        self._nfinished = 0

        if graph is not None:
            for node, predecessors in graph.items():
                self.add(node, *predecessors)

    def _get_nodeinfo(self, node):
        if (result := self._node2info.get(node)) is None:
            self._node2info[node] = result = _NodeInfo(node)
        return result

    def add(self, node, *predecessors):
        
        if self._ready_nodes is not None:
            raise ValueError("Nodes cannot be added after a call to prepare()")

        
        nodeinfo = self._get_nodeinfo(node)
        nodeinfo.npredecessors += len(predecessors)

        
        for pred in predecessors:
            pred_info = self._get_nodeinfo(pred)
            pred_info.successors.append(node)

    def prepare(self):
        
        if self._ready_nodes is not None:
            raise ValueError("cannot prepare() more than once")

        self._ready_nodes = [
            i.node for i in self._node2info.values() if i.npredecessors == 0
        ]
        
        cycle = self._find_cycle()
        if cycle:
            raise CycleError(f"nodes are in a cycle", cycle)

    def get_ready(self):
        
        if self._ready_nodes is None:
            raise ValueError("prepare() must be called first")

        
        result = tuple(self._ready_nodes)
        n2i = self._node2info
        for node in result:
            n2i[node].npredecessors = _NODE_OUT

        
        
        self._ready_nodes.clear()
        self._npassedout += len(result)

        return result

    def is_active(self):
        
        if self._ready_nodes is None:
            raise ValueError("prepare() must be called first")
        return self._nfinished < self._npassedout or bool(self._ready_nodes)

    def __bool__(self):
        return self.is_active()

    def done(self, *nodes):
        

        if self._ready_nodes is None:
            raise ValueError("prepare() must be called first")

        n2i = self._node2info

        for node in nodes:

            
            if (nodeinfo := n2i.get(node)) is None:
                raise ValueError(f"node {node!r} was not added using add()")

            
            stat = nodeinfo.npredecessors
            if stat != _NODE_OUT:
                if stat >= 0:
                    raise ValueError(
                        f"node {node!r} was not passed out (still not ready)"
                    )
                elif stat == _NODE_DONE:
                    raise ValueError(f"node {node!r} was already marked done")
                else:
                    assert False, f"node {node!r}: unknown status {stat}"

            
            nodeinfo.npredecessors = _NODE_DONE

            
            
            for successor in nodeinfo.successors:
                successor_info = n2i[successor]
                successor_info.npredecessors -= 1
                if successor_info.npredecessors == 0:
                    self._ready_nodes.append(successor)
            self._nfinished += 1

    def _find_cycle(self):
        n2i = self._node2info
        stack = []
        itstack = []
        seen = set()
        node2stacki = {}

        for node in n2i:
            if node in seen:
                continue

            while True:
                if node in seen:
                    
                    
                    if node in node2stacki:
                        return stack[node2stacki[node] :] + [node]
                    
                else:
                    seen.add(node)
                    itstack.append(iter(n2i[node].successors).__next__)
                    node2stacki[node] = len(stack)
                    stack.append(node)

                
                
                while stack:
                    try:
                        node = itstack[-1]()
                        break
                    except StopIteration:
                        del node2stacki[stack.pop()]
                        itstack.pop()
                else:
                    break
        return None

    def static_order(self):
        
        self.prepare()
        while self.is_active():
            node_group = self.get_ready()
            yield from node_group
            self.done(*node_group)

    __class_getitem__ = classmethod(GenericAlias)