graphmatekt/graphMateKT.graphClasses/Grid

Grid

class Grid(val width: Int, val height: Int, initWithDatalessTiles: Boolean = true, debugTimeUse: Boolean = false, isSparse: Boolean = false) : BaseGraph<Tile>

A general graph class that represents a 2D grid structure of nodes.

It uses the data class: Tile(val x: Int, val y: Int, val data: Any? = null) to represent nodes of any datatype, where each node also has x and y coordinates.

The grid can be created in two ways:

By specifying a width and height, optionally initializing it with tiles that has data=null.
By passing a list of strings, where each string represents a row, and all strings must have the same length.

The Grid class supports the same algorithms as the Graph class. Additionally, it provides methods for connecting nodes in the grid without explicitly adding edges:

.connectGridDefault() connects each node to its neighbors in the up, down, left, and right directions, if they exist.
.connectWithRule(::yourCustomFunction) (or .connectWithRule { yourLambda }) allows custom connections, where the function takes a Tile and returns a List<Tile> to connect to.

Example usage:

val grid = Grid(100,100)
grid.connectGridDefault()
grid.bfs(Tile(50,50))
grid.visualizeGrid()

String constructor and custom connections example usage:

val stringList = listOf(
"0#4",
"123",
"234"
)
val grid = Grid(stringList)
grid.deleteNodesWithData('#')
grid.connectWithRule { t ->
    grid.getStraightNeighbours(t).filter { it.x > t.x || it.y > t.y } // connect right and down
}
grid.bfs(Tile(0, 0))
grid.visualizeGrid()

Parameters

width

The width of the grid (number of columns).

height

The height of the grid (number of rows).

initWithDatalessTiles

If true, initializes the grid with empty tiles.

debugTimeUse

If true, prints the time use of algorithms to standard error. Defaults to false.

isSparse

If true, search results are stored in maps instead of arrays. More performant when searches only reach a small part of a large grid. Defaults to false.

Constructors

Grid

constructor(width: Int, height: Int, initWithDatalessTiles: Boolean = true, debugTimeUse: Boolean = false, isSparse: Boolean = false)

constructor(stringGrid: List<String>, debugTimeUse: Boolean = false, isSparse: Boolean = false)

Construct the grid from a list of strings, where each string represents a row in the grid, and each character, a node.

Properties

height

val height: Int

width

val width: Int

Functions

addEdge

fun addEdge(node1: Tile, node2: Tile, weight: Int)

Overloaded function that calls addEdge with weight converted to a double.

open override fun addEdge(node1: Tile, node2: Tile, weight: Double = 1.0)

Adds a directed edge from node1 to node2. Tiles are matched by their (x, y) coordinates, so data is ignored.

addNode

open override fun addNode(node: Tile)

Adds (or replaces) the tile at the node's (x, y) coordinates. Can also be used to restore a deleted tile.

allPairsShortestPaths

fun allPairsShortestPaths()

Executes the Floyd-Warshall algorithm on the graph to compute the shortest paths between all pairs of nodes.

bfs

fun bfs(startNode: Tile, target: Tile? = null, reset: Boolean = true, maxDistance: Double = Double.POSITIVE_INFINITY)

Overload of fun bfs(startNodes: List, target: T?, reset: Boolean, maxDistance: Double) that accepts a single starting node instead of a list of starting nodes

fun bfs(startNodes: List<Tile>, target: Tile? = null, reset: Boolean = true, maxDistance: Double = Double.POSITIVE_INFINITY)

Performs a Breadth-First Search, which finds the shortest path from the starting node to all other nodes, assuming the graph is unweighted (all edges have a weight of 1.0) It stores results that can be retrieved with the following functions:

clearEdges

fun clearEdges()

Removes all edges from the graph, including a rule defined by connectWithRule. Nodes and search results are kept.

connect

fun connect(node1: Tile, node2: Tile)

Connects two nodes in the graph, by calling addEdge(node1,node2) and addEdge(node2, node1)

fun connect(node1: Tile, node2: Tile, weight: Double)

Connects two nodes in the graph, by calling addEdge(node1,node2, weight) and addEdge(node2, node1, weight)

fun connect(node1: Tile, node2: Tile, weight: Int)

Overloaded function that calls connect with weight converted to a double.

connectGridDefault

fun connectGridDefault()

Connects all nodes in the grid with their straight neighbours, i.e. top, down, left, right neighbours, if they exist within the grid boundaries and have not been deleted.

connectWithRule

open fun connectWithRule(getNeighbours: (node: Tile) -> List<Tile>)

Defines a rule for how each node is connected to its neighbors.

currentVisitedNodes

fun currentVisitedNodes(): List<Tile>

deleteNodeAtXY

fun deleteNodeAtXY(x: Int, y: Int)

Deletes the node at the specified (x, y) coordinates in the grid.

deleteNodesWithData

fun deleteNodesWithData(data: Any?)

Deletes all nodes in the grid that have the specified data. Deleted nodes are not considered neighbours of nodes.

depth

fun depth(): Int

Retrieves the depth of the graph from the most recent search operation

dfs

fun dfs(startNode: Tile, reset: Boolean = true)

Performs a Depth-First Search, which finds all nodes that's reachable from the starting node. It stores results that can be retrieved with the following functions:

distanceFromUtoV

fun distanceFromUtoV(u: Tile, v: Tile): Double

Retrieves the shortest distance between two nodes in the graph.

distanceTo

fun distanceTo(node: Tile): Double

Retrieves the distance to the specified node from the starting node of the most recent search operation (BFS, DFS, shortestPathsFrom).

edges

fun edges(): List<Triple<Tile, Tile, Double>>

fun edges(node: Tile): List<Pair<Double, Tile>>

Retrieves a list of edges connected to the specified node.

finalPath

fun finalPath(): List<Tile>?

Retrieves the shortest path from the start to target node (if a target was specified) during the most recent search operation (BFS, shortestPathsFrom). After topologicalSort(), it holds the topological ordering.

firstNodeWithData

fun firstNodeWithData(data: Any): Tile

Returns the first tile in the grid (row-wise from left to right) that contains the requested data.

forEachNeighbour

fun forEachNeighbour(node: Tile, action: (Tile) -> Unit)

Executes a given function on all the neighbours of a given node.

foundTarget

fun foundTarget(): Boolean

Checks if the target node was found during the most recent search operation (BFS, shortestPathsFrom).

furthestNode

fun furthestNode(): Tile

Retrieves the node that is the farthest from the starting node in the most recent search operation (BFS, shortestPathsFrom).

getAllNeighbours

fun getAllNeighbours(t: Tile): List<Tile>

Retrieves all neighbors (both straight and diagonal) of the given tile.

getDiagonalNeighbours

fun getDiagonalNeighbours(t: Tile): List<Tile>

Retrieves the diagonal neighbors of the given tile.

getPath

fun getPath(target: Tile): List<Tile>?

Retrieves the path from the starting node to the specified target node based on the most recent search results.

getStraightNeighbours

fun getStraightNeighbours(t: Tile): List<Tile>

Retrieves the straight (orthogonal) neighbors of the given tile.

maxDistance

fun maxDistance(): Double

Retrieves the maximum distance from the starting node to any other node after the most recent search operation (BFS, shortestPathsFrom).

minimumSpanningTree

fun minimumSpanningTree(): Pair<Double, Graph>

Computes the Minimum Spanning Tree (MST) of the graph using Prim's algorithm.

neighbours

fun neighbours(node: Tile): List<Tile>

Retrieves a list of the neighboring nodes of the specified node.

nodes

open override fun nodes(): List<Tile>

nrOfEdges

fun nrOfEdges(): Int

nrOfPaths

fun nrOfPaths(startNode: Tile, targetNode: Tile, mod: Long = Long.MAX_VALUE): Long

Calculates the number of distinct paths from the starting node to the target node in the graph.

open override fun print()

Print the content of the grid, tile by tile, to the standard error stream

printConnections

fun printConnections()

Prints which nodes each node is connected to, to the standard error stream.

resetSearchResults

fun resetSearchResults()

Clears the search results stored in the graph.

shortestPathsFrom

fun shortestPathsFrom(startNode: Tile, target: Tile? = null)

Performs Dijkstra's algorithm to find the shortest path from the starting node to all other nodes. It stores results that can be retrieved with the following functions:

size

fun size(): Int

stronglyConnectedComponents

open override fun stronglyConnectedComponents(): GridComponents

Identifies groups where each node is reachable from every other node in the group.

topologicalSort

open override fun topologicalSort(): List<Tile>

Builds an order of nodes so that the first nodes has no outgoing edges, then nodes with edges pointing to these and so on, assuming the graph is a Directed Acyclic Graph (DAG). This is done by running a DFS from each node and ordering the nodes by descending depth (post-order).

visitedNodes

fun visitedNodes(): List<Tile>

visualizeGraph

fun <T : Any> BaseGraph<T>.visualizeGraph(isBidirectional: Boolean = false, finalPath: List<T> = finalPath() ?: emptyList(), screenTitle: String = "Graph visualizer (Click space to pause and resume)", animationTicTimeOverride: Double? = null, closeOnEnd: Boolean = false, startPaused: Boolean = false)

Visualizes the graph with Bruno Silva's JavaFXSmartGraph library.

visualizeGrid

fun Grid.visualizeGrid(currentVisitedNodes: List<Tile> = currentVisitedNodes(), finalPath: List<Tile> = finalPath() ?: emptyList(), nodeDistances: List<Double> = currentVisitedNodes.map { tile -> runCatching { distanceTo(tile) }.getOrDefault(Double.MAX_VALUE) }, screenTitle: String = "Grid visualizer (Click space to pause and resume)", animationTicTimeOverride: Double? = null, closeOnEnd: Boolean = false, startPaused: Boolean = false, screenWidthMultiplier: Double = 1.0)

Visualizes the grid and optionally its traversal process using a graphical interface.

xy2Node

fun xy2Node(x: Int, y: Int): Tile

Retrieves the Tile node at the specified (x, y) coordinates.

xy2NodeOrNull

fun xy2NodeOrNull(x: Int, y: Int): Tile?

Retrieves the Tile node at the specified (x, y) coordinates, if it exists.