CODEWITHSUNDEEP
pythongraphnetworkx
Marian
Marian

Reputation: 15338

How to isolate these (image included) paths in a graph?

I have a graph and want to isolate distinct paths from it. Since I can't phrase this easily in graph jargon, here is a sketch:

[Source graph (left) and intended result (right)]

On the left side is a highly simplified representation of my source graph. The graph has nodes with only 2 neighbors (shown as blue squares). Then it has intersection and end nodes with more than 2 neighbors or exactly 1 neighbor (shown as red dots).

On the right side, coded in three different colors, are the paths I want to isolate as a result. I want to isolate alls paths connecting the red dots. The resulting paths must not cross (go through) any red dots. Each edge may only be part of one distinct result path. No edges should remain (shortest path length is 1).

I am sure this is a known task in the graph world. I have modeled the graph in NetworkX, which I'm using for the first time, and can't find the proper methods to do this. I'm sure I could code it the hard way, but would be glad to use a simple and fast method if it existed. Thanks!

Edit: After randomly browsing the NetworkX documentation I came across the all_simple_paths method. My idea is now to

  1. iterate all nodes and identify the red dots (number of neighbors != 2)
  2. use all_simple_paths() pairwise for the red dots, collect the resulting paths
  3. deduplicate the resulting paths, throw away everything that contains a red dot except as the start and end node

Step 2, of course, won't scale well. With ~2000 intersection nodes, this seems still possible though.

Edit 2: all_simple_paths appears to be way too slow to use it this way.

Upvotes: 3

Views: 292

Answers (1)

Alfe
Alfe

Reputation: 59436

I propose to find all straight nodes (i. e. nodes which have exactly two neighbors) and from the list of those build up a list of all your straight paths by picking one straight node by random and following its two leads to their two ends (the first non-straight nodes).

In code:

def eachStraightPath(g):
  straightNodes = { node for node in g.node if len(g.edge[node]) == 2 }
  print straightNodes
  while straightNodes:
    straightNode = straightNodes.pop()
    straightPath = [ straightNode ]
    neighborA, neighborB = g.edge[straightNode].keys()
    while True:  # break out later if node is not straight
      straightPath.insert(0, neighborA)
      if neighborA not in straightNodes:
        break
      newNeighborA = (set(g.edge[neighborA]) ^ { straightPath[1] }).pop()
      straightNodes.remove(neighborA)
      neighborA = newNeighborA
    while True:  # break out later if node is not straight
      straightPath.append(neighborB)
      if neighborB not in straightNodes:
        break
      newNeighborB = (set(g.edge[neighborB]) ^ { straightPath[-2] }).pop()
      straightNodes.remove(neighborB)
      neighborB = newNeighborB
    yield straightPath

g = nx.lollipop_graph(5, 7)

for straightPath in eachStraightPath(g):
  print straightPath

If your graph is very large and you do not want to hold a set of all straight nodes in memory, then you can iterate through them instead, but then the check whether the next neighbor is straight will become less readable (though maybe even faster). The real problem with that approach would be that you'd have to introduce a check to prevent straight paths from being yielded more than once.

Upvotes: 2

Related Questions