找到使用所有給定邊的路徑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

簡而言之，您可能需要在邊上執行多次傳遞來組裝使用所有邊的路徑。

所包含的代碼運行在以下假設：

• 的溶液存在。即，所有頂點屬於底層圖的單個連接組件，並且對於除了2個頂點以外的全部或全部頂點，都可以使用
• in_degree = out_degree。在後一種情況下，其中一個頂點有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