通过递归从一个节点到另一个节点的有向图路径

Question

PYTHON 3.8

我试图通过 transitions (T) 和 branches(B) 从 step(S) 遍历到另一个 step，其中数据是 [from_id, from_number, to_id, to_number].

我的最终目标是将每个路径保存在嵌套数组中。

信息

随着数据：

DATA_CONNS = [['T', '1', 'S', '2'], ['T', '10', 'S', '11'], ['S', '11', 'T', '11'], ['T', '5', 'S', '6'], ['B', '16', 'T', '9'], ['B', '16', 'T', '12'], ['T', '9', 'B', '17'], ['T', '12', 'B', '17'], ['B', '19', 'S', '4'], ['T', '3', 'S', '5'], ['T', '2', 'B', '19'], ['B', '19', 'S', '3'], ['T', '6', 'B', '22'], ['B', '22', 'S', '7'], ['B', '22', 'S', '8'], ['S', '6', 'B', '33'], ['S', '4', 'B', '33'], ['S', '7', 'T', '7'], ['S', '9', 'B', '16'], ['S', '8', 'B', '16'], ['S', '2', 'B', '30'], ['B', '30', 'T', '2'], ['B', '30', 'T', '14'], ['S', '3', 'B', '31'], ['B', '31', 'T', '3'], ['B', '31', 'T', '15'], ['S', '5', 'B', '32'], ['B', '32', 'T', '5'], ['B', '32', 'T', '16'], ['B', '33', 'T', '6'], ['B', '33', 'T', '17'], ['S', '10', 'B', '34'], ['B', '34', 'T', '10'], ['B', '34', 'T', '18'], ['S', '21', 'T', '21'], ['T', '17', 'S', '21'], ['S', '22', 'T', '22'], ['T', '18', 'S', '22'], ['B', '17', 'S', '10'], ['B', '34', 'T', '13'], ['T', '7', 'S', '9'], ['T', '11', 'S', '1'], ['T', '21', 'S', '1'], ['T', '14', 'S', '21'], ['T', '15', 'S', '21'], ['T', '16', 'S', '21'], ['T', '22', 'S', '10'], ['T', '13', 'S', '9']]

使用递归函数：

def recur_conn(ARR, tag, BUILD):

    if tag[0] == 'S':
        print('got here!')
        return BUILD

    else:
        # find all options
        for i in [x for x in ARR if x[0] == tag[0] and x[1] == tag[1]]:
            BUILD[-1].append([i[2], i[3]])
            VAL = recur_conn(ARR, [i[2], i[3]], BUILD)
            BUILD[-1].append(VAL)

    return BUILD

执行：

# 'S','6' is selected which is ['S', '6', 'B', '33']

W = recur_conn(DATA_CONNS, ['B', '33'], [['S', '6'], ['B', '33']])

输出：

W = [['S', '6'], ['B', '33', ['T', '6'], ['B', '22'], ['S', '7'],
     [...], ['S', '8'], [...], [...], [...], ['T', '17'], ['S', '21'], 
     [...], [...]]]

预期输出：

W = [ [['S', '6'], ['B', '33'], ['T', '6'], ['B', '22'], ['S', '7']],
      [['S', '6'], ['B', '33'], ['T', '6'], ['B', '22'], ['S', '8']],
      [['S', '6'], ['B', '33'], ['T', '17'], ['S', '21']              ]

Answer 1

我添加了一个全局参数 PATH。这应该可以解决您的问题

import copy
PATH = [ ]
def recur_conn(ARR, tag, BUILD):

    if tag[0] == 'S':
        print('got here!')
        PATH.append( BUILD )
        return PATH

    else:
        # find all options
        for i in [x for x in ARR if x[0] == tag[0] and x[1] == tag[1]]:
            CURR_BUILD = copy.deepcopy( BUILD )
            CURR_BUILD[-1].append([i[2], i[3]])
            recur_conn(ARR, [i[2], i[3]], CURR_BUILD)

    return PATH

您可能会或可能不会 return PATH，具体取决于您的用例。

通过递归从一个节点到另一个节点的有向图路径

Directed Graph Paths From One Node To Another Through Recursion

python

recursion

graph-theory

list