创建“最小连通”有向无环图

Question

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

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

null

>

节点为：

['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']

边缘是：

[('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')]

Answer 1

是的。

您希望使用all_simple_paths[documentation]（它提供了两者之间所有简单路径的生成器）。一旦它找到第二个就退出，这样它就不会计算所有的。

一旦定义了这一点，您希望查看每个边，如果从源到目标有多条路径，则删除该边。

def multiple_paths(G,source,target):
    '''returns True if there are multiple_paths, False otherwise'''
    path_generator = nx.all_simple_paths(G, source=source, target=target)
    counter = 0
    for path in path_generator: #test to see if there are multiple paths
        counter += 1
        if counter >1:  
            break  #instead of breaking, could have return True
    if counter >1:  #counter == 2
        return True
    else:  #counter == 0 or 1
        return False

import networkx as nx
G=nx.DiGraph()
G.add_edges_from([(0,1), (1,2), (1,3), (0,3), (2,3)])
multiple_paths(G,0,1)
> False
multiple_paths(G,0,2) 
> False
multiple_paths(G,0,3)
> True

for edge in G.edges_iter():  #let's do what you're trying to do
    if multiple_paths(G, edge[0], edge[1]):
        G.remove_edge(edge[0],edge[1])

G.edges()
> [(0, 1), (1, 2), (2, 3)]

import networkx as nx
G=nx.DiGraph()
G.add_edges_from([(0,1), (1,2), (1,3), (0,3), (2,3)])
for edge in G.edges_iter():
    G.remove_edge(edge[0],edge[1])
    if not nx.has_path(G,edge[0],edge[1]):
        G.add_edge(edge[0],edge[1])

G.edges()
> [(0, 1), (1, 2), (2, 3)]

不过，如果有任何边缘数据，您将需要小心，我不喜欢删除边缘然后再添加回来的可能性--这为一些难以发现的bug打开了机会。