Graph algorithms library offering directed, undirected, weighted, and unweighted graph support. Features a type-safe API, implements Dijkstra's and Ford-Fulkerson algorithms, and avoids JVM auto-boxing.
Directed, undirected, weighted and unweighted graph algorithms for Kotlin Multiplatform.
val graph = buildUndirectedNetwork {
val (v1, v2, v3) = addVertices()
addEdge(v1 edgeTo v3, 4)
addEdge(v1 edgeTo v2, 1)
addEdge(v2 edgeTo v3, 2)
}
val path = graph.shortestPathDijkstra(graph[0], graph[3])
println(path) // [v1, v2, v3]
repositories {
mavenCentral()
}
dependencies {
implementation "io.github.alexandrepiveteau:kotlin-graphs:0.6.0"
}
repositories {
maven {
url "https://s01.oss.sonatype.org/content/repositories/snapshots/"
}
}
dependencies {
implementation "io.github.alexandrepiveteau:kotlin-graphs:0.7.0-SNAPSHOT"
}
[!WARNING] This library is still in heavy development, and you should expect the following:
- The API is not stable, and may change at any time.
- The algorithms are not well tested, and may contain correctness bugs.
- The algorithms are not optimized, and may have performance issues.
A Graph is a collection of Vertex, connected by Edges (for undirected graphs) or Arcs (for directed graphs).
Each arc or edge may have an Int weight, in which case the graph is a Network.
val undirectedGraph = buildUndirectedGraph {
val (a, b, c) = addVertices() // Insert multiple vertices at once ...
val d = addVertex() // ... or just one at a time.
val e1 = a edgeTo b // Create an edge between two vertices ...
addEdge(e1) // ... and insert it in the graph. Networks support weighted edges and arcs.
}
val directedGraph = buildDirectedGraph { /* ... */}
val undirectedNetwork = buildUndirectedNetwork { /* ... */}
directedNetwork = buildDirectedNetwork { }
You can then iterate over the vertices of the network.
directedGraph.forEachVertex { v -> println(v) }
Additionally, the edges or arcs of the graph can be iterated over.
undirectedGraph.forEachEdge { (u, v) -> println("$u <-> $v") }
Networks also provide the weight of their edges or arcs.
directedNetwork.forEachArc { (from, to), weight -> println("$from -> $to : $weight") }
:unicorn: Contributions are welcomed and appreciated! In particular, the following contributions would be very useful:
If you're interested in contributing, please take a look at the list of open issues!
graph LR
a ---|1| b
b ---|1| c
c ---|1| d
d ---|1| e
e ---|5| a
val graph = buildUndirectedNetwork {
val (a, b, c, d, e) = addVertices()
addEdge(a edgeTo b, 1)
addEdge(b edgeTo c, 1)
addEdge(c edgeTo d, 1)
addEdge(d edgeTo e, 1)
addEdge(e edgeTo a, 5)
}
val expected = buildDirectedNetwork {
val (a, b, c, d, e) = addVertices()
addArc(a arcTo b, 1)
addArc(b arcTo c, 1)
addArc(c arcTo d, 1)
addArc(d arcTo e, 1)
}
val spfa = graph.shortestPathFasterAlgorithm(graph[0])
// Checks that the graphs have the same structure and the same weights.
assertEqualsGraph(expected, spfa)
graph LR
a -->|1| b
a -->|10| c
b -->|10| d
c -->|1| d
val capacities = buildDirectedNetwork {
val (a, b, c, d) = addVertices()
addArc(a arcTo b, 1)
addArc(a arcTo c, 10)
addArc(b arcTo d, 10)
addArc(c arcTo d, 1)
}
val expected = buildDirectedNetwork {
val (a, b, c, d) = addVertices()
addArc(a arcTo b, 1)
addArc(a arcTo c, 1)
addArc(b arcTo d, 1)
addArc(c arcTo d, 1)
}
val a = capacities[0]
val d = capacities[3]
val flow = capacities.maxFlowEdmondsKarp(a, d)
// Checks that the graphs have the same structure and the same weights.
assertEqualsGraph(expected, flow)
Surfaced from shared tags and platforms — no rankings paid for.