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

• ToStringPrinter

Implementers

• ForwardingGraph

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 setter, inherited

edges → Iterable<Edge<V, E>>

Returns the edges of this graph.

no setter

hashCode → int

The hash code for this object.

no setter, inherited

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<V, E>, provided by the ReversedGraphExtension extension

Returns a graph where all edges point in the opposite direction.

no setter

runtimeType → Type

A representation of the runtime type of the object.

no setter, inherited

toStringPrinter → ObjectPrinter

Override and call super to add values to the ObjectPrinter.

no setter, override

unmodifiable → Graph<V, E>

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

Returns a graph that throws an exception when being modified.

no 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 and target vertex. Optionally associates the provided value 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<V, E>, provided by the AlgorithmsGraphExtension extension

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

breadthFirst(V vertex, {StorageStrategy<V>? vertexStrategy}) → Iterable<V>

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

Traverses the vertices in a breadth-first order, starting with vertex.

breadthFirstAll(Iterable<V> vertices, {StorageStrategy<V>? vertexStrategy}) → Iterable<V>

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

Traverses the vertices in a breadth-first order, starting with vertices.

complement({bool allowSelfLoops = false, E? edge(V source, V target)?}) → Graph<V, E>

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

Returns the complement of this graph, that is a graph with the same vertices but with edges between vertices that had no edge.

connected() → Iterable<Graph<V, E>>

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

Returns an iterable of the connected sub-graphs.

copy({bool empty = false}) → Graph<V, E>

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

Creates a copy of this graph.

depthFirst(V vertex, {StorageStrategy<V>? vertexStrategy}) → Iterable<V>

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

Traverses the vertices in a depth-first order, starting with vertex.

depthFirstAll(Iterable<V> vertices, {StorageStrategy<V>? vertexStrategy}) → Iterable<V>

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

Traverses the vertices in a depth-first order, starting with vertices.

depthFirstPostOrder(V vertex, {StorageStrategy<V>? vertexStrategy}) → Iterable<V>

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

Traverses the vertices in a depth-first order, starting with vertex.

depthFirstPostOrderAll(Iterable<V> vertices, {StorageStrategy<V>? vertexStrategy}) → Iterable<V>

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

Traverses the vertices in a depth-first order, starting with vertices.

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<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.

getEdge(V source, V target) → Edge<V, E>?

Returns the edge between source and target, or null.

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<V, E>, provided by the LogicalGraphExtension extension

Returns the intersection of this graph and other. 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<V, E>, provided by the MapGraphExtension extension

Creates a new graph by mapping vertices and edges to new values.

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.

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 and target, or add a new edge with the value of ifAbsent 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<V, E>, provided by the RandomWalkGraphExtension extension

Traverses the vertices in a random order.

removeEdge(V source, V target) → void

Removes an edge between source and target 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<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.

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<V, E>, provided by the ExportGraphExtension extension

Export this graph to DOT Language typically used to describe Graphviz graphs.

topological(V vertex, {StorageStrategy<V>? vertexStrategy}) → Iterable<V>

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

Traverses the vertices in a topological order, starting with vertex.

topologicalAll(Iterable<V> vertices, {StorageStrategy<V>? vertexStrategy}) → Iterable<V>

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

Traverses the vertices in a topological order, starting with vertices.

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<V, E>, provided by the LogicalGraphExtension extension

Returns the union of this graph and other. 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<V, E>, provided by the WhereGraphExtension extension

Returns a new lazy Graph with all vertices that satisfy the vertexPredicate and all edges that satisfy the edgePredicate.

Operators

operator ==(Object other) → bool

The equality operator.

inherited