A novel Graph-Theory and Maze Solution library made for kotlin JVM.
Please compile against com.resnik.math:1.0.0 and com.resnik.intel:1.0.0 as well as this project.
This is a slightly different process to that of com.resnik.intel.
~/.m2/settings.xml:
<settings xmlns="http://maven.apache.org/SETTINGS/1.0.0"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/SETTINGS/1.0.0
http://maven.apache.org/xsd/settings-1.0.0.xsd">
...
<activeProfiles>
<activeProfile>github</activeProfile>
</activeProfiles>
...
<servers>
<server>
<id>github</id>
<username>GITHUB_USERNAME</username>
<password>GITHUB_PAT</password>
</server>
</servers>
</settings>
pom.xml:
<repository>
<id>github</id>
<url>https://maven.pkg.github.com/mtresnik/math</url>
<snapshots>
<enabled>true</enabled>
</snapshots>
</repository>
<repository>
<id>github</id>
<url>https://maven.pkg.github.com/mtresnik/intel</url>
<snapshots>
<enabled>true</enabled>
</snapshots>
</repository>
<repository>
<id>github</id>
<url>https://maven.pkg.github.com/mtresnik/graph</url>
<snapshots>
<enabled>true</enabled>
</snapshots>
</repository>
...
<dependency>
<groupId>com.resnik</groupId>
<artifactId>math</artifactId>
<version>1.0.0</version>
</dependency>
<dependency>
<groupId>com.resnik</groupId>
<artifactId>intel</artifactId>
<version>1.0.0</version>
</dependency>
<dependency>
<groupId>com.resnik</groupId>
<artifactId>graph</artifactId>
<version>1.0.0</version>
</dependency>
~/.gradle/gradle.properties:
gpr.user=GITHUB_USERNAME
gpr.token=GITHUB_PAT
build.gradle:
repositories {
...
maven {
url= uri("https://maven.pkg.github.com/mtresnik/math")
credentials {
// Runner stored in env, else stored in ~/.gradle/gradle.properties
username = System.getenv("USERNAME") ?: findProperty("gpr.user") ?: "<GITHUB_USERNAME>"
password = System.getenv("TOKEN") ?: findProperty("gpr.token")
}
}
...
maven {
url= uri("https://maven.pkg.github.com/mtresnik/intel")
credentials {
// Runner stored in env, else stored in ~/.gradle/gradle.properties
username = System.getenv("USERNAME") ?: findProperty("gpr.user") ?: "<GITHUB_USERNAME>"
password = System.getenv("TOKEN") ?: findProperty("gpr.token")
}
}
maven {
url= uri("https://maven.pkg.github.com/mtresnik/graph")
credentials {
// Runner stored in env, else stored in ~/.gradle/gradle.properties
username = System.getenv("USERNAME") ?: findProperty("gpr.user") ?: "<GITHUB_USERNAME>"
password = System.getenv("TOKEN") ?: findProperty("gpr.token")
}
}
}
dependencies {
...
implementation group: 'com.resnik', name: 'math', version: '1.0.0'
implementation group: 'com.resnik', name: 'intel', version: '1.0.0'
implementation group: 'com.resnik', name: 'graph', version: '1.0.0'
...
}
Prim's Algorithm (40x40) | Kruskal's Algorithm (40x40) |
---|---|
The obvious benefit to MST's is that every node can be reached from any other node, meaning all produced mazes are consistent (able to be solved).
"Recursive" Subdivision (40x40) | Aldous-Broder Algorithm |
---|---|
Recursive is in quotes here because the actual process of generating the Maze uses Depth First Search in a single method rather than programatically calling itself.
The Aldous-Broder Algorithm is slightly modified such that neighboring frontiers are connected. This produces a more uniform spanning tree.
WIP : Recursive DFS for Maze Generation
Initial Maze | Graph Representation |
---|---|
val maze : Maze = // Somehow generated maze...
val graph = MazeToGraphProvider(maze).build()
The resulting graph represents the initial maze, where a MazeCell
is represented by a Vertex
and a MazeBorder
determines the Edge
's.
Maze Solution | Graph Solution |
---|---|
All GraphAlgorithms
can be used on Graphs
and all Mazes
can be converted into Graphs
.
- Breadth-First Search
- Depth-First Search
- Dijkstra
- A* Search
Kruskal's Algorithm | Prim's Algorithm |
---|---|
Generated using
PartiallyConnectedGraph
with V=20 and (E/V)<=10
In general, the MST
algorithms accept a base Graph
and return a cloned Graph
representing the Tree. (Formally this is written as G \ T)
- Brute Force Search - O(n!) uses recursion
- Permutation Search - O(n!) linear search
- Random Search - O(N * (|V| + |E|))
- Greedy Search (sub optimal) - O(|V| + |E|)
- Greedy Twice-Around (uses Prim's MST) - O(|V|^2 + MST)
- Two-Opt (reduces edge cross over)
Vertices, Edges, Paths, and Graphs are both Clonable
and Serializable
.
Saving an Identifyable
Item to an ItemizedLongStorable
will set an auto-incementing ID (long) to the Item and store it within its internal collection. In general, there is VertexStorage
, EdgeStorage
, PathStorage
, and GraphStorage
.
/*
* Where xyzStorage could be:
* VertexStorage,
* EdgeStorage,
* PathStorage, or GraphStorage
* */
val outputStream = ByteArrayOutputStream()
xyzStorage.writeTo(outputStream)
// or to file...
val parent = File("PATH/TO/GRAPH/STORAGE")
xyzStorage.saveFromParent(parent)
val vertexStorage = graph.storage.vertexStorage
// or
val vertexStorage2 = VertexStorage()
vertexStorage2.save(v1)
vertexStorage2.save(v2)
// ...
vertexStorage2.save(vn)
vertexStorageX.forEach{ vertex -> doSomething(vertex) }
header v size 3
header v bbox 0.1 1.0 11.0 2.0
v 1 0.5 1.0 | 1 5 11
v 2 0.1 2.0
v 3 11.0 2.0 | 12
val edgeStorage = graph.storage.edgeStorage
// or
val vertexStorage = VertexStorage()
val edgeStorage2 = EdgeStorage(vertexStorage)
vertexStorage.save(v1)
vertexStorage.save(v2)
val edge1 = Edge(v1, v2)
edgeStorage2.save(edge1)
edgeStorageX.forEach { edge -> doSomething(edge) }
header e size 3
e 1 1 2 0.0
e 2 2 3 0.0
e 3 3 1 0.0
header g v PATH\TO\VERTICES\file.rgv
header g e PATH\TO\EDGES\file.rge
header g t PATH\TO\PATHS\file.rgt
val graphProvider = BoundedGraphProvider(bbox, width, height)
val graph = graphProvider.build()
// Prune input by 20%
val prunedProvider = RandomPruneGraphProvider(graph, 0.20)
// Uses a cloned graph for pruning
val pruned1 = prunedProvider.build()
val pruned2 = prunedProvider.build()
// ...
val prunedN = prunedProvider.build()
val vertexStorage = graph.storage.vertexStorage
// O(|V|)
val start = vertexStorage.nearestNeighbor(ArrayPoint(0.5, 1.0))
val dest = vertexStorage.nearestNeighbor(ArrayPoint(10.5, -20))
// kNN checks : O(k*|V|)
val closest3 = vertexStorage.kNearestNeighbors(ArrayPoint(3.0, 4.0), 6)