def _contains_cycle(fgraph, orderings):
    # These are lists of Variable instances
    outputs = fgraph.outputs

    # this is hard-coded reimplementation of functions from graph.py
    # reason: go faster, prepare for port to C.
    # specifically, it could be replaced with a wrapper
    # around graph.io_toposort that returns True iff io_toposort raises
    # a ValueError containing the substring 'cycle'.
    # This implementation is optimized for the destroyhandler and runs
    # slightly faster than io_toposort.

    # this is performance-critical code. it is the largest single-function
    # bottleneck when compiling large graphs.
    assert isinstance(outputs, (tuple, list, deque))

    # TODO: For more speed - use a defaultdict for the orderings
    # (defaultdict runs faster than dict in the case where the key
    # is not in the dictionary, at least in CPython)

    # IG: I tried converting parent_counts to use an id for the key,
    # so that the dict would do reference counting on its keys.
    # This caused a slowdown.
    # Separate benchmark tests showed that calling id is about
    # half as expensive as a dictionary access, and that the
    # dictionary also runs slower when storing ids than when
    # storing objects.

    # dict mapping an Apply or Variable instance to the number
    # of its parents (including parents imposed by orderings)
    # that haven't been visited yet
    parent_counts = {}
    # dict mapping an Apply or Variable instance to its children
    node_to_children = {}

    # visitable: A container holding all Variable and Apply instances
    # that can currently be visited according to the graph topology
    # (ie, whose parents have already been visited)
    # TODO: visitable is a fifo_queue. could this run faster if we
    # implement it as a stack rather than a deque?
    # TODO: visitable need not be a fifo_queue, any kind of container
    # that we can throw things into and take things out of quickly will
    # work. is there another kind of container that could run faster?
    # we don't care about the traversal order here as much as we do
    # in io_toposort because we aren't trying to generate an ordering
    # on the nodes
    visitable = deque()

    # IG: visitable could in principle be initialized to fgraph.inputs
    #     + fgraph.orphans... if there were an fgraph.orphans structure.
    #     I tried making one and maintaining it caused a huge slowdown.
    #     This may be because I made it a list, so it would have a
    #     deterministic iteration order, in hopes of using it to speed
    #     up toposort as well.
    #     I think since we need to scan through all variables and nodes
    #     to make parent_counts anyway, it's cheap enough to always
    #     detect orphans at cycle detection / toposort time

    # Pass through all the nodes to build visitable, parent_count, and
    # node_to_children
    for var in fgraph.variables:

        # this is faster than calling get_parents
        owner = var.owner
        # variables don't appear in orderings, so we don't need to worry
        # about that here
        if owner:
            # insert node in node_to_children[r]
            # (if r is not already in node_to_children,
            # intialize it to [])
            node_to_children.setdefault(owner, []).append(var)
            parent_counts[var] = 1
        else:
            visitable.append(var)
            parent_counts[var] = 0

    for a_n in fgraph.apply_nodes:
        parents = list(a_n.inputs)
        # This is faster than conditionally extending
        # IG: I tried using a shared empty_list = [] constructed
        # outside of the for loop to avoid constructing multiple
        # lists, but this was not any faster.
        parents.extend(orderings.get(a_n, []))

        if parents:
            for parent in parents:
                # insert node in node_to_children[r]
                # (if r is not already in node_to_children,
                # intialize it to [])
                node_to_children.setdefault(parent, []).append(a_n)
            parent_counts[a_n] = len(parents)
        else:
            # an Apply with no inputs would be a weird case, but I'm
            # not sure we forbid it
            visitable.append(a_n)
            parent_counts[a_n] = 0

    # at this point,
    # parent_counts.keys() == fgraph.apply_nodes + fgraph.variables

    # Now we actually check for cycles
    # As long as there are nodes that can be visited while respecting
    # the topology, we keep visiting nodes
    # If we run out of visitable nodes and we haven't visited all nodes,
    # then there was a cycle. It blocked the traversal because some
    # node couldn't be visited until one of its descendants had been
    # visited too.
    # This is a standard cycle detection algorithm.

    visited = 0
    while visitable:
        # Since each node is inserted into the visitable queue exactly
        # once, it comes out of the queue exactly once
        # That means we can decrement its children's unvisited parent count
        # and increment the visited node count without double-counting
        node = visitable.popleft()
        visited += 1
        for client in node_to_children.get(node, []):
            parent_counts[client] -= 1
            # If all of a node's parents have been visited,
            # it may now be visited too
            if not parent_counts[client]:
                visitable.append(client)

    return visited != len(parent_counts)
Parameters
dataset/ETHPy150Open rizar/attention-lvcsr/libs/Theano/theano/gof/destroyhandler.py/_contains_cycle