Implementing Karger's minimum cut algorithm in functional paradigm

Question

I have no problem in implementing this algorithm in any imperative language, but I am struggling implementing it in Clojure or any other functional language. A lot of algorithms are described in terms of working with mutable data structures and imperative loops and it is hard for me to translate all of those to a functional domain.

Here is my incomplete attempt (a draft, not a working implementation) at implementing it in Clojure using adjacency lists as graph representation:

(ns karger.core
  (:require [clojure.string :as string]))

(defn load-data []
    (zipmap 
     (range 1 1000)
     (map rest (map read-string
       (string/split (slurp "data.txt") #"\n")))))

(defn min-cut [graph] 
  (let [start (rand-int (count graph))
        end (rand-int (graph start))
        start-list (nth graph start)]
    (for [x (graph end)
          :when (not= x start)]
      (assoc graph start (conj start-list x)))
      ))

(count (load-data))

Can anyone give me a reference implementation of this algorithm (preferably written in Clojure)? Also I would like if someone gave me a general advice of translating an algorithm described in imperative terms to a functional domain.

Thanks in advance!

UPDATE #1

Here is a link to algorithm implementation written in Python: http://pastebin.com/WwWCtxpu

Answer 1

There are fundamental problems with your code as is:

• your start-list binding is a number and cannot be conjed to'
• you are calling assoc and ignoring the return value, thus making it a no-op.
• you are using for as if it were a looping construct (it is a list comprehension)
• you are calling nth on a hash-map, which will always fail (zipmap returns a hash-map)

In general the idea in functional programming is to lift mutable variables into immutable local bindings by making the "state of the world" entirely encapsulated by the function arguments, and making function calls with refined versions of that state.

Here is a working implementation from scratch based on the python solution you posted, and the graph file used by the java example here

(ns min-cut.core
  (:require [clojure.java.io :as io]
            [clojure.string :as string]
            [clojure.pprint :refer [pprint]]))

(defn make-maps
  [filename]
  (reduce (fn [graph line]
            (let [[node & edges] (->> line
                                      (#(string/split % #"\W+"))
                                      (remove #{""})
                                      (map read-string))]
              (assoc graph node (set edges))))
          {}
          (line-seq (io/reader filename))))

(defn karger
  [graph]
  (if (<= (count (keys graph))
          2)
    (count (graph (apply min (keys graph))))
    (let [start (rand-nth (keys graph))
          finish (rand-nth (vec (graph start)))
          graph (loop [g graph
                       [edge & edges] (seq (graph finish))]
                  (if-not edge
                    g
                    (recur
                     (if (= edge start)
                       g
                       (update-in g [start] conj edge))
                     edges)))
          graph (loop [g graph
                       [edge & edges] (seq (graph finish))]
                  (if-not edge
                    g
                    (let [gr (update-in g [edge] disj finish)
                          gr (if (= edge start)
                               gr
                               (update-in gr [edge] conj start))]
                      (recur gr edges))))
          graph (dissoc graph finish)]
      (recur graph))))

(defn -main
  [& [file]]
  (let [file (or file "kargerAdj.txt")
        graph (make-maps file)]
    (println "min cut is: "
             (reduce min (repeatedly 1801 #(karger graph))))))

This is a very literal translation of the python code, so there are multiple places this code could be improved. For starters the two loops in the karger function could likely be replaced by a single reduce which would be much more concise and clear.

Note that no value that is created in this code is ever mutated - values are rebound but none of the incoming data structures are changed, and the only global definitions used are the functions make-maps, karger, and -main - all data is locally bound and passed to the next user.