使用Python解决图形问题

Question

使用Python解决图形问题

11

我有一个情况需要用Python来解决，但是我对图表并没有足够的了解。我找到了一个库 networkx ，看起来非常适合这个相对简单的任务，但我在做我想要的确切事情时遇到了问题，而这些事情应该是相当简单的。

我有一个节点列表，可以有不同的类型，以及两个“类”邻居，向上和向下。任务是查找两个目标节点之间的路径，并考虑一些约束条件：

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

所以，我尝试了一些实验，但我像我说的那样，遇到了麻烦。首先，我不确定这实际上代表什么类型的图形？它不是方向性的，因为无论您从节点1到节点2还是从节点2到节点1（除了最后一种情况外），都没有关系，所以这使事情变得有点复杂... 这意味着我不能只创建一个简单的多向图形，因为我必须考虑到那个约束条件。其次，我必须遍历这些节点，但指定仅特定类型的节点可用于路径。此外，在发生最后一种情况时，我必须考虑入口和出口类别/方向，这使其处于某种有向状态。

以下是一些示例代码：

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

输出结果还不错，但我需要这些约束条件。您有什么建议可以帮我实现这些约束条件，或者在理解这种类型问题上给我更多的指导，或者为这个问题提供一个不同的方法或库？也许一个简单的基于词典的算法会适合这个需求？

谢谢！

- wont_compile

1

很难理解你想要什么。你能为问题提供一些背景吗？不同类型的节点代表什么？你想要两个节点之间的所有路径，还是只想要最短路径？需要多快？（“所有路径”可能会导致指数级时间，仅打印输出就需要很长时间） - Andy Jones

假设节点代表城市、车站或某种具有特定“类型”的位置，该类型表示其大小或其他限制因素。这些节点有三种类型。应包含所有路径，而不仅仅是最短的路径。速度不是关键因素，但我不想要花费数小时来解析某些节点 :) 我将使用非常小的数据进行测试，少于100个节点，因此速度绝对不会成为问题。 - wont_compile

我并不完全理解这些限制。类型为x的节点只能通过一次还是可以任意多次通过？节点之间的连接是否完全基于这三个类别，还是还有其他需要考虑的结构？ - Michael J. Barber

类型为X的节点只是起点和终点，除了在这两种状态下，路径中不能包含它们。节点之间的连接具有额外的“侧面”，即向上和向下，在最终约束条件中很重要。除此之外，实际节点的类型以及节点/连接的描述中没有其他附加信息。关于节点y的要求，一个节点只能出现一次，但路径中可以出现多个y节点。因此，两个y是可以的，但它们必须是不同的节点。类型z也是类似，但同一个节点可以通过两次。 - wont_compile

3个回答

5

我认为最好的方法是计算源节点S和其他所有节点之间长度不超过k的所有有效路径，然后使用该信息计算长度不超过k+1的所有有效路径。您只需重复此过程，直到获得固定点，其中没有路径被修改。

实际上，这意味着您应该在每个节点上设置一个路径列表。在每个步骤中，您依次考虑每个节点U，并查看在上一步中终止于U的某个邻居V的路径。如果其中任何路径可以扩展为新的、不同的路径到U，则将其扩展并添加到U的列表中。

如果在执行步骤时找不到新路径，则达到终止状态。然后，您可以检查目标节点T的路径列表。

伪代码（使用非常宽松的C#格式）：

var paths = graph.nodes.ToDictionary(node => node, node => new List<List<node>>())
paths[S].Add(new List<node> {S}) // The trivial path that'll start us off.


bool notAFixedPoint = true;

while (notAFixedPoint)
{
    notAFixedPoint = false // Assume we're not gonna find any new paths.

    foreach (var node in graph)
    {
        var pathsToNode = paths[node]

        foreach (var neighbour in node.Neighbours)
        {
            var pathsToNeighbour = paths[neighbour]

            // ExtendPaths is where all the logic about how to recognise a valid path goes.
            var newPathsToNode = ExtendPaths(pathsToNeighbour, node)

            // The use of "Except" here is for expository purposes. It wouldn't actually work,
            // because collections in most languages are compared by reference rather than by value.
            if (newPathsToNode.Except(pathsToNode).IsNotEmpty())
            {
                // We've found some new paths, so we can't terminate yet.
                notAFixedPoint = true 

                pathsToNode.AddMany(newPathsToNode)
            }
        }
    }
}

return paths[T]

- Andy Jones

所以，对于第一部分，我会从源S到其邻居创建长度为k的路径。然后，在长度为k+1时，这将添加与连接到源的节点相邻的节点的路径，并以此方式给我源到这些节点的路径。并重复此过程，直到在结果中获得目标节点？由于可能存在多条路径，我如何知道何时停止。您能否用一些伪代码指导我，因为我真的没有写这种东西的经验。谢谢！ - wont_compile

感谢您的输入和见解，我花了更多时间来思考这个问题，并从不同的角度得出了解决方案。除了您提供的伪代码之外，另一个部分是限制条件，这些条件是这个问题的“关键”。 - wont_compile

-1

这看起来像是一个优化问题 -- 搜索"旅行商问题"，这是一个很接近你想要做的经典的例子。

我在处理优化问题时使用"模拟退火"方法效果不错，但你也可以看看"遗传算法"。

- Mark Leighton Fisher

很遗憾，我认为遗传算法根本不适用于这个问题。变异和交叉很可能很少会产生实际的解决方案。 - Hannes Ovrén

我同意，我不得不以与我预期不同的方式编写代码，我会尽快发布我的答案供参考。 - wont_compile

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aric · Accepted Answer

如果以不同的方式构建图形，您可能可以使用all_simple_paths()函数解决问题。简单路径是没有重复节点的路径。因此，对于您的约束条件，以下是一些建议，以便您可以运行未修改的算法来构建图形。

只有特定类型的节点可以被遍历，即如果起始节点是x类型，则路径中的任何节点都必须来自另一个路径集合y或z

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

如果节点属于类型y，则只能通过一次

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

如果节点属于类型z，则可以通过两次

对于每个类型为z的节点n，请添加一个具有指向和从n指向的相同边缘的新节点n2。

如果访问了类型z的节点，则必须从不同类别的邻居处退出，即如果从上方访问，则必须从下方退出

如果边缘是您所提出的定向的，则可以通过确保到达z的边缘全部是相同方向来满足此要求——例如，向上进入，向下退出...