graph library

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 within a graph connects a source and a target vertex.
FloydWarshall<V>: The result of the Floyd-Warshall all-pairs shortest paths algorithm.
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 graph types efficiently.
IdentityStorageStrategy<T>: Strategy using canonical collection objects and identity comparison.
IntegerStorageStrategy: Strategy for int objects.
ObjectStorageStrategy<T>: Strategy using canonical collection objects.
Path<V, E>: A path within a graph connects a series of vertices through their respective edges and values.
PositiveIntegerStorageStrategy: Strategy for positive int objects.
RandomWalkIterable<V>: Iterable producing a random walk over a graph.
StoerWagnerMinCut<V, E>: Stoer–Wagner minimum cut algorithm in O(VE + V^2log(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>: Extension on Graph providing access to graph algorithms.
AtlasGraphFactoryExtension on GraphFactory<V, E>: Extension on GraphFactory to create graphs from the Atlas of Graphs.
BreadthFirstGraphExtension on Graph<V, E>: Extension on Graph to perform breadth-first traversals.
CollectionGraphFactoryExtension on GraphFactory<V, E>: Extension on GraphFactory to create graphs from collections of vertices and edges.
CompleteGraphFactoryExtension on GraphFactory<V, E>: https://mathworld.wolfram.com/CompleteGraph.html
ConnectedGraphExtension on Graph<V, E>: Extension on Graph to find connected components.
CopyGraphExtension on Graph<V, E>: Extension on Graph to copy graphs.
DepthFirstGraphExtension on Graph<V, E>: Extension on Graph to perform depth-first traversals.
DepthFirstPostOrderGraphExtension on Graph<V, E>: Extension on Graph to perform depth-first post-order traversals.
EmptyGraphFactoryExtension on GraphFactory<V, E>: Extension on GraphFactory to create an empty graph.
ExportGraphExtension on Graph<V, E>: Extension on Graph to export graphs in different formats.
LogicalGraphExtension on Graph<V, E>: Extension on Graph to perform logical set operations on graphs.
MapGraphExtension on Graph<V, E>: Extension on Graph to map vertices and edges to new values.
NumericPathExtension on Path<V, num>: Extension on Path where edge values are numbers.
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>: Extension on Graph to perform random walks.
ReversedGraphExtension on Graph<V, E>: Extension on Graph to reverse directed graphs.
RingGraphFactoryExtension on GraphFactory<V, E>: Extension on GraphFactory to create ring graphs.
StarGraphFactoryExtension on GraphFactory<V, E>: https://mathworld.wolfram.com/StarGraph.html
TopologicalGraphExtension on Graph<V, E>: Extension on Graph to perform topological traversals.
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>: Extension on Graph to create unmodifiable views.
WhereGraphExtension on Graph<V, E>: Extension on Graph to filter vertices and edges.

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.
bellmanFordSearch<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>>: Bellman-Ford shortest path 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.
floydWarshallSearch<V>({required Iterable<V> vertices, required Iterable<V> successorsOf(V vertex), num edgeCost(V source, V target)?, StorageStrategy<V>? vertexStrategy}) → FloydWarshall<V>: Floyd-Warshall all-pairs shortest paths algorithm.
hasCycle<V>({required Iterable<V> vertices, required Iterable<V> successorsOf(V vertex), StorageStrategy<V>? vertexStrategy}) → bool: Checks if a directed graph has a cycle.
isBipartite<V>({required Iterable<V> vertices, Iterable<V> neighboursOf(V vertex)?, Iterable<V> successorsOf(V vertex)?, StorageStrategy<V>? vertexStrategy}) → bool: Checks if a graph is bipartite.
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.
vertexColoring<V>({required Iterable<V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V>? vertexStrategy}) → Map<V, int>: Computes a greedy coloring of the vertices in a graph.

Exceptions / Errors

GraphError: Error thrown when encountering unexpected graph types.

Classes

Extensions

Functions

Exceptions / Errors

more package

graph library