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.
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]))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-graphand 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-graphI 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)]]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)]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}]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}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]