Kaliningraph

Kaliningraph is a purely functional graph library with a DSL for constructing graphs and visualizing the behavior of graph algorithms.

Installation

Kaliningraph is hosted on JitPack.

Gradle

repositories {
    maven("https://jitpack.io")
}

dependencies {
    implementation("com.github.breandan:kaliningraph:-SNAPSHOT")
}

Maven

<project>
  <repositories>
    <repository>
      <id>jitpack.io</id>
      <url>https://jitpack.io</url>
    </repository>
  </repositories>
  
  <dependency>
    <groupId>com.github.breandan</groupId>
    <artifactId>kaliningraph</artifactId>
    <version>0.0.1</version>
  </dependency>
</project>

Graphs, Inductively

What are graphs? A graph is a (possibly empty) set of vertices.

What are vertices? A vertex is a unique label with neighbors (possibly containing itself).

What are neighbors? Neighbors are a graph.

Getting Started

Run the demo via ./gradlew HelloKaliningraph to get started.

Usage

To construct a graph, the graph builder DSL provides an small alphabet:

val graph = Graph { a - b - c - d - e; a - c - e }

This is the same as:

val abcde = Graph { a - b - c - d - e }
val ace = Graph { a - c - e }
val graph = abcde + ace

Equality is supported using the Weisfeiler-Lehman test:

val x = Graph { a - b - c - d - e; a - c - e }
val y = Graph { b - c - d - e - f; b - d - f }
assertEquals(x == y) // true

Visualization

Graph visualization is made possible thanks to KraphViz.

val de = Graph { d - e }
val dacbe = Graph { d - a - c - b - e }
val dce = Graph { d - c - e }

val abcd = Graph { a - b - c - d }
val cfde = Graph { c - "a" - f - d - e }

val dg = Graph(dacbe, dce, de) + Graph(abcd, cfde)
dg.show()

Running the above snippet will cause the following figure to be rendered in the browser:

Graph visualization in both DOT and adjacency matrix format is supported.

DOT Graph	Matrix

It is also possible to visualize the state and transition matrices and step through the graph (./gradlew PrefAttach).

Translation

Bidirectional translation to various graph formats, including Graphviz, JGraphT, Tinkerpop and RedisGraph is supported:

val g = Graph { a - b - c - a }
        .toJGraphT().toKaliningraph()
        .toTinkerpop().toKaliningraph()
        .toGraphviz().toKaliningraph()

Automata-Based Regex

A regex to NFA compiler is provided. To run the demo, run ./gradlew RegexDemo. You should see something like this:

References

Graph theory

• Solutio problematis ad geometriam situs pertinentis, Leonhard Euler
• Account of the Icosian Calculus, William (Rowan) Hamilton
• Mathematical Foundations of the GraphBLAS
• Graph Algorithms in the Language of Linear Algebra

Graph learning

• Graph Representation Learning, William Hamilton

Functional graphs

• Functional programming with structured graphs, Bruno Oliveira and William Cook
• Think Like a Vertex, Behave Like a Function! A Functional DSL for Vertex-Centric Big Graph Processing, Kento Emoto et al.
• Inductive Graphs and Functional Graph Algorithms, Martin Erwig
• Fully Persistent Graphs – Which One To Choose?

Automata

• roll-library
• dk.brics.automata
• LearnLib

Software

• GraphBlas
• GraphBLAST
• Bifurcan, high-quality JVM implementations of immutable data structures
• JGraphT - A Java Library for Graph Data Structures and Algorithms
• viz-js