Python networkx 模块，find_cycle() 实例源码

def order_build(graph):
    '''
    Assumes that packages are in graph.
    Builds a temporary graph of relevant nodes and returns it topological sort.

    Relevant nodes selected in a breadth first traversal sourced at each pkg
    in packages.
    '''
    reorder_cyclical_test_dependencies(graph)
    try:
        order = nx.topological_sort(graph, reverse=True)
    except nx.exception.NetworkXUnfeasible:
        raise ValueError("Cycles detected in graph: %s", nx.find_cycle(graph,
                                                                       orientation='reverse'))

    return order

def order_build(graph, packages=None, level=0, filter_dirty=True):
    '''
    Assumes that packages are in graph.
    Builds a temporary graph of relevant nodes and returns it topological sort.

    Relevant nodes selected in a breadth first traversal sourced at each pkg
    in packages.

    Values expected for packages is one of None, sequence:
       None: build the whole graph
       empty sequence: build nodes marked dirty
       non-empty sequence: build nodes in sequence
    '''

    if not packages:
        packages = graph.nodes()
        if filter_dirty:
            packages = dirty(graph)
    tmp_global = graph.subgraph(packages)

    # copy relevant node data to tmp_global
    for n in tmp_global.nodes_iter():
        tmp_global.node[n] = graph.node[n]

    try:
        order = nx.topological_sort(tmp_global, reverse=True)
    except nx.exception.NetworkXUnfeasible:
        raise ValueError("Cycles detected in graph: {0}".format(nx.find_cycle(tmp_global,
                                                                       orientation='ignore')))

    return tmp_global, order

def would_cause_cycle(e, u, v, reverse=False):
    """
    Test if adding the edge u -> v to the BayesNet
    object would create a DIRECTED (i.e. illegal) cycle.
    """
    G = nx.DiGraph(e)
    if reverse:
        G.remove_edge(v,u)
    G.add_edge(u,v)
    try:
        nx.find_cycle(G, source=u)
        return True
    except:
        return False

def get_cycle(self):
        try:
            return nx.find_cycle(self.graph)
        except:
            return []

def circular_dependencies(self):
        try:
            return nx.find_cycle(self)
        except Exception:
            # if there is no cycle, an exception is given
            return []