Как искать в структуре итеративно? - PullRequest
Новая
       5

Как искать в структуре итеративно?

0 голосов
/ 27 февраля 2020

[PYTHON 3.7]

Предпосылка моего запроса:

Получение кода бэкенда из LADDER logi c программы и восстановление данных из XML file.

У меня старт STEP S1. Дерево представляет собой последовательность. Я хочу итеративно циклически проходить по дереву и создавать упорядоченный список элементов этого пути между двумя шагами (S1 является первым). 

[graphical example]

           [S1]
            |          
          B3|_________ 
            |         |
           [T1]     [T7]
            |         |
            |       B4|
            |         |
           [S2]     [S3]

Идеальный логический c Пример потока: 

[S1] --> [B3] --> [T1] --> [S2]
          |
          \--> [T7] --> [B4] --> [S3]

Это приводит (в идеале): 

1: [ [S1], [B3], [T7], [B4], [S3] ]
2: [ [S1], [B3], [T1], [S2] ]

Что нужно знать:

  • Конечный шаг может исходить непосредственно из перехода или из ветви
  • Каждый элемент имеет уникальный идентификатор в своем типе
  • Каждый элемент в списках относится к уникальному идентификатору и имеет информацию о следующем соединении

Данные: 

STEPS
con_steps = [[['StepRef', {'Number': '1'}], ['BranchRef', {'Number': '3', 'In': '0'}]], [['StepRef', {'Number': '3'}], ['BranchRef', {'Number': '11', 'In': '0'}]], [['StepRef', {'Number': '5'}], ['BranchRef', {'Number': '12', 'In': '0'}]], [['StepRef', {'Number': '4'}], ['BranchRef', {'Number': '13', 'In': '0'}]], [['StepRef', {'Number': '2'}], ['BranchRef', {'Number': '14', 'In': '0'}]]]

BRANCHES
con_brans = [[['BranchRef', {'Number': '3', 'Out': '0'}], ['TransitionRef', {'Number': '1'}]], [['BranchRef', {'Number': '3', 'Out': '1'}], ['TransitionRef', {'Number': '7'}]], [['BranchRef', {'Number': '4', 'Out': '0'}], ['StepRef', {'Number': '3'}]], [['BranchRef', {'Number': '11', 'Out': '0'}], ['TransitionRef', {'Number': '3'}]], [['BranchRef', {'Number': '11', 'Out': '1'}], ['TransitionRef', {'Number': '5'}]], [['BranchRef', {'Number': '12', 'Out': '0'}], ['TransitionRef', {'Number': '6'}]], [['BranchRef', {'Number': '12', 'Out': '1'}], ['TransitionRef', {'Number': '8'}]], [['BranchRef', {'Number': '13', 'Out': '0'}], ['TransitionRef', {'Number': '4'}]], [['BranchRef', {'Number': '13', 'Out': '1'}], ['TransitionRef', {'Number': '9'}]], [['BranchRef', {'Number': '14', 'Out': '0'}], ['TransitionRef', {'Number': '2'}]], [['BranchRef', {'Number': '14', 'Out': '1'}], ['TransitionRef', {'Number': '10'}]]]

TRANSITIONS
con_trans = [[['TransitionRef', {'Number': '2'}], ['BranchRef', {'Number': '4', 'In': '0'}]], [['TransitionRef', {'Number': '7'}], ['BranchRef', {'Number': '4', 'In': '1'}]], [['TransitionRef', {'Number': '3'}], ['StepRef', {'Number': '4'}]], [['TransitionRef', {'Number': '5'}], ['StepRef', {'Number': '5'}]], [['TransitionRef', {'Number': '1'}], ['StepRef', {'Number': '2'}]], [['TransitionRef', {'Number': '8'}], ['StepRef', {'Number': '2'}]], [['TransitionRef', {'Number': '6'}], ['StepRef', {'Number': '1'}]], [['TransitionRef', {'Number': '9'}], ['StepRef', {'Number': '2'}]], [['TransitionRef', {'Number': '4'}], ['StepRef', {'Number': '1'}]], [['TransitionRef', {'Number': '10'}], ['StepRef', {'Number': '1'}]]]

Цель:

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

Моя попытка: 

    S1 = []
    for i in con_steps:
        if i[0][1]['Number'] == '1':
            print(i)
            #save branch then cont.
            bran1 = i[1][1]['Number']

            tran1 = []
            for j in con_brans:
                if j[0][1]['Number'] == bran1:
                    print(j)
                    tran1.append(j[1][1]['Number'])


                    for k in tran1:
                        bran2 = []
                        for m in con_trans:
                            if m[0][1]['Number'] == k:
                                print(m)

                                if m[1][0] == 'StepRef':
                                    print('last step', m)
                                    S1.append(['1', m[1][1]['Number']])
                                else:
                                    bran2.append(j[1][1]['Number'])
                                    print('continue on', m)

1 Ответ

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

Если вы не хотите использовать рекурсию, вы можете получить тот же результат, используя объект deque (из коллекций), который может действовать как стек и избегать ограничения глубины рекурсии (также легче отлаживать): 

def findNodes(nodeType,number):
    nodeList = {"StepRef":con_steps,"BranchRef":con_brans, "TransitionRef":con_trans}[nodeType]
    return [node for node in nodeList if node[0][1]["Number"] == number]

from collections import deque
def getPaths(start):
    q         = deque()
    result    = []
    firstNode = findNodes("StepRef",start)
    q.append(firstNode)
    seen      = set()
    while q:
        path       = q.popleft()
        nodeLink   = path[-1][1]
        linkType   = nodeLink[0]
        linkNumber = nodeLink[1]["Number"]            
        nextNodes  = findNodes(linkType,linkNumber)
        leafKey    = (path[-1][0][0],path[-1][0][1]["Number"])
        if leafKey in seen or not nextNodes:
            result.append(path)
            continue
        if leafKey[0] == "StepRef":
            seen.add(leafKey)
        for nextNode in nextNodes:
            q.append(path+[nextNode])
    return result

вывод: 

paths = getPaths("1")
for path in paths:
    print( [f"{p[0][0][:1]}{p[0][1]['Number']}" for p in path])


['S1', 'B3', 'T1', 'S2', 'B14', 'T10', 'S1']
['S1', 'B3', 'T1', 'S2', 'B14', 'T2', 'B4', 'S3']
['S1', 'B3', 'T7', 'B4', 'S3', 'B11', 'T3', 'S4', 'B13', 'T4', 'S1']
['S1', 'B3', 'T7', 'B4', 'S3', 'B11', 'T3', 'S4', 'B13', 'T9', 'S2']
['S1', 'B3', 'T7', 'B4', 'S3', 'B11', 'T5', 'S5', 'B12', 'T6', 'S1']
['S1', 'B3', 'T7', 'B4', 'S3', 'B11', 'T5', 'S5', 'B12', 'T8', 'S2']

Кстати, вашей структурой данных очень сложно манипулировать. Вам следует рассмотреть возможность использования общего класса объектов для всех узлов в иерархии, чтобы обход и манипулирование не требовали особой индексации.

...