修剪不在networkx简单路径中的节点？

我有一个DiGrraph，我想修剪任何不包含在我指定的两个节点之间的simple paths中的节点。（另一种想法是节点不能达到都start和end点应该修剪）。修剪不在networkx简单路径中的节点？

我发现要做到这一点的最好方法是获得all_simple_paths，然后使用这些重建一个新图形，但我希望有一个更优雅，更容易出错的解决方案。例如，有没有办法确定什么是不在简单路径上，然后删除这些节点？

来源

2015-11-07 mlissner

我不知道如何。但'all_simple_paths'返回一个生成器，所以你只需要用next（..）来查询它。那么如果你的图不在节点上存储数据，那么得到一个子图就是单线图。 – Kikohs

你可以扩展吗？我没有在节点上存储数据，但我不确定你想要的是什么。听起来很有希望！ – mlissner

然后我会做出回应。 – Kikohs

您可以使用方法all_simple_paths，它返回一个生成器，但只需要第一个路径。然后，您可以使用G.subgraph(nbunch)从您的路径返回诱导图。

编辑：返回由所有简单路径引发的子图只是连接由all_simple_paths返回的唯一节点。

import networkx as nx 
import itertools 

G = nx.complete_graph(10) # or DiGraph, MultiGraph, MultiDiGraph, etc 
# Concatenate all the paths and keep unique nodes (in one line) 
all_path_nodes = set(itertools.chain(*list(nx.all_simple_paths(G, source=0, target=3)))) 
# Extract the induced subgraph from a given list of nodes 
H = G.subgraph(all_path_nodes) 
print(nx.info(H))

输出：

Name: complete_graph(10) 
Type: Graph 
Number of nodes: 10 
Number of edges: 45 
Average degree: 9.0000

来源

2015-11-07 18:51:33 Kikohs

好的，我明白你的意思了，尽管我需要我的最终图来包含任何简单路径中的所有节点。不过，我不知道'subgraph'函数，所以这很有用，但我认为它不会帮助我解决这个问题。 – mlissner

你的问题并不清楚，因为你在* a *简单的路径中说过。 – Kikohs

对不起，觉得很清楚。我会更新它。 – mlissner

我没有就这个而@kikohs一些进展正在努力理解我的问题，并提供他的回答，所以我张贴这个作为一种替代解决问题的办法。我认为他的答案虽然优越！

def _trim_branches(self, g, start, end): 
    """Find all the paths from start to finish, and nuke any nodes that 
    aren't in those paths. 
    """ 
    good_nodes = set() 
    for path in networkx.all_simple_paths(
      g, 
      source=start, 
      target=end): 
     [good_nodes.add(n) for n in path] 

    for node in g.nodes: 
     if node not in good_nodes: 
      g.remove_node(node) 

    return g

使用subgraph做第二个循环是清楚越好，因为是使用itertools.chain他需要一行代码。今天围绕这些部件的好东西！

来源

2015-11-07 19:11:36 mlissner

修剪不在networkx简单路径中的节点？

回答

相关问题