如何在图表中隔离这些（包含图像的）路径？-Java 学习之路

我有一个图表，并希望从中隔离不同的路径 . 由于我不能用图表术语轻松地说出这个，这里是一个草图：

Source graph (left) and intended result (right)

在 left side 上是源图的高度简化表示 . 该图具有仅具有2个邻居的节点（显示为蓝色方块） . 然后它具有交叉点和末端节点，其具有多于2个邻居或恰好1个邻居（显示为红点） .

在 right side 上，以三种不同的颜色编码，是我想要隔离的路径 . 我想隔离连接红点的所有路径 . 生成的路径不得交叉（穿过）任何红点 . 每条边可能只是一个不同结果路径的一部分 . 不应留下任何边缘（最短路径长度为1） .

我确信这是图世界中的一项已知任务 . 我已经在NetworkX中对图形进行了建模，我是第一次使用它，并且无法找到正确的方法来执行此操作 . 我确信我可以用很难的方式对它进行编码，但如果它存在的话，我会很高兴使用一种简单快速的方法 . 谢谢！

Edit: 在随机浏览NetworkX文档后，我遇到了all_simple_paths方法 . 我的想法现在是

迭代所有节点并识别红点（邻居数量！= 2）
对红点使用all_simple_paths（）成对，收集生成的路径
对结果路径进行重复数据删除，丢弃除开始和结束节点之外的所有包含红点的内容

当然，第2步不会很好地扩展 . 有了~2000个交叉点节点，这似乎仍然可行 .

Edit 2: all_simple_paths似乎太慢而无法以这种方式使用它 .

1 回答

我建议找到所有直接节点（即具有正好两个邻居的节点），并从列表中 Build 所有直线路径的列表，方法是随机选择一个直线节点，并将其两个引线连接到它们的两端（第一个）非直线节点） .

在代码中：

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

如果你的图形非常大并且你不想在内存中保存一组所有直线节点，那么你可以改为遍历它们，但是然后检查下一个邻居是否是直的会变得不那么可读（尽管可能更快） . 这种方法的真正问题在于你必须引入一个检查来防止直路径被多次产生 .

回复于 2024-04-26T16:36:03+08:00

如何在图表中隔离这些（包含图像的）路径？

1 回答

相关问题