Поиск последовательных ребер, связывающих определенные узлы в графе

Question

У меня есть график дорожной сети, который можно представить упрощенно, как показано на рисунке ниже. Большинство узлов имеют двух соседей, но некоторые из них имеют три, что означает «пересечения» или «перекрестки». Они представлены красным цветом на рисунке.

Я хочу найти каждую последовательность последовательных ребер, напрямую связанных между двумя красными узлами («прямо» я имею в виду, не проходя через промежуточный красный узел).

В настоящее время я могу найти красные узлы, как это:

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

Но я не знаю, как собрать последовательность 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