WeightedDirectedGraph<T extends Object, W extends Comparable> class

A directed graph with vertices of type T and a weight of type W associated with each directed edges.

  • T must be usable as a map key.
Inheritance
Available extensions

Constructors

WeightedDirectedGraph.new(Map<T, Map<T, W>> edges, {required Summation<W> summation, required W zero, Comparator<T>? comparator})
Constructs a weighted directed graph with vertices of type T and associates to each graph edge a weight of type W.
WeightedDirectedGraph.of(WeightedDirectedGraph<T, W> graph)
Constructs a shallow copy of graph.
WeightedDirectedGraph.transitiveClosure(WeightedDirectedGraph<T, W> graph)
Constructs the transitive closure of graph.
factory

Properties

comparator ↔ Comparator<T>?
Returns the comparator used to sort graph vertices.
getter/setter pairinherited
crawler → GraphCrawler<T>
The graph crawler of this graph.
latefinalinherited
cycle → List<T>
Returns the first cycle detected or an empty list if the graph is acyclic.
no setterinherited
cycleVertex → T?
Returns the first vertex detected that is part of a cycle.
no setterinherited
data → Map<T, Map<T, W>>
Returns a copy of the weighted edges as an object of type Map<T, Map<T, W>>.
no setter
first → T
The first element.
no setterinherited
hasComparator → bool
Returns true if comparator is not null.
no setterinherited
hashCode → int
The hash code for this object.
no setterinherited
inDegreeMap → Map<T, int>
Returns a mapping between vertex and number of incoming connections.
no setterinherited
isAcyclic → bool
Returns true if the graph is a directed acyclic graph.
no setterinherited
isEmpty → bool
Whether this collection has no elements.
no setterinherited
isNotEmpty → bool
Whether this collection has at least one element.
no setterinherited
iterator → Iterator<T>
A new Iterator that allows iterating the elements of this Iterable.
no setteroverride
last → T
The last element.
no setterinherited
length → int
The number of elements in this Iterable.
no setterinherited
localSources → List<List<T>>?
Returns a list of type List<List<T>>. The first entry contains the local source vertices of the graph. Subsequent entries contain the local source vertices of the reduced graph. The reduced graph is obtained by removing all vertices listed in previous entries from the original graph.
no setterinherited
outDegreeMap → Map<T, int>
Returns a mapping between vertex and number of outgoing connections.
no setterinherited
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited
single → T
Checks that this iterable has only one element, and returns that element.
no setterinherited
sortedTopologicalOrdering → Set<T>?
Returns an ordered set of all vertices in topological order.
no setterinherited
sortedVertices → Iterable<T>
Returns an Iterable<T> of all vertices sorted using comparator.
no setterinherited
stronglyConnectedComponents → List<List<T>>
Returns a list of strongly connected components.
no setterinherited
summation → Summation<W>
Function used to sum edge weights.
final
topologicalOrdering → Set<T>?
Returns a set containing all graph vertices in topological order.
no setterinherited
transitiveWeightedEdges → Map<T, Map<T, W>>
Returns the weighted edges representing the transitive closure of this.
no setter
vertices → Iterable<T>
Returns a list of all vertices.
no setter
wait → Future<List<T>>

Available on Iterable<Future<T>>, provided by the FutureIterable extension

Waits for futures in parallel.
no setter
weight → W
Returns the sum of all graph edges.
no setter
zero → W
The weight of an empty path.
final

Methods

addEdge(T vertex, T connectedVertex, W weight) → void
Adds a new weighted edge pointing from vertex to connectedVertex.
addEdges(T vertex, Map<T, W> weightedEdges) → void
Adds weighted edges pointing from vertex to weightedEdges.keys.
any(bool test(T element)) → bool
Checks whether any element of this iterable satisfies test.
inherited
asNameMap() → Map<String, T>

Available on Iterable<T>, provided by the EnumByName extension

Creates a map from the names of enum values to the values.
byName(String name) → T

Available on Iterable<T>, provided by the EnumByName extension

Finds the enum value in this list with name name.
cast<R>() → Iterable<R>
A view of this iterable as an iterable of R instances.
inherited
clear() → void
Removes all graph edges.
contains(Object? element) → bool
Whether the collection contains an element equal to element.
inherited
edgeExists(T vertexOut, T vertexIn) → bool
Returns true if there is an edge pointing from vertexOut to vertexIn. Returns False otherwise.
edges(T vertex) → Iterable<T>
Returns the vertices connected to vertex. Note: Mathematically, an edge is an ordered pair (vertex, connected-vertex).
elementAt(int index) → T
Returns the indexth element.
inherited
every(bool test(T element)) → bool
Checks whether every element of this iterable satisfies test.
inherited
expand<T>(Iterable<T> toElements(T element)) → Iterable<T>
Expands each element of this Iterable into zero or more elements.
inherited
firstWhere(bool test(T element), {T orElse()?}) → T
The first element that satisfies the given predicate test.
inherited
fold<T>(T initialValue, T combine(T previousValue, T element)) → T
Reduces a collection to a single value by iteratively combining each element of the collection with an existing value
inherited
followedBy(Iterable<T> other) → Iterable<T>
Creates the lazy concatenation of this iterable and other.
inherited
forEach(void action(T element)) → void
Invokes action on each element of this iterable in iteration order.
inherited
heaviestPath(T start, T target) → List<T>
Returns the path connecting start and target with the largest summed edge-weight.
inDegree(T vertex) → int?
Returns the number of incoming directed edges for vertex.
inherited
join([String separator = ""]) → String
Converts each element to a String and concatenates the strings.
inherited
lastWhere(bool test(T element), {T orElse()?}) → T
The last element that satisfies the given predicate test.
inherited
lightestPath(T start, T target) → List<T>
Returns the path connecting start and target with the smallest summed edge-weight.
map<T>(T toElement(T e)) → Iterable<T>
The current elements of this iterable modified by toElement.
inherited
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
outDegree(T vertex) → int?
Returns the number of outgoing directed edges for vertex.
inherited
path(T start, T target) → List<T>
Returns the shortest detected path from start to target including cycles.
inherited
paths(T start, T target) → List<List<T>>
Returns all paths from start to target including cycles.
inherited
reachableVertices(T start) → Set<T>
Returns an iterable containing all vertices that are reachable from vertex start.
inherited
reduce(T combine(T value, T element)) → T
Reduces a collection to a single value by iteratively combining elements of the collection using the provided function.
inherited
remove(T vertex) → void
Completely removes vertex from the graph, including outgoing and incoming edges.
removeEdges(T vertex, Set<T> connectedVertices) → void
Removes edges pointing from vertex to connectedVertices.
removeIncomingEdges(T vertex) → void
Removes edges ending at vertex from the graph.
shortestPath(T start, T target) → List<T>
Returns the shortest path from the vertex start to the vertex target.
inherited
shortestPaths(T start) → Map<T, Iterable<T>>
Returns a map containing the shortest paths from start to each reachable vertex. The map keys represent the set of vertices reachable from start.
inherited
singleWhere(bool test(T element), {T orElse()?}) → T
The single element that satisfies test.
inherited
skip(int count) → Iterable<T>
Creates an Iterable that provides all but the first count elements.
inherited
skipWhile(bool test(T value)) → Iterable<T>
Creates an Iterable that skips leading elements while test is satisfied.
inherited
sortEdges([Comparator<T>? vertexComparator]) → void
Sorts the neighbouring vertices of each vertex using comparator.
sortEdgesByWeight([Comparator<W>? weightComparator]) → void
Sorts the neighbouring vertices of each vertex using weightComparator.
take(int count) → Iterable<T>
Creates a lazy iterable of the count first elements of this iterable.
inherited
takeWhile(bool test(T value)) → Iterable<T>
Creates a lazy iterable of the leading elements satisfying test.
inherited
toList({bool growable = true}) → List<T>
Creates a List containing the elements of this Iterable.
inherited
toSet() → Set<T>
Creates a Set containing the same elements as this iterable.
inherited
toString() → String
Returns a string representation of the weighted directed graph.
updateCache() → void
Marks cached variables as stale. This method is called every time vertices or edges are added or removed from the graph.
vertexExists(T vertex) → bool
Returns true if vertex is a graph vertex. Returns false otherwise.
weightAlong(Iterable<T> walk) → W
Returns the weight obtained by traversing walk and summing all edge weights.
where(bool test(T element)) → Iterable<T>
Creates a new lazy Iterable with all elements that satisfy the predicate test.
inherited
whereType<T>() → Iterable<T>
Creates a new lazy Iterable with all elements that have type T.
inherited

Operators

operator ==(Object other) → bool
The equality operator.
inherited