graphmatekt/graphMateKT.graphClasses/IntGraph

IntGraph

class IntGraph(size: Int, isWeighted: Boolean = true) : BaseGraph<Int>

A graph data structure specialized for integer nodes ranging from 0 to size-1.

The IntGraph class behaves a lot like the Graph class when used with integers like the example above. However, * it's more performant, because it does not need to maintain an internal mapping between the nodes and their indexes in the adjacency list. The obvious drawback being it only supports integer nodes.

Example usage:

val intGraph = IntGraph(3) // Creates a graph with nodes 0, 1 and 2
graph.addEdge(0, 1, 5.0)
graph.addEdge(0, 2, 2.0)
graph.addEdge(2, 1, 1.0)
graph.dijkstra(0, 1)
// NOTE: visualizeGraph() requires the smartgraph.css and smartgraph.properties files to be added to the root of your project.
graph.visualizeGraph() // Find the needed files here: https://github.com/Norskeaksel/GraphMateKT

Parameters

size

The number of nodes in the graph. Nodes are represented as integers from 0 to size-1. This cannot be altered later

isWeighted

Indicates whether the graph uses weighted or unweighted edges.

Constructors

IntGraph

constructor(size: Int, isWeighted: Boolean = true)

Functions

addEdge

fun addEdge(node1: Int, node2: Int, weight: Number?)

Adds an edge between two nodes in the graph, and creates the nodes if they don't exist.

addNode

open override fun addNode(node: Int): Nothing

Adds the given node to the graph

bfs

fun bfs(startNode: Int, target: Int?, reset: Boolean)

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

fun bfs(startNodes: List<Int>, target: Int?, reset: Boolean)

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: Int, node2: Int, weight: Number?)

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

currentVisitedNodes

fun currentVisitedNodes(): List<Int>

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: Int, reset: Boolean)

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: Int, target: Int?)

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: Int, v: Int): Double

Retrieves the shortest distance between two nodes in the graph.

distanceTo

fun distanceTo(node: Int): Double

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

edges

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

Retrieves a list of edges connected to the specified node.

finalPath

fun finalPath(): List<Int>

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(): Int

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

getPath

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

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: Int): List<Int>

Retrieves a list the neighboring nodes of the specified node.

nodes

open override fun nodes(): List<Int>

fun print(isWeighted: Boolean)

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

removeEdge

fun removeEdge(node1: Int, node2: Int)

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

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

topologicalSort

open fun topologicalSort(): List<Int>

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

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.