python - 用 Python 解决图形问题

Question

我有一种情况，我想用 Python 解决这个问题，但不幸的是我对图表的了解不够。我找到了一个似乎非常适合这项相对简单任务的库，networkx，但我在做我想做的事情时遇到了问题，这应该相当简单。

我有一个节点列表，它可以有不同的类型，以及两个“类”的邻居，向上和向下。任务是找到两个目标节点之间的路径，并考虑一些限制:

• 只能遍历特定类型的节点，即如果起始节点的类型为 x，则路径中的任何节点都必须来自另一组路径，y 或 z
• 如果节点的类型为y，则只能通过一次
• 如果一个节点的类型为z，它可以被传递两次
• 如果访问类型为 z 的节点，则导出必须来自不同类别的邻居，即如果它是从上方访问的，则导出必须来自下方

所以，我尝试了一些实验，但如前所述，我一直在努力。首先，我不确定这实际上代表什么类型的图？它不是定向的，因为从节点 1 到节点 2，或从节点 2 到节点 1 并不重要(except 在最后一个场景中，所以事情有点复杂...... ).这意味着我不能只创建一个简单的多向图，因为我必须牢记该约束。其次，我必须遍历这些节点，但指定只有特定类型的节点才能用于路径。此外，如果发生最后一种情况，我必须记住进入和退出类/方向，这会使其处于某种定向状态。

这是一些示例模型代码:

import networkx as nx

G=nx.DiGraph()
G.add_node(1, type=1)
G.add_node(2, type=2)
G.add_node(3, type=3)
G.add_edge(1,2, side="up")
G.add_edge(1,3, side="up")
G.add_edge(2,1, side="down")
G.add_edge(2,3, side="down")
for path in nx.all_simple_paths(G,1,3):
    print path

输出相当不错，但我需要这些约束。那么，您对我如何实现这些有什么建议吗？或者给我一些关于理解此类问题的更多指导，或者为这个问题建议不同的方法或库？也许一个简单的基于字典的算法可以满足这种需求？

谢谢!

Answer 1

如果您以不同的方式构建图表，您或许可以使用 all_simple_paths() 函数来解决您的问题。简单路径是那些没有重复节点的路径。因此，对于您的约束，这里有一些构建图形的建议，以便您可以不加修改地运行该算法。

• 只能遍历特定类型的节点，即如果起始节点的类型为 x，则路径中的任何节点都必须来自另一组路径，y 或 z

给定起始节点 n，在找到路径之前删除具有该类型的所有其他节点。

• 如果节点的类型为y，则只能通过一次

这是简单路径的定义，因此自动满足。

• 如果一个节点的类型为z，它可以被传递两次

对于类型 z 的每个节点 n 添加一个新节点 n2，其边与指向和指向 n 的边相同。

• 如果访问类型为 z 的节点，则导出必须来自不同类别的邻居，即如果它是从上方访问的，则导出必须来自下方

如果边缘按照您的建议定向，那么如果您确保到 z 的边缘都是相同的方向，则可以满足此要求 - 例如上进出下...