从起始节点查找DAG中的所有路径 [英] Find all paths in DAG from starting node

问题描述

我正在尝试从所选节点中查找DAG中的所有路径.

I am trying to find all paths in DAG from selected node.

所以我正在随机生成看起来像这样的元组列表:

So I am randomly generating list of tuples that looks like:

glavnaLista = [(6, 7), (6, 15), (15, 16), (16, 21), (15, 9), (9, 13), (13, 4), (4, 1), (1, 5)]

从此列表中，我们可以看到节点"6"是图的起点

From this list we can see that node "6" is starting point of graph

现在我正在创建图形:

G = nx.DiGraph() 
    G.add_edges_from(glavnaLista)

看起来像这张图片

现在我正在尝试使用代码从起始节点查找所有路径(已完成):

Now I am trying to find all paths (completed) from starting node with code:

def find_all_paths(graph, start, path=[]):

    path = path + [start]
    if start not in graph:
        return [path]
    paths = [path]
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, path)
            for newpath in newpaths:
                print (newpath)
                paths.append(newpath)        
    return paths

结果是所有路径的列表:

Result is list of all paths:

[[6], [6, 7], [6, 15], [6, 15, 16], [6, 15, 16, 21], [6, 15, 9], [6, 15, 9, 13], [6, 15, 9, 13, 4], [6, 15, 9, 13, 4, 1], [6, 15, 9, 13, 4, 1, 5]]

但是我的问题是我不需要不完整的路径(不去结束节点)，我的列表应该只有完整的路径:

But my problem is that I don't need paths that are not full (not going to the ending node), my list should have only full paths:

[6, 7]
[6, 15, 9, 13, 4, 1, 5]
[6, 15, 16, 21]

我的想法是检查节点是否同时具有两个邻居，是否不添加列表路径，但我不确定如何实现此功能，因为我对python还是很陌生.

My idea is to check if the node has both neighbours, and if it doesn't than add path to list but I am not sure how to implement this as I am fairly new to python.

推荐答案

您要尝试创建的实际上是从 BFS 或 DFS 遍历 DAG .您可以通过稍微更改代码来做到这一点.

what you are trying to create is actually the tree created from BFS or DFS traversal over a DAG. You can do this by changing your code a bit.

首先请注意，您有一些不必要的代码部分:

First of all notice that you have some unnecessary code parts:

def find_all_paths(graph, start, path=[]):
    path = path + [start]
    paths = [path]
    for node in graph[start]:
        newpaths = find_all_paths(graph, node, path)
        for newpath in newpaths:
            print (newpath)
            paths.append(newpath)        
    return paths

由于我们假设这是DAG，所以我们可以摆脱一些条件...

Since we assume this is a DAG we can get rid of some conditions...

现在，我们要生成DFS遍历的路径.此处的打印将在每次迭代后打印一条路径，但是我们想在结束时打印该路径.
因此，我们将添加一个简单的if语句来检查这是否是路径的结尾，如果是，我们将打印路径:

Now we want to generate the paths of a DFS traversal. The print here will print a path after each iteration but we would like to print the path after we reached an end.
So we will add a simple if statement to check if this is the end of the path and if it is we will print the path:

def find_all_paths(graph, start, path=[]):
    path = path + [start]
    paths = [path]
    if len(graph[start]) == 0:  # No neighbors
        print(path)
    for node in graph[start]:
        newpaths = find_all_paths(graph, node, path)
        for newpath in newpaths:
            paths.append(newpath)
    return paths

结果:

[6, 7]
[6, 15, 16, 21]
[6, 15, 9, 13, 4, 1, 5]

这篇关于从起始节点查找DAG中的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！