Networkx图移除冗余路径以计算级别顺序

Question

考虑以下针对networkx图的data set的图形结构。当上述数据集被转换成一棵树：

拓扑排序给出平次序如下输出（更多或更少，这正是我期待的），但没有提供有关信息每个节点对应。例如：n0：Level-0，n2：Level-1和n3：Level-1等等。

print(nx.topological_sort(G)) 
['n2', 'n1', 'n0', 'n3', 'n4', 'n5', 'n6', 'n7', 'n8', 'n9', 'n24', 'n27', 'n21', 'n23', 'n50', 'n15', 'n14', 'n16', 'n17', 'n25', 'n18', 'n19', 'n42', 'n28', 'n38', 'n30', 'n31', 'n32', 'n39', 'n33', 'n34', 'n35', 'n36', 'n37', 'n49', 'n41', 'n40', 'n43', 'n44', 'n29', 'n22', 'n20', 'n26', 'n45', 'n48', 'n46', 'n47', 'n51', 'n54', 'n52', 'n53', 'n11', 'n10', 'n13', 'n12', 'n55'] 

因此，我进一步处理所述数据集以与nextworkx.single_source_shortest_path_length()和排序基于电平的顺序。由于在双图中存在多条边，所以单源最短路径输出不是很准确。

from operator import itemgetter 
nd = nx.single_source_shortest_path_length(G,'n0') 
sorted(nd.items(), key=itemgetter(1)) 
[('n0', 0), 
('n12', 1), 
('n13', 1), 
... 
('n4', 1), 
('n5', 1), 
('n6', 1), 
('n7', 1)] 

为了解决这个问题，我试图找出基于以下方法解决：
1.通过消除冗余路径和计算使用single_source_shortest_path()水平顺序。为了实现这一点，我可能必须删除冗余路径，以使每个节点只有一条路径，直到根（n0），通过它的父节点。冗余路径除了在前往根节点（n0）的路径上访问附近节点（父节点）的路径之外的所有路径。因此，一个节点只能有一条路径（不一定是最短路径）。例如，如果节点（n221）具有到父节点（n22）的边，并且另一边是祖父节点（n或n2），则移除祖父节点的所有边（移除边n221- - > n），如果父母（n22）有一个边缘（n22 ---> n）给祖父母。

1. 我可以得到拓扑排序输出。随着输出我可以重建使用nx.topological_sort(G)和nx.bfs_successors(G, 'n0')类似于简单的树什么是this question

来达到的最终希望得到以下结果来迭代每个级别开始从N0为根：

Levels: nodes 
1: n0 
2: n3, n21 
3: n4 
4: n5 
6: n7, n15 ... 
7: ... 

我在这里错过了什么来获得正确的结果，以及如何获得预期的行为？

我正在处理具有〜1.5K节点的非常大的数据集，因此在这里采用了一个简单的示例，而不是呈现完整的数据集。

Answer 1

好像要删除从叶节点（定义here）到根节点的任何边缘，当叶同时具有：

1. 的边缘到根节点
2. 替换路径以根

上面的图G有点混乱，并不完全符合你的'图案'描述。（例如，不显示N511）

import matplotlib as plt 
import networkx as nx 

pos=nx.drawing.nx_pydot.pydot_layout(G, prog='dot') 
nx.draw(G, pos=pos, with_labels=True) 

如果我理解正确的话，这个解决方案可以帮助。它遍历叶子并检查叶子是否具有大于1的根节点路径。为leaf之间和根节点'n'

removed = [] 
for leaf in (x for x in G.nodes_iter() if G.out_degree(x)==0 and G.in_degree(x)>=1): 
    if sum(1 for _ in nx.all_simple_paths(G, 'n', leaf)) >1: # equivalent to len(generator) 
      if G.has_edge('n',leaf): 
       removed.append(('n', leaf)) # shows edges removed 
       G.remove_edge('n', leaf) 

print(removed) 
[('n', 'n221'), ('n', 'n51'), ('n', 'n131')] 

它清理图形直接边缘嵌套如果条件检查，如果节点'n'并非真正根这可能会断裂。

pos=nx.drawing.nx_pydot.pydot_layout(G, prog='dot') 
nx.draw(G, pos=pos, with_labels=True) 

编辑

这是我最后一次尝试，或许应该已经离开这个的人更有知识来回答。尝试迭代节点并提取从根节点到节点的最长路径。必须有更好的方式来执行此操作，也许有人可以推荐。

假设G是从您在评论中提供的链接中的代码创建的。

G1 = nx.DiGraph() 
for n in nodes: 
    if n == 'n0': # skip n0 
     continue 
    if not nx.has_path(G, 'n0', n): #n1 and n2 are disconnected from n0 
     lpath= max(list(nx.all_simple_paths(G, n, 'n55')), key=len) 
     G1.add_path(lpath) 
     continue 
    lpath= max(list(nx.all_simple_paths(G, 'n0', n)), key=len) 
    G1.add_path(lpath) 

#levels 
sorted(nx.shortest_path_length(G1, 'n0').items(), key=operator.itemgetter(1)) # omits n1, n2 

[('n0', 0), 
('n21', 1), 
('n3', 1), 
('n4', 2), 
('n5', 3), 
('n15', 4), 
('n24', 4), 
('n6', 4), 
('n7', 4), 
('n8', 5), 
('n12', 6), 
(... 


plt.figure(figsize=(20,12)) 
pos=nx.drawing.nx_pydot.pydot_layout(G1, prog='dot') 
nx.draw(G1, pos=pos, with_labels=True) 

Answer 2

我不知道我理解你的问题，但我想你想要的是那里是图中的任何节点从根只有一条路径。

如果这是你的要求，唯一的办法是用树。如果我理解正确的话，你也希望所有剩下的路径是最短的根，在这种情况下你要找的树就是BFS树。

你可以得到它在NetworkX这样的：

import networkx as nx 

G = nx.DiGraph() 
G.add_edges_from([('n', 'n1'), ('n', 'n2'), ('n', 'n3'), ('n', 'n4'), ('n', 'n5')]) 
G.add_edges_from([('n4', 'n41'), ('n1', 'n11'), ('n1', 'n12'), ('n1', 'n13'), ('n5', 'n51'), ('n12', 'n131')]) 
G.add_edges_from([('n2', 'n21'), ('n2', 'n22'), ('n', 'n221'), ('n', 'n51')]) 
G.add_edges_from([('n13', 'n131'), ('n22', 'n221'), ('n', 'n131'), ('n', 'n221'), ('n', 'n511')]) 

G = nx.bfs_tree(G, 'n') 

nx.draw(G, with_labels=True) 

将会产生这样的：