VISÃO GLOBAL

Estou tentando descobrir como atravessargráficos cíclicos direcionados usando algum tipo de algoritmo iterativo DFS. Aqui está uma pequena versão mcve do que eu atualmente implementei (ele não lida com ciclos):

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's 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)

O código acima está testando alguns casos, o primeiro seria algum tipo de representação do gráfico abaixo:

O segundo é o caso mais simples de um gráfico que contém um loop "infinito"{a->b, b->a}

REQUISITOS

Não existirá algo como "ciclos infinitos", digamos que quando um "ciclo infinito" for encontrado, haverá um limite máximo (var global) para indicar quando parar de girar em torno desses "ciclos pseudo-infinitos"Todos os nós do gráfico são capazes de criar ciclos, mas haverá um nó especial chamadoRepeat onde você pode indicar quantas iterações devem percorrer o cicloO mcve acima que eu publiquei é uma versão iterativa do algoritmo transversal quenão sabe lidar com gráficos cíclicos. Idealmente, a solução também seria iterativa, mas se existir uma solução recursiva muito melhor, isso seria ótimoA estrutura de dados de que falamos aqui não deve ser chamada de "gráficos acíclicos direcionados", porque, nesse caso,cada nó tem seus filhos ordenados, e nos gráficos as conexões dos nós não têm ordem.Tudo pode ser conectado a qualquer coisa no editor. Você poderá executar qualquer combinação de blocos e a única limitação é o contador de execução, que será excedido se você fizer um loop sem fim ou muitas iterações.O algoritmo preservará a execução do método de início / meio / após o nó da mesma forma que o snippet acima

PERGUNTA, QUESTÃO

Alguém poderia fornecer algum tipo de solução que saiba atravessar ciclos infinitos / finitos?

REFERÊNCIAS

Se a pergunta ainda não estiver clara neste momento, você pode ler mais sobre este problema nesteartigo, toda a ideia usará o algoritmo transversal para implementar uma ferramenta semelhante à mostrada nesse artigo.

Aqui está uma captura de tela mostrando todo o poder desse tipo de estrutura de dados que eu quero descobrir como percorrer e executar: