python - 使用所有给定的边python找到路径

Question

我有一个边列表。我需要从它们解码从源节点到汇节点的路径。我的路径中可能有循环，但我应该只使用每条边一次。在我的列表中，我可能不止一次拥有相同的边，这意味着在我的路径中我应该不止一次通过它。

假设我的边缘列表如下:

[(1, 16), (9, 3), (8, 9), (15, 8), (5, 1), (8, 15), (3, 5)]

所以我的路径是:

8->15->8->9->3->5->1->16 equivalent to [8,15,8,9,3,5,1,16]

我知道汇节点和源节点。 (在上面的示例中，我知道 8 是源，16 是汇)这是另一个示例，其中不止一次使用了相同的边:

[(1,2),(2,1),(2,3),(1,2)]

路径是:

1->2->1->2->3 equivalent to [1,2,1,2,3]

基本上它是一种拓扑排序，但是我们在拓扑排序中没有循环。我有以下代码，但它不使用循环中的节点!

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
return paths

Answer 1

简单地说，您可能需要多次遍历边缘才能使用所有边缘组装一条路径。

包含的代码基于以下假设运行:

• 存在解决方案。即所有顶点都属于底层图的单个连通分量，并且
• in_degree = out_degree 用于所有或除 2 个顶点之外的所有顶点。在后一种情况下，其中一个顶点具有 in_degree - out_degree = 1，另一个顶点具有 in_degree - out_degree = -1.

此外，即使在这些条件下，利用所有边找到从源到汇的路径的问题也不一定是唯一的解决方案。此代码仅找到一种解决方案，而不是所有解决方案。 (存在多个解决方案的示例是“雏菊”[(1,2),(2,1),(1,3),(3,1),(1,4),(4,1 ),(1,5),(5,1)] 其中开始和结束相同。)

想法是为由边的起始节点索引的路径创建所有边的字典，然后在将边添加到路径时从字典中删除边。与其尝试在第一遍中获取路径中的所有边，不如多次遍历字典，直到使用完所有边。第一遍创建一条从源到汇的路径。随后的传递添加循环。

警告几乎没有一致性检查或验证。如果起点不是边缘的有效来源，则返回的“路径”将断开连接!

"""
This is a basic implementatin of Hierholzer's algorithm as applied to the case of a 
directed graph with perhaps multiple identical edges.
"""

import collections

def node_dict(edge_list):
    s_dict = collections.defaultdict(list)
    for edge in edge_list:
        s_dict[edge[0]].append(edge)
    return s_dict

def get_a_path(n_dict,start):
    """
    INPUT:  A dictionary whose keys are nodes 'a' and whose values are lists of 
    allowed directed edges (a,b) from 'a' to 'b', along with a start WHICH IS 
    ASSUMED TO BE IN THE DICTIONARY.

    OUTPUT:  An ordered list of initial nodes and an ordered list of edges 
    representing a path starting at start and ending when there are no other 
    allowed edges that can be traversed from the final node in the last edge.

    NOTE:  This function modifies the dictionary n_dict!
    """

    cur_edge = n_dict[start][0]
    n_dict[start].remove(cur_edge)

    trail = [cur_edge[0]]
    path = [cur_edge]
    cur_node = cur_edge[1]

    while len(n_dict[cur_node]) > 0:
        cur_edge = n_dict[cur_node][0]
        n_dict[cur_node].remove(cur_edge)
        trail.append(cur_edge[0])
        path.append(cur_edge)
        cur_node = cur_edge[1]

    return trail, path


def find_a_path_with_all_edges(edge_list,start):
    """
    INPUT:  A list of edges given by ordered pairs (a,b) and a starting node.

    OUTPUT:  A list of nodes and an associated list of edges representing a path 
    where each edge is represented once and if the input had a valid Eulerian 
    trail starting from start, then the lists give a valid path through all of 
    the edges.

    EXAMPLES:

        In [2]: find_a_path_with_all_edges([(1,2),(2,1),(2,3),(1,2)],1)
        Out[2]: ([1, 2, 1, 2, 3], [(1, 2), (2, 1), (1, 2), (2, 3)])

        In [3]: find_a_path_with_all_edges([(1, 16), (9, 3), (8, 9), (15, 8), (5, 1), (8, 15), (3, 5)],8)
        Out[3]: 
        ([8, 15, 8, 9, 3, 5, 1, 16],
         [(8, 15), (15, 8), (8, 9), (9, 3), (3, 5), (5, 1), (1, 16)])
    """

    s_dict = node_dict(edge_list)
    trail, path_check = get_a_path(s_dict,start)

    #Now add in edges that were missed in the first pass...
    while max([len(s_dict[x]) for x in s_dict]) > 0:
        #Note:  there may be a node in a loop we don't have on trail yet
        add_nodes = [x for x in trail if len(s_dict[x])>0]
        if len(add_nodes) > 0:
            skey = add_nodes[0]
        else:
            print "INVALID EDGE LIST!!!"
            break

        temp,ptemp = get_a_path(s_dict,skey)
        i = trail.index(skey)
        if i == 0:
            trail = temp + trail
            path_check = ptemp + path_check
        else:
            trail = trail[:i] + temp + trail[i:]
            path_check = path_check[:i] + ptemp + path_check[i:]

    #Add the final node to trail.
    trail.append(path_check[-1][1])
    return trail, path_check