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))

Older Posts

[2024-11-12] Hosoya Index of Balanced Binary Trees

[2024-11-11] Hosoya Index of a Graph

[2024-10-29] The Clique Number of a Simple Graph

[2024-10-28] The Size of Maximally Independent Subsets in a Graph

[2023-11-03] Graph Algorithms in JGraphT with Common Lisp

[2023-10-28] An Implementation of Pandas’ cut and qcut in Lisp

[2023-07-24] A Collatz-like Conjecture for the Projective Line

[2023-03-06] Twin Primes, Cousin Primes, Sexy Primes, and Prime Triplets

[2023-03-02] Set of All Partitions of a Finite Set

[2023-02-14] Non-crossing Partitions and Dyck Words

[2023-02-13] Non-crossing Linear Chords

[2023-02-04] Clojure/Python Interop Examples

[2023-01-14] Graph Algorithms in Clojure with JGraphT

[2022-03-29] 2D-Random Walk

[2022-03-28] Trade Deficit vs Exchange Rate Curve

[2022-03-16] Working with World Bank Data in Python

[2022-03-09] Working with European Central Bank data in python (revisited)

[2022-01-24] A Clique Analysis of Quakers in early modern Britain (1500-1700)

[2021-12-05] Boyer–Moore and Misra-Gries Algorithms in Clojure

[2021-09-12] Tension in Text Plotted

[2021-09-02] Statistical Distributions using Apache Commons Math in Clojure

[2021-08-31] Reduce with Intermediate Results in Common Lisp

[2021-08-21] Multivariate Regression Implemented in Clojure

[2021-05-29] Using Neural Networks to Detect Graph Properties

[2021-04-17] Fast Null-Space Calculation via LU-Decomposition

[2021-02-24] Stoer-Wagner Algorithm in Clojure

[2021-02-19] Calculating Vertex Covers in Clojure

[2021-02-18] Listing All Paths in a Graph

[2021-02-14] Strict Dyck Words and Fibonacci Numbers

[2021-02-14] Kruskal’s Algorithm in Common Lisp

[2021-02-13] Kruskal's Algorithm Implemented in Clojure

[2021-02-10] An integer dynamical system of integers

[2021-02-08] Binary Symmetrization

[2021-01-28] Prüfer Encoding and Decoding of a Tree in Clojure

[2021-01-27] Counting Cycle-Free Paths in a Graph

[2021-01-27] Counting Connected Labeled Graphs

[2020-12-18] Counting Graphs with a Prescribed Degree Sequence

[2020-12-13] Havel–Hakimi Algorithm in Clojure

[2020-12-12] Havel–Hakimi Algorithm in Common-Lisp

[2020-10-23] The Quadratic Casimir Element

[2020-07-04] Collatz Sequence in Binary

[2020-07-02] A Lazy Sequence of Primes in Clojure

[2020-06-10] Yet Another Fizz-Buzz in Common Lisp

[2020-05-12] ECB Data with Clojure and Vega-Lite

[2020-05-06] Processing ECB Data with Common Lisp

[2020-04-17] Next Permutation in the Lexicographical Ordering

[2020-04-13] Turkish Hyphenation in Common Lisp

[2020-04-01] Using JavaPlex with Clojure

[2019-11-05] Constricted Arithmetic Progressions

[2019-11-03] The Number of Arithmetic Progressions of Integers

[2019-05-06] Bron-Kerbosch Algorithm in Clojure

[2019-05-01] An Implementation of Ford-Fulkerson Algorithm in Clojure

[2019-04-22] Document Summarization via Nonnegative Matrix Factorization

[2019-04-20] Latent Semantic Analysis in Clojure

[2019-04-13] K-Nearest Neighbors Algorithm in Clojure

[2019-04-06] K-Means Implemented in Clojure

[2019-03-19] Prüfer Encoding/Decoding of a Tree in Common Lisp

[2019-03-05] Gale-Shaply Algorithm in Common Lisp

[2019-03-02] Calculating The Correct Rank of a Matrix

[2018-12-04] Feed-forward and back-propagation in neural networks as left- and right-fold

[2018-10-31] Nonnegative Matrix Decomposition in Clojure

[2018-10-30] Non-negative Matrix Decomposition in Scala

[2018-08-30] Working with European Central Bank Data in Scala

[2018-07-30] Perverse Sequences

[2018-05-28] Online Perceptron in Common Lisp

[2018-05-26] Online Perceptron

[2018-05-18] Online Regression

[2018-05-06] Knut’s Algorithm-S in Common Lisp

[2018-02-28] Irreducible Dyck Words

[2018-02-19] Optimization with GNU Scientific Library for Lisp

[2018-02-10] Van Eck’s Sequence

[2018-02-09] Hiring networks in mathematics

[2018-02-08] Linus Sequence

[2018-02-05] Egyptian Fractions

[2018-02-01] Listing all Young Tableaux

[2018-01-23] Collatz sequence (yet again)

[2018-01-15] Hofstadter's Q sequence

[2018-01-09] Farey Sequence

[2018-01-09] Catalan's Triangle

[2018-01-06] The Shoelace Formula for the Area of a Polygon

[2017-10-01] Working with European Central Bank Data in Python

[2017-09-27] Expected Value of the Diameter of a Tree

[2017-09-26] Using Quandl with kixi.stats on Clojure

[2017-09-22] Using Quandl with Common Lisp

[2017-08-05] Solving Linear Equations in Natural Numbers

[2017-07-31] Transitive Closure of a Directed Graph or a Relation

[2017-07-20] Steenrod-Milnor and Tournament Sequences

[2017-07-15] A lower bound on the radius of a graph

[2017-07-08] All partitions of an integer

[2017-07-06] Some Hasse Diagrams

[2017-07-04] Shuffles

[2017-07-03] Kaprekar Sequence

[2017-07-01] Lattice of Dyck Words

[2017-06-28] The poset of connected subgraphs of a connected graph

[2017-06-21] Calculating the Diameter and the Radius of a Graph Using Tropic Linear Algebra

[2017-06-19] Generating random regular graphs

[2017-06-14] Estimating the maximum element of a large list

[2017-06-09] A Stochastic Gradient Descent Implementation in Clojure

[2017-06-06] A topology problem

[2017-04-22] Listing duplicate files

[2017-03-14] My First Idris Proof

[2016-12-02] Distinguishing hash functions (part II)

[2016-12-01] Distinguishing hash functions

[2016-10-20] Hofstadter-Conway $10,000 sequence

[2016-08-18] A Solution for Problem 171 of 4Clojure

[2016-08-16] Puzzles and Group Theory

[2016-08-13] Using Weka within Lisp

[2016-07-12] Funniest and Unfunniest Jokes in the Jester Dataset

[2016-07-05] Generating Uniformly Random Connected Graphs

[2016-06-16] The Robinson-Schensted Algorithm

[2016-06-01] Conjugate Partitions

[2016-04-27] Using Word2Vec from Clojure

[2016-04-24] Using Word2Vec from Common Lisp

[2016-04-18] A Migration Analysis

[2016-04-11] Basic Data Analysis with CL without Frameworks

[2016-03-25] Parallel map-reduce in Common Lisp

[2016-02-22] Text Summarization and Topic Analysis

[2016-01-27] Set Covering Problem

[2016-01-25] Kolmogorov-Smirnov Test

[2016-01-20] Eigen-values of the Laplacian and Connected Components of a Graph

[2015-12-12] Dual Graphs

[2015-10-26] Longest Increasing Subsequence Revisited

[2015-10-16] Document Summarization via Markov Chains

[2015-10-07] Computational Literary Analysis

[2015-09-30] Library of Babel in Common Lisp

[2015-09-28] Merging Association Lists in Common Lisp

[2015-07-22] Cheapest Paths via Tropic Matrices

[2015-07-21] Hidden Markov Models via Tropic Matrices

[2015-07-08] A non-technical post

[2015-06-28] An implementation of the Viterbi algorithm in Common Lisp

[2015-05-28] Greatest Common Divisor of Two Rational Numbers

[2015-05-21] Partitions of Equal Measure Whatever the Measure May Be

[2015-05-14] Finding Cliques in a Graph

[2015-05-12] Set Cover Problem

[2015-05-03] Threading Macros in Common Lisp

[2015-05-03] Happy Numbers

[2015-05-01] Collatz Primes

[2015-04-23] Splitting Streams

[2015-04-06] Hamming Distance and Double Hashing

[2015-04-05] Hamming Distance and Hashing Functions

[2015-04-05] Hamming Derivative of Hashing Functions

[2015-04-02] A Topology Problem

[2015-03-21] Curve Fitting is a Gram-Schmidt Reduction

[2015-03-08] Maximum number of characters using keystrokes A, Ctrl+A, Ctrl+C and Ctrl+V

[2015-03-06] Eccentricity, Radius and Diameter in a Graph, Revisited

[2015-03-01] Graphs and Entropy

[2015-02-22] Math PhD Hiring Network (Part 3)

[2015-02-19] Math PhD Hiring Network (Part 2)

[2015-02-18] Math PhD Hiring Network (Part 1)

[2015-02-17] Faculty Networks and Inequality in Hiring Practices in Universities

[2015-02-10] Functional Streams in Lisp Explained

[2015-02-05] Collatz-type Conjectures (Continued)

[2015-02-04] Collatz-type Conjectures (Continued)

[2015-01-31] Collatz-type Conjectures (Continued)

[2015-01-30] Collatz-type Conjectures

[2015-01-28] Experiments with Infinite Recursive Sequences (continued)

[2015-01-17] Experiments with Infinite Recursive Sequences

[2015-01-10] Goldbach Pairs

[2015-01-02] Collatz Lengths (Continued)

[2015-01-01] Functional Streams

[2014-12-27] Polarization in the US Congress

[2014-12-18] Partition a sequence

[2014-11-28] Uniformly Random Permutations

[2014-11-22] An Implementation of Ford-Fulkerson Algorithm in Common Lisp

[2014-11-17] Tropic Calculation of Cheapest Paths

[2014-11-05] Longest common subsequence of two sequences

[2014-10-30] Counting Spanning Trees of a Graph

[2014-10-26] Longest Increasing Subsequence

[2014-10-24] The Number of Inversions in a Sequence

[2014-10-22] Hashes and Entropy

[2014-10-09] Estimating Cardinality with Constant Memory Complexity

[2014-09-30] Landau's Function

[2014-09-29] A Problem on Substitution Ciphers and Group Theory

[2014-09-28] A Morse Code Translator

[2014-09-23] A Memoization Macro for Common Lisp

[2014-09-21] Reducers are Monoid Morphisms

[2014-09-18] Number of isomorphism classes of binary trees

[2014-09-07] CONS is your friend

[2014-08-22] A Zipf's Law Simulation

[2014-08-07] Generating Uniformly Random Trees

[2014-07-09] A Solution for Project Euler #463

[2014-06-12] Entropy of truncated MD5 hashing

[2014-06-08] Hexadecimal digits of π

[2014-02-11] Information content of n-grams

[2014-02-08] Turkish Sentiment Analysis Using Thesaurus Distance

[2014-02-01] Sentiment analysis using word distances

[2014-01-27] Phase transitions in entropy

[2013-12-13] Optimal length of n-grams

[2013-12-10] Counting strings that contain intervals of same letter repetitions

[2013-12-02] Patterns Separating Large Texts

[2013-11-23] Collatz Sequences (Continued)

[2013-11-11] Entropy and approximately one-to-one maps

[2013-10-23] Tree Isomorphism

[2013-10-15] Self Organizing Maps

[2013-09-15] Euler Project #401

[2013-09-15] An additively recursive definition of the Moebius function

[2013-09-11] An Unsuccessful Attempt for Solving Euler Project #401

[2013-09-04] Uniform Sampling from Parametrized Submanifolds in Scala

[2013-09-04] Uniform Sampling from Parametrized Submanifolds

[2013-08-30] Randomly Generated Points Obeying a Distribution

[2013-08-25] Simulated Annealing in Lisp

[2013-08-21] Eigenvalues and Eigenvectors in GSLL

[2013-08-16] Reservoir Sampling

[2013-08-11] Gibbs sampling in lisp compared with C

[2013-08-10] Logistic Regression in lisp

[2013-08-10] Linear Discriminant Analysis in R

[2013-07-17] A Gradient Descent Implementation in Lisp

[2013-07-01] k-Nearest Neighbor Classification Algorithm Implemented in Lisp

[2013-05-19] Newton-Raphson Method

[2013-05-07] Levenshtein Distance

[2013-04-15] Cut points in a graph

[2013-04-01] Experiments on Collatz Lengths (Continued)

[2013-02-18] The sound of the torsion parts of homotopy groups of spheres

[2013-02-12] Monadic Units

[2013-02-07] Distribution of Collatz Lengths (continued)

[2013-02-03] Distribution of Collatz Lengths

[2013-01-31] Quotients of polynomial algebras

[2013-01-12] Path ideals

[2013-01-10] McCarthy91 Terminates

[2013-01-09] Finding all paths in a directed graph

[2013-01-04] A Simple Monte-Carlo Integration Implementation in Lisp

[2012-12-30] A simple problem in Kolmogorov-Chaitin complexity

[2012-12-29] From walks to paths

[2012-12-16] Higher order functions, functors and monads

[2012-12-13] Eccentricity, Radius and Diameter in an Undirected Graph

[2012-11-29] Untitled

[2012-11-25] Strictly Increasing Labels of Directed Graphs

[2012-11-19] Strictly Increasing Labellings of Directed Graphs

[2012-11-17] Nilpotent elements in an artinian algebra

[2012-11-04] Local rings, idempotents and non-invertible elements

[2012-10-18] An implementation of the fixed-radius near neighbor clustering algorithm in lisp

[2012-10-15] Reducing directed graphs

[2012-10-10] An implementation of the k-means clustering algorithm in lisp

[2012-10-08] A comparison of different map functions in lisp

[2012-10-03] Source code entropy

[2012-09-28] Collisions in random walks

[2012-09-26] Transitive closure of a directed graph

[2012-09-26] Solving linear equations in ℕ

[2012-09-26] Listing partitions

[2012-09-26] Inverting formal power series

[2012-09-26] Hasse subgraph of a directed graph