openrndr-kartifex/org.openrndr.kartifex.utils.graphs/Graphs

Graphs

object Graphs(source)

Functions

bfsVertices

fun <V> bfsVertices(start: V, adjacent: (V) -> Iterable<V>): Iterator<V>

fun <V> bfsVertices(start: Iterable<V>, adjacent: (V) -> Iterable<V>): Iterator<V>

Performs a breadth-first traversal of vertices starting from the given set of initial vertices.

cycles

fun <V, E> cycles(graph: DirectedGraph<V, E>): List<List<V>>

Finds all simple cycles in a directed graph. A cycle is defined as a non-empty sequence of vertices such that the first and last vertices in the sequence are the same, and each edge in the sequence is traversed exactly once.

shortestPath

fun <V, E> shortestPath(graph: DirectedGraph<V, E>, start: Iterable<V>, accept: (V) -> Boolean, cost: (IEdge<V, E>) -> Double): List<V>?

stronglyConnectedComponents

fun <V> stronglyConnectedComponents(graph: DirectedGraph<V, *>, includeSingletons: Boolean): Set<Set<V>>

Computes the strongly connected components of a given directed graph using Tarjan's algorithm. A strongly connected component (SCC) is a maximal subgraph where every vertex is reachable from every other vertex in the same subgraph.

stronglyConnectedSubgraphs

fun <V, E> stronglyConnectedSubgraphs(graph: DirectedGraph<V, E>, includeSingletons: Boolean): List<DirectedGraph<V, E>>

Identifies strongly connected subgraphs within the given directed graph.