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)