Как сохранить все пути управляемого дерева в списке при рекурсивном обходе? - PullRequest
Новая
       3

Как сохранить все пути управляемого дерева в списке при рекурсивном обходе?

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

[Python 3]

У меня есть направленное дерево, узлами которого могут быть step, transition или branch, обозначенные как s, t, & b каждый с уникальным идентификатором.

Они связаны в данных в этом формате [from_id, from_num, to_id, to_num], отображаемом как ['s', '1', 't', '2'].

Это правила:

  • steps может go до transitions
  • steps может go до branches
  • branches может go до steps
  • branches может go на несколько transitions
  • branches может go на несколько steps
  • transitions может go до steps
  • transitions может go до branches

Итак, из моих данных я выбрал один step например ['s','6','b','33'] и затем поперечный дерево, пока я не достигну другого step - это опция пути.

Я хочу записать все опции пути.

Я написал рекурсивную функцию: 

 def iterconnect(ARR, tag, BUILD):
     # find all options
     for i in [x for x in ARR if x[0] == tag[0] and x[1] == tag[1]]:
         # if option is not S, recurse else add to build
         if i[2] != 's':
             BUILD[-1].append([i[0], i[1]])
             BUILD.append([])
             iterconnect(ARR, [i[2], i[3]], BUILD)
         else:
             BUILD[-1].append([i[2], i[3]])
             BUILD.append([])
     return BUILD

Вызван в моем коде: W = iterconnect(DATA_CONNS, ['b', '33'], [[['s', '6'], ['b', '33']]]), где DATA_CONNS - это просто мой список данных в вышеупомянутом формате.

My outpu В настоящее время я просто добавляю к BUILD, что я понимаю, почему это происходит, но я не могу понять, как создать массив сборки, который фиксирует каждый путь.

Я полагаю, что должен быть возврат, и BUILD добавляется как возврат почти как: BUILD.append(iterconnect(ARR, [i[2], i[3]], BUILD)), но это не работает для меня.

Вот набор данных, который должен работать 

DATA_CONNS = [['s','6', 'b', '33'], ['b','33', 't', '6'], ['b','33', 't', '17'], ['t','17', 's', '21'], 
             ['t','6', 'b', '22'], ['b','22', 's', '7'], ['b','22', 's', '8'],]

Это мой ожидаемый результат 

results = [['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']

Заранее спасибо.

...