Kruskal's Algorithm Implemented in Clojure

Description of the problem

Today, I am going to implement Kruskal’s Algorithm in Clojure.

Kruskal’s algorithm finds a spanning tree within a graph. A spanning tree of a connected graph is a maximal connected cycle-free subgraph of the graph. If the graph is disconnected then each connected component has a spanning tree, and the full set of spanning trees of the connected components is called a spanning forest, obviously!

Algorithm

I am going to concentrate on the case where edges have no direction or weights. In any case, the algorithm is pretty simple.

Algorithm Kruskal
Input: An undirected graph G given as a set of edges
Output: A spanning tree of G
Begin
  Let Tree be the empty set
  Let H be G
  While H is non-empty 
    Let e be a random edge from H
    If adding e to Tree does not create a cycle
       Add e to Tree
    End If
  Remove e from H
  End While
  Return Tree
End

In the weighted version, one has to replace “Let e be a random edge in H” line with “Let e be a cheapest edge in H”. For the directed graphs, checking whether adding the edge e to the already formed tree creates a cycle has to bo modified to take into account oriented cycles.

An implementation

I am going to represent graphs using sets of edges:

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

#'kruskal/graph

First, a function checks if adding an edge creates a cycle:

(defn creates-a-cycle? [path tree]
    (let [e (->> tree (filter #(not (empty? (intersection path %)))) first)]
       (cond (nil? e) false
             (subset? e path) true
             :else (recur (union path e) (remove #{e} tree))))))

(creates-a-cycle? #{0 1} #{#{1 2} #{2 3} #{3 0}})
(creates-a-cycle? #{0 1} #{#{1 2} #{2 3}})

#'kruskal/creates-a-cycle?
true
false

And here is my implementation of Kruskal’s algorithm.

(defn kruskal [graph]
   (loop [H (into [] graph)
          tree #{}]
      (if (empty? H)
          tree
          (let [edge (rand-nth H)]
             (recur (remove #{edge} H)
                    (if (creates-a-cycle? edge tree)
                        tree
                        (conj tree edge)))))))

#'kruskal/kruskal

Here is a test:

(kruskal graph)

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

Here is another larger test whose graph I stole from here:

(def railway-connections 
 #{
   #{"Birmingham" "Sheffield"}
   #{"Birmingham" "Leeds"}
   #{"Birmingham" "Bristol"}
   #{"Birmingham" "Liverpool"}
   #{"Birmingham" "Manchester"}

   #{"Bristol" "Leeds"}
   #{"Bristol" "Liverpool"}
   #{"Bristol" "Manchester"}

   #{"Leeds" "Liverpool"}
   #{"Leeds" "Manchester"}

   #{"Liverpool" "Manchester"}

   #{"London" "Birmingham"}
   #{"London" "Sheffield"}
   #{"London" "Leeds"}
   #{"London" "Bristol"}
   #{"London" "Liverpool"}
   #{"London" "Manchester"}

   #{"Sheffield" "Leeds"}
   #{"Sheffield" "Liverpool"}
   #{"Sheffield" "Manchester"}
})

(kruskal railway-connections)

#'kruskal/railway-connections
#{#{"Sheffield" "Leeds"} #{"Manchester" "Liverpool"} #{"Birmingham" "Liverpool"} #{"Manchester" "London"} #{"Liverpool" "Bristol"} #{"Leeds" "London"}}