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:

connect

fun connect(node1: T, node2: T, weight: Number? = null)

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

currentVisitedNodes

fun currentVisitedNodes(): List<T>

Retrieves a list of all visited nodes on the order they were visited during the last search operation (DFS, BFS, Dijkstra).

depth

fun depth(): Int

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

dfs

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

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

dijkstra

fun dijkstra(startNode: T, target: T? = null)

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

distanceFromUtoV

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

Retrieves the shortest distance between two nodes in the graph.

distanceTo

fun distanceTo(node: T): Double

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

edges

fun edges(t: T): List<Pair<Double, T>>

Retrieves a list of edges connected to the specified node.

finalPath

fun finalPath(): List<T>

Retrieves the shortest path from the start to target node path during the most recent search operation (DFS, BFS, Dijkstra)

floydWarshall

fun floydWarshall()

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

foundTarget

fun foundTarget(): Boolean

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

furthestNode

fun furthestNode(): T

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

getPath

fun getPath(target: T): List<T>

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

maxDistance

fun maxDistance(): Double

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

minimumSpanningTree

fun minimumSpanningTree(): Pair<Double, Graph>

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

neighbours

fun neighbours(t: T): List<T>

Retrieves a list the neighboring nodes of the specified node.

nodes

abstract fun nodes(): List<T>

fun print(isWeighted: Boolean)

Prints the graph's adjacency list to the standard error stream.

removeEdge

fun removeEdge(node1: T, node2: T)

Removes the edge(s) between two nodes in the graph.

resetSearchResults

fun resetSearchResults()

Clears the search results stored in the graph.

size

fun size(): Int

stronglyConnectedComponents

open fun stronglyConnectedComponents(): List<List<T>>

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

topologicalSort

open fun topologicalSort(): List<T>

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<T>

Retrieves a (unordered) list of all visited nodes during any non-reset search operation (DFS, BFS, Dijkstra).

visualizeGraph

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

Visualizes the graph with Bruno Silva's JavaFXSmartGraph library.