Graph<V, E> class
abstract
Abstract base class of graphs.
Graph does not support parallel edges. If you re-add an edge with the same source and target vertex the previous edge is replaced with the new one. Use an Iterable as the edge-value, if you'd like to model a graph with parallel edges.
Graph allows self-loops (edges from a vertex to itself). If you do not want self-loops, do not create self-loops.
- Mixed-in types
- Implementers
- Available extensions
- AlgorithmsGraphExtension
- BreadthFirstGraphExtension
- ConnectedGraphExtension
- CopyGraphExtension
- DepthFirstGraphExtension
- DepthFirstPostOrderGraphExtension
- ExportGraphExtension
- LogicalGraphExtension
- MapGraphExtension
- RandomWalkGraphExtension
- ReversedGraphExtension
- TopologicalGraphExtension
- UnmodifiableGraphExtension
- WhereGraphExtension
Constructors
- Graph.new()
- Generative constructor.
-
Graph.directed({StorageStrategy<
V> ? vertexStrategy}) -
Constructs a directed graph.
factory
-
Graph.undirected({StorageStrategy<
V> ? vertexStrategy}) -
Constructs an undirected graph.
factory
Properties
- defaultToStringPrinter → ObjectPrinter
-
Override to configure the empty ObjectPrinter.
no setterinherited
-
edges
→ Iterable<
Edge< V, E> > -
Returns the edges of this graph.
no setter
- hashCode → int
-
The hash code for this object.
no setterinherited
- isDirected → bool
-
Returns
true
, if the graph is directed.no setter - isUnmodifiable → bool
-
Returns
true
, if the graph is unmodifiable.no setter -
reversed
→ Graph<
V, E> -
Available on Graph<
Returns a graph where all edges point in the opposite direction.V, E> , provided by the ReversedGraphExtension extensionno setter - runtimeType → Type
-
A representation of the runtime type of the object.
no setterinherited
- toStringPrinter → ObjectPrinter
-
Override and call super to add values to the ObjectPrinter.
no setteroverride
-
unmodifiable
→ Graph<
V, E> -
Available on Graph<
Returns a graph that throws an exception when being modified.V, E> , provided by the UnmodifiableGraphExtension extensionno setter -
vertexStrategy
→ StorageStrategy<
V> -
Returns a strategy to store vertices.
no setter
-
vertices
→ Iterable<
V> -
Returns the vertices of this graph.
no setter
Methods
-
addEdge(
V source, V target, {E? value}) → void -
Adds an edge between
source
andtarget
vertex. Optionally associates the providedvalue
with the edge. If the edge already exists, replaces the existing edge data. -
addVertex(
V vertex) → void -
Adds a
vertex
to this graph. -
addVertices(
Iterable< V> vertices) → void -
Adds all
vertices
to this graph. -
allShortestPaths(
{num edgeCost(V source, V target)?, StorageStrategy< V> ? vertexStrategy}) → FloydWarshall<V> -
Available on Graph<
Computes all shortest paths between all pairs of vertices in a graph.V, E> , provided by the AlgorithmsGraphExtension extension -
breadthFirst(
V vertex, {StorageStrategy< V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a breadth-first order, starting withV, E> , provided by the BreadthFirstGraphExtension extensionvertex
. -
breadthFirstAll(
Iterable< V> vertices, {StorageStrategy<V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a breadth-first order, starting withV, E> , provided by the BreadthFirstGraphExtension extensionvertices
. -
complement(
{bool allowSelfLoops = false, E? edge(V source, V target)?}) → Graph< V, E> -
Available on Graph<
Returns the complement of this graph, that is a graph with the same vertices but with edges between vertices that had no edge.V, E> , provided by the LogicalGraphExtension extension -
connected(
) → Iterable< Graph< V, E> > -
Available on Graph<
Returns an iterable of the connected sub-graphs.V, E> , provided by the ConnectedGraphExtension extension -
copy(
{bool empty = false}) → Graph< V, E> -
Available on Graph<
Creates a copy of this graph.V, E> , provided by the CopyGraphExtension extension -
depthFirst(
V vertex, {StorageStrategy< V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a depth-first order, starting withV, E> , provided by the DepthFirstGraphExtension extensionvertex
. -
depthFirstAll(
Iterable< V> vertices, {StorageStrategy<V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a depth-first order, starting withV, E> , provided by the DepthFirstGraphExtension extensionvertices
. -
depthFirstPostOrder(
V vertex, {StorageStrategy< V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a depth-first order, starting withV, E> , provided by the DepthFirstPostOrderGraphExtension extensionvertex
. -
depthFirstPostOrderAll(
Iterable< V> vertices, {StorageStrategy<V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a depth-first order, starting withV, E> , provided by the DepthFirstPostOrderGraphExtension extensionvertices
. -
edgesOf(
V vertex) → Iterable< Edge< V, E> > -
Returns the incoming and outgoing edges of
vertex
. -
findCliques(
{StorageStrategy< V> ? vertexStrategy}) → Iterable<Set< V> > -
Available on Graph<
Returns the maximal cliques in this undirected graph. The implementation uses the Bron–Kerbosch algorithm and runs in exponential time.V, E> , provided by the AlgorithmsGraphExtension extension -
getEdge(
V source, V target) → Edge< V, E> ? -
Returns the edge between
source
andtarget
, ornull
. -
incomingEdgesOf(
V vertex) → Iterable< Edge< V, E> > -
Returns the incoming edges of
vertex
. -
intersection(
Graph< V, E> other, {bool edgeCompare(V source, V target, E a, E b)?, E edgeMerge(V source, V target, E a, E b)?}) → Graph<V, E> -
Available on Graph<
Returns the intersection of this graph andV, E> , provided by the LogicalGraphExtension extensionother
. This is a graph with the nodes and edges present in both graphs.edgeMerge
specifies how parallel edges are merged, if unspecified the last one is used. -
map<
VR, ER> ({VR vertex(V vertex)?, ER? edge(Edge< V, E> edge)?, StorageStrategy<VR> ? vertexStrategy}) → Graph<VR, ER> -
Available on Graph<
Creates a new graph by mapping vertices and edges to new values.V, E> , provided by the MapGraphExtension extension -
maxFlow(
{num edgeCapacity(V source, V target)?, StorageStrategy< V> ? vertexStrategy}) → DinicMaxFlow<V> -
Available on Graph<
Returns an object that can compute the maximum flow between different vertices of this graph using the Dinic max flow algorithm.V, E> , provided by the AlgorithmsGraphExtension extension -
minCut(
{num edgeWeight(V source, V target)?, StorageStrategy< V> ? vertexStrategy}) → StoerWagnerMinCut<V, E> -
Available on Graph<
Returns an object that computes the min-cut using the Stoer-Wagner algorithm.V, E> , provided by the AlgorithmsGraphExtension extension -
neighboursOf(
V vertex) → Iterable< V> -
Returns the vertices that are adjacent to a
vertex
. -
noSuchMethod(
Invocation invocation) → dynamic -
Invoked when a nonexistent method or property is accessed.
inherited
-
outgoingEdgesOf(
V vertex) → Iterable< Edge< V, E> > -
Returns the outgoing edges of
vertex
. -
predecessorsOf(
V vertex) → Iterable< V> -
Returns the vertices that come before a
vertex
. -
putEdge(
V source, V target, E ifAbsent()) → E -
Look up the value of the edge between
source
andtarget
, or add a new edge with the value ofifAbsent
if it isn't there. -
randomWalk(
V vertex, {num edgeProbability(V source, V target)?, bool selfAvoiding = false, Random? random, StorageStrategy< V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a random order.V, E> , provided by the RandomWalkGraphExtension extension -
removeEdge(
V source, V target) → void -
Removes an edge between
source
andtarget
from this graph. -
removeVertex(
V vertex) → void -
Removes a
vertex
from this graph. -
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<
Performs a search for the shortest path betweenV, E> , provided by the AlgorithmsGraphExtension extensionsource
andtarget
. -
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<
Performs a search for the shortest paths starting atV, E> , provided by the AlgorithmsGraphExtension extensionsource
. -
spanningTree(
{V? startVertex, num edgeWeight(V source, V target)?, Comparator< num> ? weightComparator, StorageStrategy<V> ? vertexStrategy}) → Graph<V, E> -
Available on Graph<
Returns the spanning tree of the graph.V, E> , provided by the AlgorithmsGraphExtension extension -
stronglyConnected(
{StorageStrategy< V> ? vertexStrategy}) → Iterable<Set< V> > -
Available on Graph<
Returns the strongly connected components in this directed graph. The implementation uses the Tarjan's algorithm and runs in linear time.V, E> , provided by the AlgorithmsGraphExtension extension -
successorsOf(
V vertex) → Iterable< V> -
Returns the vertices that come after a
vertex
. -
toDot(
{Map< String, String> ? graphAttributes, String vertexLabel(V vertex)?, Map<String, String> vertexAttributes(V vertex)?, String edgeLabel(Edge<V, E> edge)?, Map<String, String> edgeAttributes(Edge<V, E> edge)?}) → String -
Available on Graph<
Export this graph to DOT Language typically used to describe Graphviz graphs.V, E> , provided by the ExportGraphExtension extension -
topological(
V vertex, {StorageStrategy< V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a topological order, starting withV, E> , provided by the TopologicalGraphExtension extensionvertex
. -
topologicalAll(
Iterable< V> vertices, {StorageStrategy<V> ? vertexStrategy}) → Iterable<V> -
Available on Graph<
Traverses the vertices in a topological order, starting withV, E> , provided by the TopologicalGraphExtension extensionvertices
. -
toString(
) → String -
Standard Object.toString implementation. Do not override, instead
implement toStringPrinter to customize.
inherited
-
union(
Graph< V, E> other, {E edgeMerge(V source, V target, E a, E b)?}) → Graph<V, E> -
Available on Graph<
Returns the union of this graph andV, E> , provided by the LogicalGraphExtension extensionother
. This is a graph with the nodes and edges present in either of the two graphs.edgeMerge
specifies how parallel edges are merged, if unspecified the last one is used. -
where(
{bool vertexPredicate(V vertex)?, bool edgePredicate(Edge< V, E> edge)?}) → Graph<V, E> -
Available on Graph<
Returns a new lazy Graph with all vertices that satisfy theV, E> , provided by the WhereGraphExtension extensionvertexPredicate
and all edges that satisfy theedgePredicate
.
Operators
-
operator ==(
Object other) → bool -
The equality operator.
inherited