graph library

Graph-theory objects and algorithms.

Classes

BreadthFirstIterable<V>

Iterable over the breadth-first traversal of vertices.

DepthFirstIterable<V>

Iterable over the depth-first traversal of vertices. The vertices are emitted pre-order, that is right when they are first discovered.

DepthFirstPostOrderIterable<V>

Iterable over the post-order depth-first traversal of vertices. The vertices are emitted post-order, that is after all its descendants have been discovered.

DinicMaxFlow<V>

Dinic max flow algorithm in O(V^2*E).

Edge<V, E>

An edge withing a graph connects a source and a target vertex.

ForwardingGraph<V, E>

Graph that forwards to a delegate implementation.

Graph<V, E>

Abstract base class of graphs.

GraphFactory<V, E>

Factory methods to create common graphs types efficiently.

Path<V, E>

A path withing a graph connects a series of vertices through their respective edges and values.

RandomWalkIterable<V>

Iterable producing a random walk over a graph.

StoerWagnerMinCut<V, E>

Stoer–Wagner minimum cut algorithm in O(VE + Vlog(V)).

StorageStrategy<T>

Encapsulates data structures used for the various graph algorithms.

TopologicalIterable<V>

Iterable over the topological sorting of vertices. This traversal requires a predecessor-function, and ignores nodes that are part of cycles.

Extensions

AlgorithmsGraphExtension on Graph<V, E>

AtlasGraphFactoryExtension on GraphFactory<V, E>

BreadthFirstGraphExtension on Graph<V, E>

CollectionGraphFactoryExtension on GraphFactory<V, E>

CompleteGraphFactoryExtension on GraphFactory<V, E>

https://mathworld.wolfram.com/CompleteGraph.html

ConnectedGraphExtension on Graph<V, E>

CopyGraphExtension on Graph<V, E>

DepthFirstGraphExtension on Graph<V, E>

DepthFirstPostOrderGraphExtension on Graph<V, E>

EmptyGraphFactoryExtension on GraphFactory<V, E>

ExportGraphExtension on Graph<V, E>

LogicalGraphExtension on Graph<V, E>

MapGraphExtension on Graph<V, E>

NumericPathExtension on Path<V, num>

PartiteGraphFactoryExtension on GraphFactory<V, E>

https://mathworld.wolfram.com/Completek-PartiteGraph.html

PathGraphFactoryExtension on GraphFactory<V, E>

https://mathworld.wolfram.com/PathGraph.html

RandomGraphFactoryExtension on GraphFactory<V, E>

Creates random graphs using different models.

RandomWalkGraphExtension on Graph<V, E>

ReversedGraphExtension on Graph<V, E>

RingGraphFactoryExtension on GraphFactory<V, E>

StarGraphFactoryExtension on GraphFactory<V, E>

https://mathworld.wolfram.com/StarGraph.html

TopologicalGraphExtension on Graph<V, E>

TreeGraphFactoryExtension on GraphFactory<V, E>

Creates m-ary trees (also known as n-ary, k-ary or k-way tree) in which each node has no more than m children.

UnmodifiableGraphExtension on Graph<V, E>

WhereGraphExtension on Graph<V, E>

Functions

aStarSearch<V>({required Iterable<V> startVertices, required bool targetPredicate(V vertex), required Iterable<V> successorsOf(V vertex), required num costEstimate(V source), num edgeCost(V source, V target)?, bool includeAlternativePaths = false, StorageStrategy<V>? vertexStrategy}) → Iterable<Path<V, num>>

A-Star search algorithm.

bronKerboschCliques<V>(Iterable<V> vertices, {required Iterable<V> neighboursOf(V vertex), required StorageStrategy<V> vertexStrategy}) → Iterable<Set<V>>

The Bron–Kerbosch algorithm enumerates all maximal cliques in an undirected graph. This implementation uses the variation with pivoting. The algorithm has exponential complexity, but for graphs with small outgoing vertex degree is fast.

dijkstraSearch<V>({required Iterable<V> startVertices, required bool targetPredicate(V vertex), required Iterable<V> successorsOf(V vertex), num edgeCost(V source, V target)?, bool includeAlternativePaths = false, StorageStrategy<V>? vertexStrategy}) → Iterable<Path<V, num>>

Dijkstra's search algorithm.

kruskalSpanningTree<V, E>(Graph<V, E> graph, {required num edgeWeight(V source, V target), required Comparator<num> weightComparator, required StorageStrategy<V> vertexStrategy}) → Graph<V, E>

Kruskal's algorithm to find the spanning tree in O(E*log(E)).

primSpanningTree<V, E>(Graph<V, E> graph, {required V? startVertex, required num edgeWeight(V source, V target), required Comparator<num> weightComparator, required StorageStrategy<V> vertexStrategy}) → Graph<V, E>

Prim's algorithm to find the spanning tree in O(E*log(V)).

tarjanStronglyConnected<V>(Iterable<V> vertices, {required Iterable<V> successorsOf(V vertex), required StorageStrategy<V> vertexStrategy}) → Iterable<Set<V>>

The Tarjan's algorithm enumerates the strongly connected components (SCCs). It runs in linear time.

Exceptions / Errors

GraphError

Error thrown when encountering unexpected graph types.