The Kitchen Sink and Other Oddities

Atabey Kaygun

Graph Algorithms in Clojure with JGraphT

Description of the problem

In this blog, I have implemented many graph algorithms from scratch either in Common Lisp, or in Clojure, or sometimes in Scala. Today, I am going to show you how to use the java graph library JGraphT to apply some of these graph algorithms on random graphs. JGrapjT is similar to iGraph or networkx in its functionality, but it is more flexible in that one can use any java object as a vertex. It is not as extensive as Sage Math’s Graph Library, but it is very useful.

Dependencies and the name-space

For today’s examples, the only dependency I need is the JGraphT:

{:deps {org.jgrapht/jgrapht-core {:mvn/version "1.5.1"}}}

and the name-space is defined as follows:

(ns jg
  (:import [org.jgrapht.graph
            SimpleGraph
            SimpleWeightedGraph
            SimpleDirectedGraph
            SimpleDirectedWeightedGraph
            DefaultEdge
            DefaultWeightedEdge]
           [org.jgrapht.alg TransitiveClosure StoerWagnerMinimumCut]
           [org.jgrapht.alg.flow EdmondsKarpMFImpl]
           [org.jgrapht.alg.shortestpath JohnsonShortestPaths DijkstraShortestPath]
           [org.jgrapht.alg.spanning KruskalMinimumSpanningTree PrimMinimumSpanningTree]
           [org.jgrapht.alg.clique ChordalGraphMaxCliqueFinder BronKerboschCliqueFinder]))

Random Graphs

I am going to need two functions that will generate random graphs for today’s computations. The first one is for creating a random directed graph,

(defn random-graph [n e l]
  (let [G (SimpleGraph. DefaultEdge)]
    (doseq [i (range n)]
      (.addVertex G i))
    (doseq [i (.vertexSet G)]
      (doseq [u (range e)]
        (.addEdge G i (mod (+ 1 i (rand-int l)) n))))
    G))
#'jg/random-graph

and the second is for random directed graphs:

(defn random-directed-graph [n e l]
  (let [G (SimpleDirectedGraph. DefaultEdge)]
    (doseq [i (range n)]
      (.addVertex G i))
    (doseq [i (.vertexSet G)]
      (doseq [u (range e)]
        (.addEdge G i (mod (+ 1 i (rand-int l)) n))))
    G))
#'jg/random-directed-graph

I am also going to need weighted versions of these random graphs:

(defn random-weighted-graph [n e l]
  (let [G (SimpleWeightedGraph. DefaultWeightedEdge)]
    (doseq [i (range n)]
      (.addVertex G i))
    (doseq [i (.vertexSet G)]
      (doseq [u (range e)]
        (.addEdge G i (mod (+ 1 i (rand-int l)) n))))
    (doseq [e (.edgeSet G)]
      (if (> G KruskalMinimumSpanningTree. .getSpanningTree))
Spanning-Tree [weight=39.0, edges=[(0 : 8), (2 : 7), (27 : 36), (6 : 13), (10 : 19), (14 : 23), (29 : 38), (28 : 33), (31 : 39), (11 : 20), (0 : 9), (26 : 31), (0 : 7), (0 : 3), (10 : 18), (0 : 5), (7 : 15), (8 : 14), (17 : 25), (1 : 10), (19 : 28), (1 : 9), (12 : 21), (1 : 4), (15 : 22), (26 : 34), (23 : 30), (22 : 29), (4 : 12), (6 : 11), (7 : 16), (23 : 32), (19 : 27), (27 : 35), (1 : 6), (19 : 26), (17 : 24), (35 : 37), (9 : 17)]]

You may also use Prim’s algorithm:

(let [n 40
      d 6
      G (random-graph n d 9)]
  (->> G PrimMinimumSpanningTree. .getSpanningTree))
Spanning-Tree [weight=39.0, edges=[(7 : 13), (9 : 10), (37 : 0), (0 : 5), (0 : 4), (13 : 15), (0 : 7), (13 : 14), (13 : 21), (7 : 12), (2 : 3), (1 : 9), (3 : 9), (3 : 11), (23 : 29), (32 : 1), (7 : 16), (23 : 28), (21 : 27), (13 : 17), (39 : 0), (22 : 29), (21 : 23), (34 : 0), (21 : 26), (24 : 25), (38 : 3), (0 : 3), (23 : 30), (35 : 3), (19 : 23), (31 : 39), (36 : 0), (21 : 24), (12 : 18), (7 : 8), (20 : 21), (33 : 39), (3 : 6)]]

Shortest Path

Next, let us move to Dijkstra’s shortest path algorithm. I did not actually did this from scratch, but I used a fancy matrix method here and here that used tropic rings.

(let [n 40
      d 5
      G (random-graph n d 10)
      alg (DijkstraShortestPath. G)
      a (->> (.vertexSet G) (random-sample 0.2) first)
      b (->> (.vertexSet G) (random-sample 0.2) last)]
  (.getPath alg a b))
[(8 : 12), (38 : 8)]

While at it, let us apply Johnson’s Shortest Path Algorithm:

(let [n 40
      d 5
      G (random-graph n d 10)
      alg (JohnsonShortestPaths. G)
      a (->> (.vertexSet G) (random-sample 0.2) first)
      b (->> (.vertexSet G) (random-sample 0.2) last)]
  (.getPath alg a b))
[(37 : 1)]

Maximal Cliques

I implemented Bron-Kerbosch both in Common Lisp and Clojure:

(let [n 40
      d 6
      G (random-graph n d 9)
      cliques (BronKerboschCliqueFinder. G)]
  (->> cliques .maximumIterator iterator-seq (into [])))
[#{7 8 10 13 15}]

Maximal Flow

I did an implementation of Ford-Fulkerson Maximum Flow (which is also known as Edmond-Karp) both in Common Lisp and Clojure.

(let [n 40
      d 5
      G (random-weighted-graph n d 10)
      flow (EdmondsKarpMFImpl. G)
      a (->> (.vertexSet G) (random-sample 0.2) first)
      b (->> (.vertexSet G) (random-sample 0.2) last)]
  (.getMaximumFlow flow a b))
Flow Value: 1.1119844227952433
Flow map:
{(30 : 32)=0.0, (16 : 25)=0.0, (13 : 15)=0.0, (26 : 31)=0.2074921060959558, (34 : 39)=0.0, (4 : 11)=0.0, (37 : 2)=0.0, (21 : 26)=0.257751382221186, (0 : 1)=0.6539934273958473, (36 : 38)=0.0, (28 : 31)=0.0, (9 : 19)=0.0, (14 : 18)=0.0, (9 : 10)=0.0, (4 : 7)=0.0, (32 : 2)=0.0, (3 : 9)=0.0, (26 : 35)=0.09606035114276479, (11 : 16)=0.0, (13 : 14)=0.0, (10 : 18)=0.0, (6 : 16)=0.0, (23 : 24)=0.0, (24 : 28)=0.0, (38 : 6)=0.0, (8 : 14)=0.0, (16 : 26)=0.0, (27 : 31)=0.17328910441742917, (11 : 20)=0.0, (7 : 10)=0.0, (13 : 20)=0.0, (20 : 21)=0.0, (34 : 4)=0.0, (14 : 15)=0.0, (29 : 30)=0.0, (10 : 13)=0.0, (21 : 23)=0.0, (38 : 1)=0.0, (18 : 22)=0.0, (15 : 24)=0.0, (19 : 22)=0.0, (3 : 12)=0.0, (21 : 27)=0.257751382221186, (23 : 32)=0.0, (39 : 5)=0.0, (37 : 7)=0.0, (28 : 36)=0.2648009224619392, (38 : 0)=0.0, (10 : 19)=0.0, (18 : 21)=0.0, (36 : 1)=0.27321221688246233, (17 : 26)=0.0, (22 : 24)=0.0, (19 : 20)=0.0, (22 : 30)=0.0, (25 : 31)=0.0, (12 : 18)=0.0, (35 : 5)=0.0, (38 : 4)=0.0, (12 : 16)=0.0, (15 : 17)=0.0, (7 : 15)=0.0, (38 : 5)=0.0, (32 : 36)=0.08446227780375681, (30 : 36)=0.0, (35 : 36)=0.09606035114276479, (39 : 3)=0.0, (24 : 25)=0.0, (20 : 28)=0.2648009224619392, (1 : 8)=0.0, (19 : 27)=0.0, (39 : 0)=0.0, (11 : 18)=0.0, (35 : 3)=0.0, (2 : 5)=0.0, (25 : 35)=0.0, (27 : 35)=0.0, (17 : 25)=0.0, (0 : 7)=0.0, (18 : 27)=0.0, (6 : 7)=0.0, (15 : 22)=0.0, (34 : 38)=0.0, (21 : 28)=0.0, (3 : 4)=0.0, (6 : 9)=0.0, (36 : 0)=0.4579909953993959, (32 : 1)=0.0, (18 : 19)=0.0, (24 : 33)=0.0, (4 : 9)=0.0, (25 : 32)=0.0, (13 : 17)=0.0, (5 : 12)=0.0, (32 : 0)=0.0, (23 : 25)=0.0, (15 : 25)=0.0, (28 : 34)=0.0, (31 : 1)=0.380781210513385, (21 : 24)=0.0, (1 : 10)=0.0, (27 : 32)=0.08446227780375681, (31 : 35)=0.0, (8 : 11)=0.0, (25 : 34)=0.0, (5 : 11)=0.0, (31 : 38)=0.0, (33 : 38)=0.0, (37 : 3)=0.0, (8 : 15)=0.0, (2 : 10)=0.0, (13 : 22)=0.0, (8 : 13)=0.0, (7 : 12)=0.0, (15 : 23)=0.0, (26 : 28)=0.0, (29 : 36)=0.0, (14 : 21)=0.0, (19 : 23)=0.0, (28 : 30)=0.0, (16 : 19)=0.0, (33 : 3)=0.0, (34 : 1)=0.0, (20 : 24)=0.0, (26 : 36)=0.28587966087339745, (35 : 39)=0.0, (2 : 12)=0.0, (27 : 37)=0.0, (14 : 23)=0.0, (9 : 11)=0.0, (30 : 35)=0.0, (1 : 6)=0.0, (37 : 0)=0.0, (16 : 20)=0.0, (3 : 13)=0.0, (1 : 5)=0.0, (39 : 9)=0.0, (31 : 32)=0.0, (17 : 24)=0.0, (33 : 37)=0.0, (22 : 32)=0.0, (24 : 34)=0.0, (10 : 17)=0.0, (5 : 13)=0.0, (29 : 35)=0.0, (30 : 31)=0.0, (23 : 30)=0.0, (20 : 26)=0.2648009224619392, (10 : 14)=0.0, (4 : 14)=0.0, (11 : 21)=0.0, (33 : 34)=0.0, (36 : 37)=0.0, (12 : 22)=0.0, (7 : 13)=0.0, (28 : 38)=0.0, (5 : 10)=0.0}

Minumum Cut

I did an implementation of Stoer-Wagner in Clojure. Here is the same algorithm from JGraphT:

(let [n 40
      d 15
      G (random-weighted-graph n d 30)
      cut (StoerWagnerMinimumCut. G)]
  (.minCut cut))
[30]