The Kitchen Sink and Other Oddities

Atabey Kaygun

Graph Algorithms in JGraphT with Common Lisp

Description of the problem

I wrote earlier about interfacing with jgrapht library from clojure. Today it’s common lisp’s turn :)

Java Interop with ABCL

If you need to build a bridge between a java library and lisp, your best option is abcl, or kawa if you prefer writing in scheme. I’ve used it before with Weka, Word2Vec and JavaPlex. So, for today’s post I am using ABCL.

Loading up JGraphT

Let us start with loading up the libraries we need:

(mapc #'require '(:abcl-asdf :java))

I like the thread first macro from clojure, and I am going to use this quite a lot today.

(defmacro -> (x &rest forms)
  (dolist (f forms x)
    (if (listp f)
        (setf x (append (list (car f) x) (cdr f)))
        (setf x (list f x)))))

Next up the java stuff we need:

(-> "org.jgrapht/jgrapht-core"
    abcl-asdf:resolve 
    abcl-asdf:as-classpath
    java:add-to-classpath)

Random Graphs

JGraphT has some good graph generation functions, especially the named graph generation functions. You should check them out. For today’s purposes the following two should be enough:

(defun random-graph (n p &optional
                           (graph-class :SimpleGraph)
                           (directed-p nil))
  (let* ((supplier (-> :SupplierUtil jss:find-java-class jnew))
         (G (jnew (jss:find-java-class graph-class)
                  (#"createIntegerSupplier" supplier)
                  (#"createDefaultEdgeSupplier" supplier)
                  (jnew (java:jclass "java.lang.Boolean") directed-p))))
    (-> :GnpRandomGraphGenerator jss:find-java-class (jnew 20 0.3) (#"generateGraph" G))
    G))

(defun random-weighted-graph (n p &optional
                                   (graph-class :SimpleWeightedGraph)
                                   (directed-p nil))
  (let* ((supplier (-> :SupplierUtil jss:find-java-class jnew))
         (G (jnew (jss:find-java-class graph-class)
                  (#"createIntegerSupplier" supplier)
                  (#"createDefaultWeightedEdgeSupplier" supplier))))
    (-> :GnpRandomGraphGenerator jss:find-java-class (jnew 20 0.3) (#"generateGraph" G))
    G))

Minimum Spanning Trees

I’ll start with two minimum spanning tree algorithms: Kruskal’s and Prim’s algorithms. I did Kruskal’s algorithm in lisp and in clojure here.

(let* ((G (random-graph 40 0.3 :SimpleGraph))
       (tree (-> :KruskalMinimumSpanningTree jss:find-java-class (jnew G) (#"getSpanningTree"))))
  (mapcar #"toString" (jss:set-to-list (#"getEdges" tree))))
("(3 : 16)" "(3 : 14)" "(3 : 10)" "(1 : 3)" "(5 : 7)" "(1 : 12)" "(0 : 11)"
 "(2 : 15)" "(1 : 19)" "(0 : 3)" "(0 : 8)" "(4 : 18)" "(6 : 17)" "(0 : 2)"
 "(0 : 9)" "(2 : 7)" "(2 : 13)" "(4 : 17)" "(0 : 4)")
(let* ((G (random-graph 40 0.3 :SimpleGraph))
      (tree (-> :PrimMinimumSpanningTree jss:find-java-class (jnew G) (#"getSpanningTree"))))
  (mapcar #"toString" (jss:set-to-list (#"getEdges" tree))))
("(10 : 14)" "(1 : 8)" "(7 : 17)" "(0 : 13)" "(3 : 11)" "(12 : 14)"  "(6 : 13)"
 "(5 : 6)" "(0 : 8)" "(6 : 14)" "(13 : 19)" "(0 : 3)" "(2 : 13)" "(6 : 9)" "(1 : 7)"
 "(13 : 16)" "(8 : 15)" "(3 : 18)" "(4 : 6)")

Stoer-Wagner Minimum Cut

I wrote Stoer-Wagner in Clojure. Let us see how this is done in ABCL:

(let* ((G (random-graph 30 0.9))
       (cut (-> :StoerWagnerMinimumCut jss:find-java-class (jnew G) (#"minCut"))))
  (#"toString" cut))
"[16]"

Shortest Path Algorithms

I did not implement Dijkstra in lisp on this blog. But I did some interesting tropic semi-ring matrix implementation of shortest path.

(let* ((G (random-graph 140 0.8 :SimpleDirectedGraph))
       (S (jss:set-to-list (#"vertexSet" G)))
       (a (car S))
       (b (car (reverse S)))
       (path (-> :DijkstraShortestPath jss:find-java-class (jnew G) (#"getPath" a b))))
  (#"toString" path))
"[(0 : 3), (3 : 19)]"

Here is an extra: Johnson’s shortest path algorithm

(let* ((G (random-graph 200 0.4 :SimpleDirectedGraph))
       (S (jss:set-to-list (#"vertexSet" G)))
       (a (car S))
       (b (car (reverse S)))
       (path (-> :JohnsonShortestPaths jss:find-java-class (jnew G) (#"getPath" a b))))
  (#"toString" path))
"[(0 : 7), (7 : 19)]"

Maximum Flow Algorithms

I did Edmond-Karp in lisp and Clojure here. Let’s see how this looks like in JGraphT.

(let* ((G (random-weighted-graph 120 0.5 :SimpleWeightedGraph))
       (S (-> G (#"vertexSet") jss:set-to-list (sort #'<)))
       (a (car S))
       (b (car (reverse S)))
       (flow (-> :EdmondsKarpMFImpl jss:find-java-class (jnew G) (#"getMaximumFlow" a b))))
  (#"toString" flow))
"Flow Value: 7.0
Flow map:
{(1 : 2)=0.0, (6 : 18)=0.0, (1 : 10)=1.0, (2 : 19)=1.0, (0 : 2)=1.0, (8 : 11)=0.0, (15 : 18)=0.0, (4 : 11)=1.0, (0 : 10)=1.0, (3 : 9)=0.0, (4 : 19)=1.0, (13 : 19)=0.0, (4 : 13)=0.0, (1 : 16)=1.0, (1 : 3)=0.0, (4 : 14)=0.0, (5 : 19)=1.0, (15 : 17)=0.0, (4 : 8)=0.0, (12 : 18)=0.0, (5 : 14)=0.0, (6 : 7)=0.0, (12 : 19)=1.0, (3 : 10)=0.0, (18 : 19)=1.0, (0 : 18)=1.0, (1 : 18)=0.0, (10 : 15)=0.0, (16 : 17)=0.0, (5 : 11)=0.0, (6 : 9)=0.0, (8 : 17)=0.0, (10 : 18)=0.0, (4 : 18)=0.0, (1 : 4)=0.0, (8 : 12)=0.0, (2 : 9)=0.0, (7 : 13)=0.0, (1 : 19)=1.0, (3 : 15)=0.0, (9 : 11)=0.0, (3 : 14)=0.0, (1 : 5)=1.0, (7 : 18)=0.0, (4 : 15)=1.0, (12 : 17)=0.0, (1 : 13)=0.0, (0 : 12)=1.0, (6 : 11)=0.0, (0 : 4)=1.0, (4 : 16)=0.0, (5 : 9)=0.0, (11 : 19)=1.0, (0 : 16)=1.0, (2 : 17)=0.0, (7 : 16)=0.0, (2 : 15)=0.0, (0 : 15)=1.0, (9 : 16)=0.0, (7 : 8)=0.0, (12 : 15)=0.0, (8 : 14)=0.0}"

Here is an extra.

(let* ((G (random-weighted-graph 120 0.5 :SimpleWeightedGraph))
       (S (-> G (#"vertexSet") jss:set-to-list (sort #'<)))
       (a (car S))
       (b (car (reverse S)))
       (flow (-> :PushRelabelMFImpl jss:find-java-class (jnew G) (#"getMaximumFlow" a b))))
  (#"toString" flow))
"Flow Value: 4.0
Flow map:
{(16 : 18)=0.0, (4 : 13)=0.0, (5 : 7)=0.0, (2 : 15)=0.0, (1 : 13)=1.0, (1 : 9)=0.0, (11 : 13)=1.0, (3 : 18)=0.0, (5 : 13)=0.0, (5 : 12)=1.0, (5 : 15)=0.0, (12 : 14)=0.0, (6 : 18)=0.0, (9 : 17)=0.0, (6 : 12)=0.0, (1 : 4)=0.0, (1 : 17)=0.0, (12 : 19)=1.0, (1 : 3)=0.0, (1 : 15)=0.0, (1 : 12)=0.0, (10 : 19)=0.0, (0 : 13)=1.0, (5 : 9)=0.0, (0 : 2)=1.0, (7 : 9)=0.0, (3 : 17)=0.0, (17 : 19)=1.0, (13 : 18)=0.0, (13 : 19)=1.0, (3 : 10)=0.0, (0 : 17)=1.0, (6 : 7)=0.0, (0 : 11)=1.0, (2 : 18)=0.0, (8 : 19)=0.0, (5 : 11)=1.0, (8 : 18)=0.0, (2 : 11)=1.0, (7 : 15)=0.0, (7 : 11)=0.0, (9 : 18)=0.0, (1 : 19)=1.0, (5 : 17)=0.0, (10 : 14)=0.0, (3 : 15)=0.0, (9 : 11)=0.0, (6 : 19)=0.0, (4 : 7)=0.0, (8 : 17)=0.0, (8 : 9)=0.0, (16 : 17)=0.0, (15 : 17)=0.0, (11 : 14)=0.0}"

Clique Finding

I did Bron-Kerbosch in clojure here. Let us see how this looks like in JGraphT:

(let* ((G (random-graph 140 0.5 :SimpleGraph))
       (cliques (-> :BronKerboschCliqueFinder jss:find-java-class (jnew G) (#"maximumIterator")))
       (res nil))
  (do ((clique (#"next" cliques) (#"next" cliques)))
      ((not (#"hasNext" cliques)) res)
    (push (jss:set-to-list clique) res)))
((18 13 14) (13 14 15) (18 11 14) (16 10 15) (10 13 15) (9 13 15)
 (17 7 14) (16 7 12) (7 12 14) (16 7 10) (7 9 12) (18 6 14) (17 6 14)
 (18 6 8) (6 8 9) (18 19 5) (18 5 11) (16 5 7) (17 3 6) (2 19 14)
 (17 2 14) (16 1 15) (16 1 12) (16 1 5) (0 16 15) (0 16 5))