recorrido - programa de grafos en python

Cómo atravesar gráficos dirigidos cíclicos con algoritmo DFS modificado

Question

VISIÓN GENERAL

Estoy tratando de averiguar cómo atravesar gráficos cíclicos dirigidos usando algún tipo de algoritmo iterativo DFS. Aquí hay una pequeña versión mcve de lo que actualmente implementé (no trata con los 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)

El código anterior está probando un par de casos, el primero sería algún tipo de representación del siguiente gráfico:

El segundo es el caso más simple de un gráfico que contiene un bucle "infinito" {a->b, b->a}

REQUISITOS

• No existirá una cosa como "ciclos infinitos", digamos que cuando se encuentra un "ciclo infinito", habrá un umbral máximo (var global) para indicar cuándo dejar de bucle alrededor de esos "ciclos pseudoinfinitos"
• Todos los nodos de la gráfica pueden crear ciclos, pero existirá un nodo especial llamado Repeat en el que puede indicar cuántas iteraciones hay para recorrer el ciclo.
• El mcve anterior que he publicado es una versión iterativa del algoritmo transversal que no sabe cómo tratar con los gráficos cíclicos . Idealmente, la solución también sería iterativa, pero si existe una solución recursiva mucho mejor, sería genial
• La estructura de datos de la que estamos hablando aquí no debería llamarse "gráficos acíclicos dirigidos" realmente porque en este caso, cada nodo tiene sus hijos ordenados , y en los gráficos las conexiones de nodo no tienen orden.
• Todo puede estar conectado a cualquier cosa en el editor. Podrás ejecutar cualquier combinación de bloques y la única limitación es el contador de ejecución, que se desbordará si realizas un bucle interminable o demasiadas iteraciones.
• El algoritmo conservará la ejecución del método de inicio / medio / posterior del nodo de manera similar al fragmento anterior.

PREGUNTA

¿Podría alguien proporcionar algún tipo de solución que sepa cómo atravesar ciclos infinitos / finitos?

Referencias

Si la pregunta no está clara aún en este punto, puede leer más sobre este problema en este article , toda la idea será usar el algoritmo de recorrido para implementar una herramienta similar como la que se muestra en ese artículo.

Aquí hay una captura de pantalla que muestra todo el poder de este tipo de estructura de datos que quiero averiguar cómo recorrer y ejecutar:

Answer 1

Antes de comenzar, ejecute el código en CodeSkulptor! También espero que los comentarios elaboren lo que he hecho lo suficiente. Si necesita más explicación, mire mi explicación del enfoque recursivo debajo del código.

# If you don''t want global variables, remove the indentation procedures
indent = -1

MAX_THRESHOLD = 10
INF = 1 << 63

def whitespace():
    global indent
    return ''|  '' * (indent)

class Node:
    def __init__(self, name, num_repeats=INF):
        self.name = name
        self.num_repeats = num_repeats

    def start(self):
        global indent
        if self.name.find(''Sequence'') != -1:
            print whitespace()
            indent += 1
        print whitespace() + ''%s_start'' % self.name

    def middle(self):
        print whitespace() + ''%s_middle'' % self.name

    def end(self):
        global indent
        print whitespace() + ''%s_end'' % self.name
        if self.name.find(''Sequence'') != -1:
            indent -= 1
            print whitespace()

def dfs(graph, start):
    visits = {}
    frontier = [] # The stack that keeps track of nodes to visit

    # Whenever we "visit" a node, increase its visit count
    frontier.append((start, start.num_repeats))
    visits[start] = visits.get(start, 0) + 1

    while frontier:
        # parent_repeat_count usually contains vertex.repeat_count
        # But, it may contain a higher value if a repeat node is its ancestor
        vertex, parent_repeat_count = frontier.pop()

        # Special case which signifies the end
        if parent_repeat_count == -1:
            vertex.end()
            # We''re done with this vertex, clear visits so that 
            # if any other node calls us, we''re still able to be called
            visits[vertex] = 0
            continue

        # Special case which signifies the middle
        if parent_repeat_count == -2:
            vertex.middle()
            continue  

        # Send the start message
        vertex.start()

        # Add the node''s end state to the stack first
        # So that it is executed last
        frontier.append((vertex, -1))

        # No more children, continue
        # Because of the above line, the end method will
        # still be executed
        if vertex not in graph:
            continue

        ## Uncomment the following line if you want to go left to right neighbor
        #### graph[vertex].reverse()

        for i, neighbor in enumerate(graph[vertex]):
            # The repeat count should propagate amongst neighbors
            # That is if the parent had a higher repeat count, use that instead
            repeat_count = max(1, parent_repeat_count)
            if neighbor.num_repeats != INF:
                repeat_count = neighbor.num_repeats

            # We''ve gone through at least one neighbor node
            # Append this vertex''s middle state to the stack
            if i >= 1:
                frontier.append((vertex, -2))

            # If we''ve not visited the neighbor more times than we have to, visit it
            if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
                frontier.append((neighbor, repeat_count))
                visits[neighbor] = visits.get(neighbor, 0) + 1

def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
    visits[node] = visits.get(node, 0) + 1

    node.start()

    if node not in graph:
        node.end()
        return

    for i, neighbor in enumerate(graph[node][::-1]):
        repeat_count = max(1, parent_repeat_count)
        if neighbor.num_repeats != INF:
            repeat_count = neighbor.num_repeats

        if i >= 1:
            node.middle()

        if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
            dfs_rec(graph, neighbor, repeat_count, visits)

    node.end()  
    visits[node] = 0

Sequence1 = Node(''Sequence1'')
MtxPushPop1 = Node(''MtxPushPop1'')
Rotate1 = Node(''Rotate1'')
Repeat1 = Node(''Repeat1'', 2)

Sequence2 = Node(''Sequence2'')
MtxPushPop2 = Node(''MtxPushPop2'')
Translate = Node(''Translate'')
Rotate2 = Node(''Rotate2'')
Rotate3 = Node(''Rotate3'')
Scale = Node(''Scale'')
Repeat2 = Node(''Repeat2'', 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 ''-''*40

dfs_rec(cyclic_graph, Sequence1)

print ''-''*40

dfs({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)

print ''-''*40

dfs_rec({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)

La entrada y la salida (bien formateada y con sangría) se pueden encontrar here . Si desea ver cómo formateé la salida, consulte el código, que también se puede encontrar en CodeSkulptor .

Correcto, a la explicación. La solución recursiva más fácil de entender pero mucho más ineficiente, que usaré para ayudar a explicar, sigue:

def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
    visits[node] = visits.get(node, 0) + 1

    node.start()

    if node not in graph:
        node.end()
        return

    for i, neighbor in enumerate(graph[node][::-1]):
        repeat_count = max(1, parent_repeat_count)
        if neighbor.num_repeats != INF:
            repeat_count = neighbor.num_repeats

        if i >= 1:
            node.middle()

        if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
            dfs_rec(graph, neighbor, repeat_count, visits)

    node.end()  
    visits[node] = 0

1. Lo primero que hacemos es visitar el nodo. Hacemos esto incrementando el número de visitas del nodo en el diccionario.
2. A continuación, planteamos el evento de start del nodo.
3. Hacemos una comprobación simple para ver si el nodo es un nodo sin hojas (hoja) o no. Si es así, levantamos el evento end y regresamos.
4. Ahora que hemos establecido que el nodo tiene vecinos, iteramos a través de cada vecino. Nota al margen: invierto la lista de vecinos (utilizando el graph[node][::-1] ) en la versión recursiva para mantener el mismo orden (de derecha a izquierda) del recorrido de vecinos como en la versión iterativa.
   1. Para cada vecino, primero calculamos el conteo de repetición. El recuento de repeticiones se propaga (se hereda) a través de los nodos del antepasado, por lo que se utiliza el recuento de repeticiones heredado a menos que el vecino contenga un valor de recuento de repeticiones.
   2. Levantamos el evento middle del nodo actual ( no el vecino) si se procesa el segundo vecino (o mayor).
   3. Si el vecino puede ser visitado, el vecino es visitado. La verificación de visitabilidad se realiza verificando si el vecino ha sido visitado menos de a) veces MAX_THRESHOLD (para ciclos pseudoinfinitos) yb) los tiempos de conteo de repetición calculados anteriormente.
5. Ahora hemos terminado con este nodo; Levante el evento end y borre sus visitas en la tabla hash. Esto se hace para que si otro nodo lo vuelve a llamar, no falla la verificación de visitabilidad y / o se ejecuta por menos del número requerido de veces.

Answer 2

De acuerdo con comment66244567 : reducir el gráfico a un árbol al ignorar los enlaces a los nodos visitados y realizar una búsqueda en primer lugar, ya que esto produciría un árbol de aspecto más natural (y probablemente más equilibrado):

def traverse(graph,node,process):
    seen={node}
    current_level=[node]
    while current_level:
        next_level=[]
        for node in current_level:
            process(node)
            for child in (link for link in graph.get(node,[]) if link not in seen):
                next_level.append(child)
                seen.add(child)
        current_level=next_level

Con su gráfico y def process(node): print node , esto produce:

In [24]: traverse(cyclic_graph,Sequence1,process)
Sequence1
MtxPushPop1
Rotate1
Sequence2
Repeat1
MtxPushPop2
Translate
Rotate2
Rotate3
Scale
Repeat2
Mesh

El otro algoritmo BFS, el DFS de profundización iterativo (usa menos memoria a costa de la velocidad) no va a ganar nada en este caso: ya que tiene que almacenar referencias a nodos visitados, ya consume la memoria O (n) . Tampoco necesita generar resultados intermedios (pero puede hacerlo de todos modos, por ejemplo, yield algo después de procesar un nivel).