AlgorithmsGraphExtension<V, E> extension

on

• Graph<V, E>

Methods

allShortestPaths({num edgeCost(V source, V target)?, StorageStrategy<V>? vertexStrategy}) → FloydWarshall<V>

Available on Graph<V, E>, provided by the AlgorithmsGraphExtension extension

Computes all shortest paths between all pairs of vertices in a graph.

findCliques({StorageStrategy<V>? vertexStrategy}) → Iterable<Set<V>>

Available on Graph<V, E>, provided by the AlgorithmsGraphExtension extension

Returns the maximal cliques in this undirected graph. The implementation uses the Bron–Kerbosch algorithm and runs in exponential time.

maxFlow({num edgeCapacity(V source, V target)?, StorageStrategy<V>? vertexStrategy}) → DinicMaxFlow<V>

Available on Graph<V, E>, provided by the AlgorithmsGraphExtension extension

Returns an object that can compute the maximum flow between different vertices of this graph using the Dinic max flow algorithm.

minCut({num edgeWeight(V source, V target)?, StorageStrategy<V>? vertexStrategy}) → StoerWagnerMinCut<V, E>

Available on Graph<V, E>, provided by the AlgorithmsGraphExtension extension

Returns an object that computes the min-cut using the Stoer-Wagner algorithm.

shortestPath(V source, V target, {num edgeCost(V source, V target)?, num costEstimate(V vertex)?, bool includeAlternativePaths = false, bool hasNegativeEdges = false, StorageStrategy<V>? vertexStrategy}) → Path<V, num>?

Available on Graph<V, E>, provided by the AlgorithmsGraphExtension extension

Performs a search for the shortest path between source and target.

shortestPathAll(V source, {Predicate1<V>? targetPredicate, num edgeCost(V source, V target)?, num costEstimate(V target)?, bool includeAlternativePaths = false, bool hasNegativeEdges = false, StorageStrategy<V>? vertexStrategy}) → Iterable<Path<V, num>>

Available on Graph<V, E>, provided by the AlgorithmsGraphExtension extension

Performs a search for the shortest paths starting at source.

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

Available on Graph<V, E>, provided by the AlgorithmsGraphExtension extension

Returns the spanning tree of the graph.

stronglyConnected({StorageStrategy<V>? vertexStrategy}) → Iterable<Set<V>>

Available on Graph<V, E>, provided by the AlgorithmsGraphExtension extension

Returns the strongly connected components in this directed graph. The implementation uses the Tarjan's algorithm and runs in linear time.