创建“极小连通”有向无圈图

Question

我在NetworkX中有一个有向无圈简单图。

现在，对于每个边，该边有一个“源”和一个“目标”。如果除了这个边之外还有从“源”到“目标”的路径，那么我想删除这个边。

1. NetworkX有一个内置的函数来完成这个任务吗？

我真的不想重新发明轮子。

1. 只有在对1的答案是“否”的情况下才可选，那么实现这一目标的最有效算法是什么(对于相当稠密的图)？

下面是一个需要清理的DAG示例：

• 这些节点是： “术语序列”、“最大度”、“空图”、“最小”、“多集”、“步行”、“非空多图”、“euleriantrail”、“非空多图”、“循环”、“path”、“端点”、“简单图”、“顶点”、“多重路径”、“边”、“集”、“漫步”、“并”、“trail条件”、“nullmulti图”、“三维多图”、“序列”、“多个顶点”、“路径”、“路径”“度”、“单面顶点”、“非三维空间图”、“邻接边”、“邻接顶点”、“简单边”、“最大值”、“乘法器”、“长度”、“电路”、“类”、“euleriang相图”、“入射”、“最小度”、“ordered结对”、“唯一”、“闭边”、“多重边”、“病理条件”、“多重图”、“轨迹”
• 边缘是： (“术语序列”、“端点”)、(“空多图”、“非空多图”)、(“最小”、“最小度”)、(“多集”、“跟踪条件”)、(“多集”、“路径条件”)、(“多集”、“多图”)、(“步行”、“长度”)、(“步行”、“封闭行走”)、(“步行”、“walk”)、(“步行”、“轨迹”)、(“步行”、“端点”)，(“euleriantrail”、“euleriang相图”)、(“循环”、“单纯图”)、(“循环”、“度”)、(“循环”、“简单边”)、(“循环”、“多个顶点”)、(“顶点”、“多边”)、(“顶点”、“多边”)、(‘顶点’，‘边缘’)，(‘顶点’，‘乘法’)，(‘顶点’，‘度’)，(‘顶点’，‘事件’)，(‘边’，‘环’)，(‘边’，‘单顶点’)，(‘边’，‘多个边’)，(‘边’，‘单纯边’)，(‘边’，‘环’)，(‘边’，‘循环’，‘’边‘，’贸易条件‘)，(“边”、“路径条件”)、(“边”、“行走”)、(“边”、“事件”)、(“集”、“单点”)、(“集”、“边”)、(“并”、“乘数”)、(“并”、“多条路径”)、(“跟踪条件”、“轨迹”)、(“无空多图”、“非空多图”)、(“序列”、“行走”)、(“序列”、“端点”)，(“路”、“循环”)、(“路”、“乘数”)、(“度”、“最大度”)、(“度”、“最小度”)、(“单点”、“多个图”)、(“最大值”、“最大度”)、(“电路”、“euleriang相图”)、(“类”、“乘数”)、(“类”、“多重路径”)、(“事件”、“邻接边”)、(“事件”、“度”)、(“事件”、“单点”)、(“有序对”、“多图”)、(“闭合行走”、“电路”)、(“闭合行走”、“循环”)、(“闭合行走”、“漫步”)、(“路径”)、(“多图”、“euleriang相图”)、(“多图”、“空多图”)、(“多重图”、“三重图”)、(“多图”、“非三维多图”)、(“多图”、“空多图”)，(“多图”，“euleriantrail”)，(“多重图”，“简单图”)，(“trail”，“路”)，(“trail”，“电路”)，(“trail”，“多重路径”)

Answer 1

您可以使用nx.transitive_reduction(G)。

下面是文档中的一个示例。

DG = nx.DiGraph([(1, 2), (2, 3), (1, 3)])
TR = nx.transitive_reduction(DG)
list(TR.edges)  # [(1, 2), (2, 3)]

Answer 2

我先前的回答专门讨论了一个直接的问题，即是否有一种很好的方法来测试单个边是否是多余的。

看起来你真的想要一种有效去除所有冗余边缘的方法。这意味着你想要一次把它们都做完的方法。这是一个不同的问题，但这里有一个答案。我不认为networkx在这方面有内置的东西，但是要找到一个可行的算法并不困难。

这个想法是因为它是一个DAG，有些节点没有外边。从它们开始并处理它们。一旦全部被处理，那么他们的父母的一个子集就没有没有被处理过的孩子。去看看那些父母。重复一遍。在每个阶段，一组未处理的节点是一个DAG，我们正在处理该DAG的“结束节点”。它保证完成(如果原始网络是有限的)。

在实现中，每当我们处理节点时，我们首先检查是否有任何子节点也是间接后代。如果是的话，删除边缘。如果没有，就别管它了。当处理所有的子级时，我们通过将其所有的后代添加到父母的间接后代集合中来更新其父母的信息。如果父级的所有子级都被处理，我们现在将其添加到列表中，以便进行下一次迭代。

import networkx as nx
from collections import defaultdict

def remove_redundant_edges(G):
    processed_child_count = defaultdict(int)  #when all of a nodes children are processed, we'll add it to nodes_to_process
    descendants = defaultdict(set)            #all descendants of a node (including children)
    out_degree = {node:G.out_degree(node) for node in G.nodes_iter()}
    nodes_to_process = [node for node in G.nodes_iter() if out_degree[node]==0] #initially it's all nodes without children
    while nodes_to_process:
        next_nodes = []
        for node in nodes_to_process:
            '''when we enter this loop, the descendants of a node are known, except for direct children.'''
            for child in G.neighbors(node):
                if child in descendants[node]:  #if the child is already an indirect descendant, delete the edge
                    G.remove_edge(node,child)
                else:                                    #otherwise add it to the descendants
                    descendants[node].add(child)
            for predecessor in G.predecessors(node):             #update all parents' indirect descendants
                descendants[predecessor].update(descendants[node])  
                processed_child_count[predecessor]+=1            #we have processed one more child of this parent
                if processed_child_count[predecessor] == out_degree[predecessor]:  #if all children processed, add to list for next iteration.
                    next_nodes.append(predecessor)
        nodes_to_process=next_nodes

为了测试它：

G=nx.DiGraph()
G.add_nodes_from(['termsequence', 'maximumdegree', 'emptymultigraph', 'minimum', 'multiset', 'walk', 'nonemptymultigraph', 'euleriantrail', 'nonnullmultigraph', 'cycle', 'loop', 'abwalk', 'endvertices', 'simplegraph', 'vertex', 'multipletrails', 'edge', 'set', 'stroll', 'union', 'trailcondition', 'nullmultigraph', 'trivialmultigraph', 'sequence', 'multiplepaths', 'path', 'degreevertex', 'onedgesonvertices', 'nontrivialmultigraph', 'adjacentedges', 'adjacentvertices', 'simpleedge', 'maximum', 'multipleloops', 'length', 'circuit', 'class', 'euleriangraph', 'incident', 'minimumdegree', 'orderedpair', 'unique', 'closedwalk', 'multipleedges', 'pathcondition', 'multigraph', 'trail'])
G.add_edges_from([('termsequence', 'endvertices'), ('emptymultigraph', 'nonemptymultigraph'), ('minimum', 'minimumdegree'), ('multiset', 'trailcondition'), ('multiset', 'pathcondition'), ('multiset', 'multigraph'), ('walk', 'length'), ('walk', 'closedwalk'), ('walk', 'abwalk'), ('walk', 'trail'), ('walk', 'endvertices'), ('euleriantrail', 'euleriangraph'), ('loop', 'simplegraph'), ('loop', 'degreevertex'), ('loop', 'simpleedge'), ('loop', 'multipleloops'), ('endvertices', 'abwalk'), ('vertex', 'adjacentvertices'), ('vertex', 'onedgesonvertices'), ('vertex', 'walk'), ('vertex', 'adjacentedges'), ('vertex', 'multipleedges'), ('vertex', 'edge'), ('vertex', 'multipleloops'), ('vertex', 'degreevertex'), ('vertex', 'incident'), ('edge', 'adjacentvertices'), ('edge', 'onedgesonvertices'), ('edge', 'multipleedges'), ('edge', 'simpleedge'), ('edge', 'adjacentedges'), ('edge', 'loop'), ('edge', 'trailcondition'), ('edge', 'pathcondition'), ('edge', 'walk'), ('edge', 'incident'), ('set', 'onedgesonvertices'), ('set', 'edge'), ('union', 'multiplepaths'), ('union', 'multipletrails'), ('trailcondition', 'trail'), ('nullmultigraph', 'nonnullmultigraph'), ('sequence', 'walk'), ('sequence', 'endvertices'), ('path', 'cycle'), ('path', 'multiplepaths'), ('degreevertex', 'maximumdegree'), ('degreevertex', 'minimumdegree'), ('onedgesonvertices', 'multigraph'), ('maximum', 'maximumdegree'), ('circuit', 'euleriangraph'), ('class', 'multiplepaths'), ('class', 'multipletrails'), ('incident', 'adjacentedges'), ('incident', 'degreevertex'), ('incident', 'onedgesonvertices'), ('orderedpair', 'multigraph'), ('closedwalk', 'circuit'), ('closedwalk', 'cycle'), ('closedwalk', 'stroll'), ('pathcondition', 'path'), ('multigraph', 'euleriangraph'), ('multigraph', 'nullmultigraph'), ('multigraph', 'trivialmultigraph'), ('multigraph', 'nontrivialmultigraph'), ('multigraph', 'emptymultigraph'), ('multigraph', 'euleriantrail'), ('multigraph', 'simplegraph'), ('trail', 'path'), ('trail', 'circuit'), ('trail', 'multipletrails')])

print G.size()
>71
print G.order()
>47
descendants = {}  #for testing below
for node in G.nodes():
    descendants[node] = nx.descendants(G,node)

remove_redundant_edges(G)  #this removes the edges

print G.size()  #lots of edges gone
>56
print G.order() #no nodes changed.
>47
newdescendants = {}  #for comparison with above
for node in G.nodes():
    newdescendants[node] = nx.descendants(G,node)

for node in G.nodes():  
    if descendants[node] != newdescendants[node]:
        print 'descendants changed!!'   #all nodes have the same descendants
    for child in G.neighbors(node):  
        if len(list(nx.all_simple_paths(G,node, child)))>1:
            print 'bad edge'  #no alternate path exists from a node to its child.

这将是有效的:它必须在开始时处理每个节点，以查看它是否是一个"end“节点。然后，它处理到达这些边缘的每一条边，并检查是否已处理了该父级的所有子级。然后，它看着这些父母，并重复。

因此，它将处理每个边缘一次(包括浏览父)，每个顶点将在开始时处理一次，然后再处理一次。

Answer 3

这里有一个简单的通用算法.该算法可以向前或向后运行。这和Joel的回答本质上是双重的--他向后跑，这是向前跑：

def remove_redundant_edges(G):
    """
    Remove redundant edges from a DAG using networkx (nx).
    An edge is redundant if there is an alternate path
    from its start node to its destination node.

    This algorithm could work front to back, or back to front.
    We choose to work front to back.

    The main persistent variable (in addition to the graph
    itself) is indirect_pred_dict, which is a dictionary with
    one entry per graph node.  Each entry is a set of indirect
    predecessors of this node.

    The algorithmic complexity of the code on a worst-case
    fully-connected graph is O(V**3), where V is the number
    of nodes.
    """

    indirect_pred_dict = collections.defaultdict(set)
    for node in nx.topological_sort(G):
        indirect_pred = indirect_pred_dict[node]
        direct_pred = G.predecessors(node)
        for pred in direct_pred:
            if pred in indirect_pred:
                G.remove_edge(pred, node)
        indirect_pred.update(direct_pred)
        for succ in G.successors(node):
            indirect_pred_dict[succ] |= indirect_pred

复杂性分析与大O优化

对于最小连通图，其中每个节点只连接到单个边缘，复杂度为O(V+E)。然而，即使对于一个简单的线性图(每个节点都有一个传入边和一个输出边)，复杂度也是O(V*E)，对于最大连通图(这是最坏的情况，每个节点都连接到图上的每个下游节点)，复杂性是O(V**3)。对于这种情况，of的数目遵循序列A000292，这是n * (n+1) * (n+2) / 6，其中n是节点数(V)减去3。

根据图形的形状，还可以进行其他优化。下面是一个带有几个不同优化器的版本，这些优化器可以显着地降低某些类型图的复杂性和运行时间：

def remove_redundant_edges(G, optimize_dense=True, optimize_chains=True,
                              optimize_tree=False,  optimize_funnel=False):
    """
    Remove redundant edges from a DAG using networkx (nx).
    An edge is redundant if there is an alternate path
    from its start node to its destination node.

    This algorithm could work equally well front to back,
    or back to front. We choose to work front to back.

    The main persistent variable (in addition to the graph
    itself) is indirect_pred_dict, which is a dictionary with
    one entry per graph node.  Each entry is a set of indirect
    predecessors of this node.

    The main processing algorithm uses this dictionary to
    iteratively calculate indirect predecessors and direct
    predecessors for every node, and prune the direct
    predecessors edges if they are also accessible indirectly.
    The algorithmic complexity is O(V**3), where V is the
    number of nodes in the graph.

    There are also several graph shape-specific optimizations
    provided.  These optimizations could actually increase
    run-times, especially for small graphs that are not amenable
    to the optimizations, so if your execution time is slow,
    you should test different optimization combinations.

    But for the right graph shape, these optimizations can
    provide dramatic improvements.  For the fully connected
    graph (which is worst-case), optimize_dense reduces the
    algorithmic complexity from O(V**3) to O(V**2).

    For a completely linear graph, any of the optimize_tree,
    optimize_chains, or optimize_funnel options would decrease
    complexity from O(V**2) to O(V).

    If the optimize_dense option is set to True, then an
    optimization phase is before the main algorithm.  This
    optimization phase works by looking for matches between
    each node's successors and that same node's successor's
    successors (by only looking one level ahead at a time).

    If the optimize_tree option is set true, then a phase is
    run that will optimize trees by working right-to-left and
    recursively removing leaf nodes with a single predecessor.
    This will also optimize linear graphs, which are degenerate
    trees.

    If the optimize_funnel option is set true, then funnels
    (inverted trees) will be optimized.

    If the optimize_chains option is set true, then chains
    (linear sections) will be optimized by sharing the
    indirect_pred_dict sets.  This works because Python
    checks to see if two sets are the same instance before
    combining them.

    For a completely linear graph, optimize_funnel or optimize_tree
    execute more quickly than optimize_chains.  Nonetheless,
    optimize_chains option is enabled by default, because
    it is a balanced algorithm that works in more cases than
    the other two.
    """

    ordered = nx.topological_sort(G)

    if optimize_dense:
        succs= dict((node, set(G.successors(node))) for node in ordered)
        for node in ordered:
            my_succs = succs.pop(node)
            kill = set()
            while my_succs:
                succ = my_succs.pop()
                if succ not in kill:
                    check = succs[succ]
                    kill.update(x for x in my_succs if x in check)
            for succ in kill:
                G.remove_edge(node, succ)

    indirect_pred_dict = dict((node, set()) for node in ordered)

    if optimize_tree:
        remaining_nodes = set(ordered)
        for node in reversed(ordered):
            if G.in_degree(node) == 1:
                if not (set(G.successors(node)) & remaining_nodes):
                    remaining_nodes.remove(node)
        ordered = [node for node in ordered if node in remaining_nodes]

    if optimize_funnel:
        remaining_nodes = set(ordered)
        for node in ordered:
            if G.out_degree(node) == 1:
                if not (set(G.predecessors(node)) & remaining_nodes):
                    remaining_nodes.remove(node)
        ordered = [node for node in ordered if node in remaining_nodes]

    if optimize_chains:
        # This relies on Python optimizing the set |= operation
        # by seeing if the objects are identical.
        for node in ordered:
            succs = G.successors(node)
            if len(succs) == 1 and len(G.predecessors(succs[0])) == 1:
                indirect_pred_dict[succs[0]] = indirect_pred_dict[node]

    for node in ordered:
        indirect_pred = indirect_pred_dict.pop(node)
        direct_pred = G.predecessors(node)
        for pred in direct_pred:
            if pred in indirect_pred:
                G.remove_edge(pred, node)
        indirect_pred.update(direct_pred)
        for succ in G.successors(node):
            indirect_pred_dict[succ] |= indirect_pred

我还没有分析是否有可能构造一个在启用了O(V**2)选项的情况下以比optimize_dense更复杂的复杂度执行的稠密、但非最大连通的图，但我没有理由先验地认为这是不可能的。优化对一个最大连通图最有效，并且不会做任何事情，例如，在每个节点与其孙子共享接班人的情况下，而不是它的子节点，而我还没有分析这种情况的运行时间。

示例测试平台

我已经简化了基本算法的代码，并添加了记录最坏情况路径所需操作数的工具，以及生成最大连通图的示例测试生成器。

import collections
import networkx as nx

def makegraph(numnodes):
    """
    Make a fully-connected graph given a number of nodes
    """
    edges = []
    for i in range(numnodes):
        for j in range(i+1, numnodes):
            edges.append((i, j))
    return nx.DiGraph(edges)

def remove_redundant_edges(G):
    ops = 0
    indirect_pred_dict = collections.defaultdict(set)
    for node in nx.topological_sort(G):
        indirect_pred = indirect_pred_dict[node]
        direct_pred = G.predecessors(node)
        for pred in direct_pred:
            if pred in indirect_pred:
                G.remove_edge(pred, node)
        indirect_pred.update(direct_pred)
        for succ in G.successors(node):
            indirect_pred_dict[succ] |= indirect_pred
            ops += len(indirect_pred)
    return ops

def test_1(f, numnodes):
    G = makegraph(numnodes)
    e1 = nx.number_of_edges(G)
    ops = f(G)
    e2 = nx.number_of_edges(G)
    return ops, e1, e2

for numnodes in range(30):
    a = test_1(remove_redundant_edges, numnodes)
    print numnodes, a[0]