Пути направленного графа от одного узла к другому через рекурсию - PullRequest
Новая
       7

Пути направленного графа от одного узла к другому через рекурсию

0 голосов
/ 12 марта 2020

PYTHON 3.8

Я пытаюсь перейти от step (S) к другому step через transitions (T) и branches (B ) где формат данных: [from_id, from_number, to_id, to_number].

Моя конечная цель - сохранить каждый путь во вложенном массиве.

INFO

С данными: 

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']              ]

1 Ответ

0 голосов
/ 12 марта 2020

Я добавил глобальный параметр 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

Вы можете или не можете вернуть PATH в зависимости от вашего варианта использования.

...