Today, I am going to write a clojure function that solves vertex cover problem for a given undirected graph.
Given a graph \(G = (V,E)\) a vertex cover is a subset \(C\subseteq V\) such that when we add all edges incident to every vertex in \(C\) we get all vertices of \(G\). For example, any vertex \(v\) in the complete graph \(K_n\) would form a cover by itself since every other vertex is connected to \(v\). On the other hand, any graph on \(n\) vertices with no edges is on the opposite end since one would need all of \(V\) to get a cover.
Algorithm Cover
Input: A graph G as a list of neighbors for each vertex.
A subset S of vertices.
Output: A subset C of vertices covering G.
Begin
If G is empty then
Return S
End If
Take a vertex v with the largest degree.
If deg(v) = 0 then
Return S
End If
Let H be G from which all edges incident to v are removed.
Return Cover( H , S ∪ {v} )
EndAs I described above, a graph is a map of subsets of neighbors.
(def G {0 #{1 2 3}, 1 #{0 2}, 2 #{0 1 3 4}, 3 #{0 2}, 4 #{2}}) #'covering/GNext, a function that finds a vertex with the largest degree.
(defn largest-degree [G]
(->> (into [] G)
(map (fn [[x y]] [x (count y)]))
(sort #(> (last %1) (last %2)))
first
first))#'covering/largest-degreeLet us test:
(G (largest-degree G))#{0 1 4 3}Now, a function that removes a vertex and every edge incident to it.
(defn remove-vertex [v G]
(->> (dissoc G v)
(map (fn [x] {(key x) (->> (val x)
(remove #{v})
(into #{}))}))
(into {}))) #'covering/remove-vertexLet us test:
(remove-vertex 2 G){0 #{1 3}, 1 #{0}, 3 #{0}, 4 #{}}As for the function, I’ll write
(defn cover
([G] (cover G []))
([G S] (let* [v (largest-degree G)
H (remove-vertex v G)]
(if (or (empty? G)
(empty? (G v)))
S
(recur H (conj S v))))))#'covering/coverLet us test.
(cover G)[2 0]How do we know that we get the correct answer? Well, if we remove all of the vertices in the cover, what remains has to be an independent subset. Let us see if this works.
(loop [S (cover G)
H G]
(if (empty? S)
H
(recur (rest S) (remove-vertex (first S) H)))){1 #{}, 3 #{}, 4 #{}}Let us construct a random tree and test our code on it:
(defn random-tree [n]
(->> (range 1 (* 2 n))
(map (fn [x] {(rand-int x) #{x}}))
(reduce #(merge-with union %1 %2))
(into {})))
(let [tree (random-tree 100)]
(loop [S (cover tree)
H tree]
(if (empty? S)
H
(recur (rest S) (remove-vertex (first S) H)))))#'covering/random-tree
{119 #{}, 31 #{}, 40 #{}, 56 #{}, 61 #{}, 111 #{}, 134 #{}, 35 #{}, 76 #{}, 16 #{}, 98 #{}, 73 #{}, 10 #{}}