查找连接图中某些节点的连续边

Question

我有一个道路网络图，可以简单地表示为下图。大多数节点有两个邻居，但有些节点有三个，这意味着它们是 "intersections"，或 "crossroads"。这些在图中用红色表示。

我想找到直接连接两个红色节点的每个连续边序列（"directly" 我的意思是，不通过中间红色节点）。

目前，我可以找到这样的红色节点：

crossroad_nodes = [node for node in graph.nodes() if len(graph.edges(node)) > 2]

但我不知道如何assemble一系列networkx命令来完成我想做的事情。

期望的输出类似于

print segments
> [[1,2,3,4,5,6],[3,5,6,2,4,7],[9,8,7,6,3,2],...] # list of lists of nodes or node indices.

Answer 1

您可以使用shortest_path功能找到路径，然后检查确保它没有经过另一个十字路口。

这是使用集合进行检查并在 crossroad_nodes 的所有成对组合之间查找的一种方法。

import itertools as it
import sets
#import networkx as nx

c_s = set(crossroad_nodes)
for i in it.combinations(crossroad_nodes,2):
    path = nx.shortest_path(G,source=i[0],target=i[1])
    #check to make sure path does not pass through another crossroad node
    if len((c_s - set(i)) & set(path)) == 0:
        print i,path

这是构建图的完整可重现示例。

import networkx as nx

G = nx.grid_graph([3,6])
pos = nx.spectral_layout(G)

for i in range(1,5):
    G.remove_edge((0, i),(1, i))
    G.remove_edge((1, i),(2, i))

#example using corners
crossroad_nodes = [(0, 0),(2, 0),(0, 5),(2, 5)]
oth = [i for i in G.nodes() if i not in crossroad_nodes]

nx.draw_networkx_nodes(G,pos,nodelist=oth,node_color='black')
nx.draw_networkx_nodes(G,pos,nodelist=crossroad_nodes)
#nx.draw_networkx_labels(G,pos=pos)
nx.draw_networkx_edges(G,pos)

#find the paths between our nodes of interest
import itertools as it
import sets

c_s = set(crossroad_nodes)
for i in it.combinations(crossroad_nodes,2):
    path = nx.shortest_path(G,source=i[0],target=i[1])
    #check to make sure path does not pass through another crossroad node
    if len((c_s - set(i)) & set(path)) == 0:
        print i,path

查找连接图中某些节点的连续边

Finding consecutive edges linking certain nodes in graph

graph-theory

networkx