Listing All Paths in a Graph

Description of the problem

Assume we have an undirected graph given as a hash-map of vertices vs the set of their neighbors. Today I am going to describe an algorithm and a clojure implementation that lists all paths between any two vertices.

An algorithm

This is a variation of breath first search.

Function AllPaths
Input: A graph G as a hash-map of vertices and their neighbors.
       A pair of vertices a and b.
       A set P of already constructed paths.
Output: The set of all paths between a and b in G.

Begin
  If G is empty then
     Return the empty set
  End If

  Let Q be the empty set
  For each alpha in P do
      Adjoin a to alpha and add newly constructed path to Q
  End For 

  If a = b then
     Return Q
  Else 
     Let H be the graph from which all edges
         incident to a is removed
     Let R be the empty set
     For each neighbor x of a in G do
         Add AllPaths(H,x,b,Q) to R
     End For
     Return R
  End If
End

The worst case complexity of the algorithm is O(d^D) where d is the maximum degree within G and D is the diameter of the graph G. Though the average complexity will be much less since recursion works by removing all edges incident to a vertex.

An implementation in Clojure

I am going to represent an undirected graph via a hash-map of neighbors.

(def G {0 #{1 2}, 1 #{3 4}, 2 #{3 4}, 3 #{5}, 4 #{5}})

#'all-paths/G

Here is a function that removes all edges incident to a vertex

(defn remove-edges [v G]
   (->> (dissoc G v)
        (map (fn [x] {(key x) (->> (val x)
                                   (remove #{v})
                                   (into #{}))}))
        (into {})))   

#'all-paths/remove-edges

Next, my implementation of all-paths:

(defn all-paths
  ([a b G] (all-paths a b G #{[]}))
  ([a b G P]
      (let [Q (map #(conj % a) P)]
         (cond (empty? G) #{[]}
               (= a b)    (into #{} Q)
               :else      (let [H (remove-edges a G)]
                             (->> (map #(all-paths % b H Q) (G a))
                                  (reduce union)))))))

#'all-paths/all-paths

Let us test:

(all-paths 0 5 G)

#{[0 2 4 5] [0 1 4 5] [0 1 3 5] [0 2 3 5]}

Next, I am going test the algorithm with the complete graph on n vertices.

(defn complete-graph [n]
  (let [vertices (into #{} (range n))]
     (->> (map (fn [x] {x (remove #{x} vertices)}) vertices)
          (into {}))))

(complete-graph 5)
(all-paths 0 4 (complete-graph 5))

#'all-paths/complete-graph
{0 (1 4 3 2), 1 (0 4 3 2), 4 (0 1 3 2), 3 (0 1 4 2), 2 (0 1 4 3)}
#{[0 3 1 2 4] [0 2 3 1 4] [0 3 2 1 4] [0 1 3 4] [0 1 4] [0 2 4] [0 2 3 4] [0 3 4] [0 3 2 4] [0 2 1 4] [0 1 3 2 4] [0 4] [0 1 2 3 4] [0 2 1 3 4] [0 3 1 4] [0 1 2 4]}

The final test is going to be on a large random tree where between any two vertices there is only one path.

(defn random-tree [n]
   (->> (range 1 (* 2 n))
        (map (fn [x] {(rand-int x) #{x}}))
        (reduce  #(merge-with union %1 %2))
        (into {})))

(all-paths 0 9 (random-tree 5))
(all-paths 0 29 (random-tree 15))
(all-paths 0 199 (random-tree 100))

#'all-paths/random-tree
#{[0 2 9]}
#{[0 1 2 18 29]}
#{[0 1 76 91 92 121 199]}