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 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.
-
TransitiveGraphExtension
on Graph<
V, E> - Extension on Graph providing transitive closure and transitive reduction.
-
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
-
approximateMaximumIndependentSet<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Set<V> - Computes an approximate maximum independent set using a greedy minimum-degree heuristic.
-
approximateMinimumVertexCover<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Set<V> -
Computes a 2-approximate minimum vertex cover of an undirected graph in
O(|V| + |E|)time. -
articulationPoints<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Set<V> - Finds articulation points (cut vertices) in an undirected graph.
-
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.
-
averageClusteringCoefficient<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), required Iterable<V> successorsOf(V vertex), required bool isDirected, StorageStrategy<V> ? vertexStrategy}) → double -
Returns the average clustering coefficient across all
verticesin the graph. -
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.
-
betweennessCentrality<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), bool isDirected = true, bool normalized = true, StorageStrategy<V> ? vertexStrategy}) → Map<V, double> -
Computes betweenness centrality for all
verticesusing Brandes's algorithm (O(|V| * |E|)for unweighted graphs). -
biconnectedComponents<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Iterable<BiconnectedComponent< V> > - Computes the biconnected components of an undirected graph.
-
bipartiteMatching<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Map<V, V> - Computes the maximum bipartite matching of an undirected bipartite graph using the Hopcroft–Karp algorithm (O(E * sqrt(V))).
-
bridges<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Set<(V, V)> - Finds bridges (cut edges) in an undirected graph.
-
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.
-
coreNumbers<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Map<V, int> -
Computes the core numbers of all
verticesusing the Matula–BeckO(|V| + |E|)algorithm. -
degreeAssortativity<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), Iterable<V> predecessorsOf(V vertex)?, required bool isDirected, StorageStrategy<V> ? vertexStrategy}) → double - Computes the degree assortativity coefficient of a graph.
-
degreeCentrality<
V> ({required Iterable< V> vertices, required int degreeOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Map<V, double> -
Computes the degree centrality of all
vertices. -
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.
-
edgeConnectivity<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), bool containsEdge(V source, V target)?, bool isDirected = false, V? source, V? target, StorageStrategy<V> ? vertexStrategy}) → int -
Computes the edge connectivity of a graph or between
sourceandtarget. -
eigenvectorCentrality<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), Iterable<V> predecessorsOf(V vertex)?, num edgeWeight(V source, V target)?, int maxIterations = 100, double tolerance = 1e-6, StorageStrategy<V> ? vertexStrategy}) → Map<V, double> -
Computes the eigenvector centrality of all
verticesusing power iteration. -
findEulerianPath<
V, E> ({required Iterable< V> vertices, required Iterable<Edge< outgoingEdgesOf(V vertex), required bool isDirected, int inDegreeOf(V vertex)?, int outDegreeOf(V vertex)?, int degreeOf(V vertex)?, bool containsEdge(V u, V v)?, bool circuit = false, StorageStrategy<V, E> >V> ? vertexStrategy}) → Path<V, E> ? - Finds an Eulerian path or circuit in a graph using Hierholzer's algorithm.
-
findHamiltonianPath<
V, E> ({required Iterable< V> vertices, Iterable<Edge< outgoingEdgesOf(V vertex)?, Iterable<V, E> >V> successorsOf(V vertex)?, required bool isDirected, bool circuit = false, StorageStrategy<V> ? vertexStrategy}) → Path<V, E> ? - Finds a Hamiltonian path or circuit in a graph.
-
findIsomorphisms<
VT, ET, VP, EP> ({required Iterable< VT> targetVertices, required Iterable<VP> patternVertices, required Iterable<VT> targetSuccessorsOf(VT vertex), required Iterable<VP> patternSuccessorsOf(VP vertex), Iterable<VT> targetPredecessorsOf(VT vertex)?, Iterable<VP> patternPredecessorsOf(VP vertex)?, int? targetEdgeCount, int? patternEdgeCount, bool isDirected = false, bool subgraph = false, bool vertexComparator(VT targetVertex, VP patternVertex)?, bool edgeComparator(ET targetEdgeValue, EP patternEdgeValue)?, ET? targetEdgeValue(VT source, VT target)?, EP? patternEdgeValue(VP source, VP target)?, StorageStrategy<VT> ? targetStrategy, StorageStrategy<VP> ? patternStrategy}) → Iterable<Map< VP, VT> > - Finds isomorphisms or subgraph isomorphisms between target and pattern using the VF2 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.
-
graphDensity<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), required bool isDirected}) → double - Computes the density of a graph.
-
graphTransitivity<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → double - Returns the transitivity (global clustering coefficient) of an undirected graph.
-
hasCycle<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → bool - Checks if a directed graph has a cycle.
-
hasEulerianCircuit<
V, E> ({required Iterable< V> vertices, required Iterable<Edge< outgoingEdgesOf(V vertex), required bool isDirected, int inDegreeOf(V vertex)?, int outDegreeOf(V vertex)?, int degreeOf(V vertex)?, bool containsEdge(V u, V v)?, StorageStrategy<V, E> >V> ? vertexStrategy}) → bool - Checks if a graph has an Eulerian circuit (a closed trail visiting every edge exactly once).
-
hasEulerianPath<
V, E> ({required Iterable< V> vertices, required Iterable<Edge< outgoingEdgesOf(V vertex), required bool isDirected, int inDegreeOf(V vertex)?, int outDegreeOf(V vertex)?, int degreeOf(V vertex)?, bool containsEdge(V u, V v)?, StorageStrategy<V, E> >V> ? vertexStrategy}) → bool - Checks if a graph has an Eulerian path (a trail visiting every edge exactly once).
-
hasHamiltonianCircuit<
V, E> ({required Iterable< V> vertices, Iterable<Edge< outgoingEdgesOf(V vertex)?, Iterable<V, E> >V> successorsOf(V vertex)?, required bool isDirected, StorageStrategy<V> ? vertexStrategy}) → bool - Checks if a graph has a Hamiltonian circuit (a closed cycle visiting every vertex exactly once).
-
hasHamiltonianPath<
V, E> ({required Iterable< V> vertices, Iterable<Edge< outgoingEdgesOf(V vertex)?, Iterable<V, E> >V> successorsOf(V vertex)?, required bool isDirected, StorageStrategy<V> ? vertexStrategy}) → bool - Checks if a graph has a Hamiltonian path (a path visiting every vertex exactly once).
-
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.
-
isPlanar<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → bool - Tests whether an undirected graph is planar using the Left–Right planarity test.
-
kCoreVertices<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), required int k, StorageStrategy<V> ? vertexStrategy}) → Set<V> - Computes the set of vertices belonging to the k-core of a graph.
-
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)).
-
labelPropagationCommunities<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), num edgeWeight(V source, V target)?, int maxIterations = 100, Random? random, StorageStrategy<V> ? vertexStrategy}) → Iterable<Set< V> > - Detects communities in an undirected graph using the asynchronous label propagation algorithm (LPA).
-
localClusteringCoefficient<
V> (V vertex, {required Iterable< V> neighboursOf(V vertex), required Iterable<V> successorsOf(V vertex), required bool isDirected, StorageStrategy<V> ? vertexStrategy}) → double -
Returns the local clustering coefficient of
vertex. -
louvainCommunities<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), num edgeWeight(V source, V target)?, double resolution = 1.0, StorageStrategy<V> ? vertexStrategy}) → Iterable<Set< V> > - Detects communities in an undirected graph by maximizing modularity using the Louvain algorithm.
-
maximumIndependentSet<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), bool approximate = false, StorageStrategy<V> ? vertexStrategy}) → Set<V> - Computes a maximum independent set of an undirected graph.
-
maximumMatching<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), StorageStrategy<V> ? vertexStrategy}) → Map<V, V> - Computes a maximum cardinality matching in an undirected graph using Edmonds' Blossom algorithm (O(|V|^3)).
-
minimumVertexCover<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), bool approximate = false, StorageStrategy<V> ? vertexStrategy}) → Set<V> - Computes a minimum vertex cover of an undirected graph.
-
modularity<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), required Iterable<Set< communities, num edgeWeight(V source, V target)?, required bool isDirected, StorageStrategy<V> >V> ? vertexStrategy}) → double -
Computes the Newman–Girvan modularity of
communitiesin a graph. -
pageRank<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), Iterable<V> predecessorsOf(V vertex)?, double damping = 0.85, double tolerance = 1e-6, int maxIterations = 100, StorageStrategy<V> ? vertexStrategy}) → Map<V, double> -
Computes the PageRank of
verticesusing power iteration. -
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.
-
vertexConnectivity<
V> ({required Iterable< V> vertices, required Iterable<V> successorsOf(V vertex), bool containsEdge(V source, V target)?, bool isDirected = false, V? source, V? target, StorageStrategy<V> ? vertexStrategy}) → int -
Computes vertex connectivity of a graph or between
sourceandtarget. -
weightedBipartiteMatching<
V> ({required Iterable< V> vertices, required Iterable<V> neighboursOf(V vertex), required num edgeWeight(V source, V target), bool maximumWeight = true, StorageStrategy<V> ? vertexStrategy}) → Map<V, V> - Computes the maximum weight bipartite matching of an undirected bipartite graph.
Exceptions / Errors
- GraphError
- Error thrown when encountering unexpected graph types.