Обзор
Я пытаюсь понять, как перемещаться направленные циклические графики, используя какой-то итеративный алгоритм DFS. Вот небольшая версия mcve того, что я сейчас реализовал (это не касается циклов):
class Node(object):
def __init__(self, name):
self.name = name
def start(self):
print '{}_start'.format(self)
def middle(self):
print '{}_middle'.format(self)
def end(self):
print '{}_end'.format(self)
def __str__(self):
return "{0}".format(self.name)
class NodeRepeat(Node):
def __init__(self, name, num_repeats=1):
super(NodeRepeat, self).__init__(name)
self.num_repeats = num_repeats
def dfs(graph, start):
"""Traverse graph from start node using DFS with reversed childs"""
visited = {}
stack = [(start, "")]
while stack:
# To convert dfs -> bfs
# a) rename stack to queue
# b) pop becomes pop(0)
node, parent = stack.pop()
if parent is None:
if visited[node] < 3:
node.end()
visited[node] = 3
elif node not in visited:
if visited.get(parent) == 2:
parent.middle()
elif visited.get(parent) == 1:
visited[parent] = 2
node.start()
visited[node] = 1
stack.append((node, None))
# Maybe you want a different order, if it so, don't use reversed
childs = reversed(graph.get(node, []))
for child in childs:
if child not in visited:
stack.append((child, node))
if __name__ == "__main__":
Sequence1 = Node('Sequence1')
MtxPushPop1 = Node('MtxPushPop1')
Rotate1 = Node('Rotate1')
Repeat1 = NodeRepeat('Repeat1', num_repeats=2)
Sequence2 = Node('Sequence2')
MtxPushPop2 = Node('MtxPushPop2')
Translate = Node('Translate')
Rotate2 = Node('Rotate2')
Rotate3 = Node('Rotate3')
Scale = Node('Scale')
Repeat2 = NodeRepeat('Repeat2', num_repeats=3)
Mesh = Node('Mesh')
cyclic_graph = {
Sequence1: [MtxPushPop1, Rotate1],
MtxPushPop1: [Sequence2],
Rotate1: [Repeat1],
Sequence2: [MtxPushPop2, Translate],
Repeat1: [Sequence1],
MtxPushPop2: [Rotate2],
Translate: [Rotate3],
Rotate2: [Scale],
Rotate3: [Repeat2],
Scale: [Mesh],
Repeat2: [Sequence2]
}
dfs(cyclic_graph, Sequence1)
print '-'*80
a = Node('a')
b = Node('b')
dfs({
a : [b],
b : [a]
}, a)
Вышеприведенный код проверяет несколько случаев, первый из них будет представлять собой некоторый вид представленного ниже графика:
Второй - простейший случай одного графика, содержащего один "бесконечный" цикл {a->b, b->a}
ПОТРЕБНОСТИ
- Не существует такой вещи, как "бесконечные циклы", скажем, когда будет найден один "бесконечный цикл", будет максимальный порог (глобальный var), чтобы указать, когда прекратить цикл вокруг этих "псевдо бесконечных" циклы "
- Все узлы графа могут создавать циклы, но там будет существовать специальный node, называемый
Repeat, где вы можете указать, сколько итераций цикла цикла цикла - Вышеупомянутый mcve, который я опубликовал, является итеративной версией алгоритма обхода, который не знает, как обращаться с циклическими графами. В идеале решение было бы также итеративным, но если бы существовало гораздо лучшее рекурсивное решение, это было бы здорово
- Структура данных, о которой мы говорим здесь, не должна называться "направленными ациклическими графами", потому что в этом случае каждый node имеет упорядоченные дочерние элементы, а в графах node соединения не имеют порядка.
- Все может быть связано с чем-либо в редакторе. Вы сможете выполнить любую комбинацию блоков, и единственным ограничением является счетчик выполнения, который будет переполняться, если вы сделали бесконечный цикл или слишком много итераций.
- Алгоритм сохранит выполнение метода start/middle/after node аналогично приведенному выше фрагменту
Вопрос
Может ли кто-нибудь предоставить какое-то решение, которое знает, как пройти бесконечные/конечные циклы?
ЛИТЕРАТУРЫ
Если на данный момент вопрос еще не ясен, вы можете прочитать об этом подробнее об этой статье вся идея будет используя алгоритм обхода для реализации аналогичного инструмента, подобного показанному в этой статье.
Вот скриншот, показывающий всю мощь такого типа структуры данных. Я хочу выяснить, как пройти & run:
