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.
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
EndThe 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.
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/GHere 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-edgesNext, 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-pathsLet 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]}