Encontrar todas las rutas en un gráfico dirigido con ciclos

Question

Estoy trabajando en un problema que requiere encontrar todas las rutas entre dos nodos en un gráfico dirigido. El gráfico puede tener ciclos.

Observe que este enfoque de implementación particular es un DFS iterativo.

varios enfoques que he considerar son los siguientes -

• BFS no parecen tener una forma de gestionar cuidadosamente este tipo de relaciones pathing entre nodos.

• No veo un mecanismo fácil para que un algoritmo recursivo DFS pase por la ruta cuando se encuentra el nodo de terminación. (Lo más probable es que se podría hacer, si implemento un tipo de cosa Maybe Monaco).

• Creando una rutina GRAPH-PARENT. Eso agregaría una buena cantidad de churn (& bugs) en el código existente.

En abstracto, lo que se necesita es un árbol necesita ser generada, con el nodo de inicio como root, y todas las hojas son los nodos de terminación. Cada camino de hoja a raíz es una ruta legal. Eso es lo que un DFS recursivo trazaría.

Estoy razonablemente seguro de que se puede hacer aquí, pero no veo exactamente cómo hacerlo.

He definido un protocolo para este algoritmo donde se pueden definir GRAPH-EQUAL y GRAPH-NEXT para objetos arbitrarios.

El tipo de nodo de depuración es un SEÑAL DE BÚSQUEDA, y tiene el acceso de datos o SEARCH-NODE-DATA.

(defun all-paths (start end) 
    (let ((stack (list start)) 
     (mark-list (list start)) ;I've chosen to hold marking information local to all-paths, instead of marking the objects themselves. 
     (all-path-list '()))  ; Not used yet, using debug statements to think about the problem 
    (do () ;; intializing no variables 
    ;; While Stack still has elements 
     ((not stack))   
     (let ((item (pop stack))) 
    ;; I'm looking at the item. 
    (format t "I: ~a~%" (search-node-data item)) 
    (cond ((graph-equal item end) 
      (format t "*Q: ~a~%" (loop for var in stack collect (search-node-data var))) 
      ;;Unmark the terminal node so we can view it it next time. 
      (setf mark-list (remove item mark-list)))) 

     (loop for next in (graph-next item) 
      do   
      (cond ((not (in next mark-list :test #'graph-equal)) 
        ;; mark the node 
        (push next mark-list) 
        ;;Put it on the stack 
        (push next stack)))))))) 

Answer 1

Ver A Very General Method for Computing Shortest Paths para un algoritmo que puede regresar todas las rutas en una gráfica (incluso cuando hay ciclos) como expresiones regulares sobre el alfabeto de los bordes en tiempo finito (suponiendo un gráfico finito).

Answer 2

Debe pasar la lista de ruta (mark-list) junto con los nodos, ya que es parte del estado. Lo he cambiado de nombre path en este código:

(defun all-paths (start end) 
    (let ((stack (list '(start (start)))) ; list of (node path) elements 
     (all-path-list '())) 
    (do () 
     ((not stack))   
     (let ((item (pop stack))) 
     (let ((node (first item)) 
       (path (second item))) 
      (format t "I: ~a~%" (search-node-data node)) 
      (cond ((graph-equal node end) 
       (format t "*Q: ~a~%" 
         (loop for var in path 
           collect (search-node-data var))))) 
      (loop for next in (graph-next node) 
       do   
       (cond ((not (in next path :test #'graph-equal)) 
         (push (list next (cons next path)) stack)))))))))