python - 如何在图中隔离这些(包括图像)路径？

Question

我有一张图，想从中分离出不同的路径。由于我不能用图形术语轻松表达这一点，这里有一个草图:

在左侧 是我的源图的高度简化表示。该图的节点只有 2 个邻居(显示为蓝色方 block )。然后它的交集和端节点有超过 2 个邻居或恰好有 1 个邻居(显示为红点)。

在右侧，用三种不同的颜色编码，是我想要隔离的路径。我想隔离连接红点的所有路径。生成的路径不得穿过(通过)任何红点。每条边可能只是一个不同结果路径的一部分。不应保留任何边缘(最短路径长度为 1)。

我确信这是图形世界中的已知任务。我已经在 NetworkX 中对图表进行了建模，这是我第一次使用它，但找不到合适的方法来执行此操作。我确定我可以用困难的方式对其进行编码，但如果存在的话，我会很高兴使用一种简单快速的方法。谢谢!

编辑:随机浏览 NetworkX 文档后，我发现了 all_simple_paths方法。我现在的想法是

1. 迭代所有节点并识别红点(邻居数!= 2)
2. 对红点使用 all_simple_paths() 成对，收集生成的路径
3. 对生成的路径进行去重，丢弃除开始和结束节点以外的所有包含红点的内容

第 2 步当然不会很好地扩展。有大约 2000 个交叉节点，这似乎仍然是可能的。

编辑 2:all_simple_paths 似乎太慢了，无法以这种方式使用。

Answer 1

我建议找到所有直节点(即恰好有两个邻居的节点)，然后从这些列表中通过选择构建所有直路径的列表随机一个直节点并跟随它的两条引线到达它们的两端(第一个非直节点)。

在代码中:

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

如果你的图非常大并且你不想在内存中保存所有直节点的集合，那么你可以遍历它们，但是检查下一个邻居是否是直节点将变得不那么可读(尽管也许甚至更快)。该方法的真正问题是您必须引入检查以防止直线路径被多次生成。