用Python解决图形问题

Question

我有一种情况,我想用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

输出相当不错,但我需要这些约束.那么,您是否有一些建议如何实现这些,或者给我一些关于理解这类问题的指导,或者针对这个问题提出不同的方法或库？也许一个简单的基于字典的算法适合这种需要？

谢谢!

Answer 1

如果以不同方式构造图形,则可以对问题使用all_simple_paths()函数.简单路径是没有重复节点的路径.因此,对于您的约束,这里有一些构建图形的建议,以便您可以不修改地运行该算法.

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

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

• 如果节点的类型为y,则只能传递一次

这是简单路径的定义,因此它会自动满足.

• 如果节点具有类型z,则可以传递两次

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

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

如果边缘是按照你的建议定向的,那么如果你确保z的边缘都是相同的方向就可以满足这个要求 - 例如,向上和向下用于向下...

Answer 2

我认为最好的方法是计算源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]