Finding all paths in a directed graph with cycles

Question

I am working on a problem which requires finding all paths between two nodes in a directed graph. The graph may have cycles.

Notice that this particular implementation approach is an iterative DFS.

Several approaches I've considered are as follows -

• BFS does not appear to have a way to neatly manage this kind of pathing relationships between nodes.

• I don't see an easy mechanism for a DFS recursive algorithm to pass up the path when the terminating node is found. (Likely enough it could be done, if I implement a Maybe monad kind of thing).

• Creating a GRAPH-PARENT routine. That would add a decent amount of churn (& bugs) in the existing code.

Abstractly, what needs to happen is a tree needs to be generated, with the start node as root, and all leafs are the terminating nodes. Each path from leaf to root is a legal path. That is what a recursive DFS would trace out.

I'm reasonably sure it can be done here, but I don't see exactly how to do it.

I've defined a protocol for this algorithm where GRAPH-EQUAL and GRAPH-NEXT can be defined for arbitrary objects.

The debug node type is a SEARCH-NODE, and it has the data accessor 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

See A Very General Method for Computing Shortest Paths for an algorithm that can return all paths in a graph (even when there are cycles) as regular expressions over the alphabet of edges in finite time (assuming a finite graph).

Answer 2

You need to pass the path list (mark-list) along with the nodes, since that is part of the state. I've renamed it path in this code:

(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)))))))))