CODEWITHSUNDEEP
graph-theorynetworkx
heltonbiker
heltonbiker

Reputation: 27575

Finding consecutive edges linking certain nodes in graph

I have a road network graph that can be represented simplistically as the figure below. Most nodes have two neighbors, but some have three, meaning they are "intersections", or "crossroads". These are represented in red in the figure.

I want to find every sequence of consecutive edges directly linking two red nodes (by "directly" I mean, not passing through an intermediate red node).

Currently, I can find the red nodes like this:

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

But I don't know how to assemble a sequence of networkx commands to do what I want.

Desired output would be something like

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.

enter image description here

Upvotes: 2

Views: 659

Answers (1)

Andy W
Andy W

Reputation: 5089

You can use the shortest_path function to find the paths, and then check to make sure afterwards that it does not pass through another crossroad.

Here is one way to do the check using sets and looking between all pairwise combinations of 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

Here is a full reproducible example for a constructed graph.

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

Upvotes: 1

Related Questions