DirectedGraph<T extends Object> class

Generic directed graph storing vertices of type T.

The data-type T should be usable as a map key.

Inheritance
Implementers
Available extensions

Constructors

DirectedGraph(Map<T, Set<T>> edges, {Comparator<T>? comparator})
Constructs a directed graph.
DirectedGraph.fromWeightedEdges(Map<T, Map<T, dynamic>> weightedEdges, {Comparator<T>? comparator})
Constructs a directed graph from a map of weighted edges.
DirectedGraph.of(DirectedGraph<T> graph)
Constructs a shallow copy of graph.
DirectedGraph.transitiveClosure(DirectedGraph<T> graph)
Factory constructor returning the transitive closure of graph.
factory

Properties

comparator ↔ Comparator<T>?
Returns the current comparator. This could be:
getter/setter pairinherited
crawler → GraphCrawler<T>
The graph crawler of this graph.
latefinalinherited
cycleVertex → T?
Returns the first vertex detected that forms part of a cycle if the graph is cyclic and null otherwise.
no setterinherited
data → Map<T, Set<T>>
Returns a copy of the graph edges as a map of type Map<T, Set<T>>.
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
inverseComparator → Comparator<T>?
Returns the inverse of comparator. Returns null if the graph has no comparator (that was set by the user of provided as constructor parameter).
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 setter
length → int
Returns the number of graph vertices. Classes extending DirectedGraphBase should make sure that the length is obtained from an EfficientLengthIterable.
no setter
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
sortedVertices → Set<T>
Returns an set containing all vertices sorted using comparator. If comparator is null this getter returns the original unsorted set of vertices.
no setterinherited
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

Methods

addEdge(T vertex, T connectedVertex) → void
Adds a new edge pointing from vertex to connectedVertex.
addEdges(T vertex, Set<T> connectedVertices) → void
Adds edges (connections) pointing from vertex to connectedVertices.
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.
cycle() → List<T>
Returns the first cycle detected or an empty list if the graph is acyclic.
inherited
edgeExists(T vertexOut, T vertexIn) → bool
Returns true if there is an edge pointing from source to target. Returns False otherwise.
edges(T vertex) → Set<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
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
localSources() → List<Set<T>>?
Returns a list of type List<Set<T>> if the graph is acyclic or null otherwise.
inherited
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
quasiTopologicalOrdering(Set<T> vertices, {bool sorted = false}) → Set<T>?
Returns a set containing the elements of vertices in quasi-topological insertion order.
inherited
reachableVertices(T start) → Set<T>
Returns a set 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 (connections) pointing from vertex to connectedVertices.
removeIncomingEdges(T vertex) → void
Removes edges ending at vertex from the graph.
reverseQuasiTopologicalOrdering(Set<T> vertices, {bool sorted = false}) → Set<T>?
Returns a set containing the elements of vertices in reverse quasi topological insertion order if there is not mutual connection between any two elements of vertices.
inherited
reverseTopologicalOrdering({bool sorted = false}) → Set<T>?
Returns an ordered set of all vertices in topological order.
inherited
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() → void
Sorts the neighbouring vertices of each vertex using comparator.
stronglyConnectedComponents({bool sorted = false, Comparator<T>? comparator}) → List<Set<T>>
Returns a list of strongly connected components (SCC). The vertices are sorted if sorted is set to true and a comparator is provided. The graph comparator is used as a fallback.
inherited
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
topologicalOrdering({bool sorted = false}) → Set<T>?
Returns an ordered set of all vertices in topological order.
inherited
toSet() → Set<T>
Creates a Set containing the same elements as this iterable.
inherited
toString() → String
Returns a String representation of the graph.
inherited
updateCache() → void
Marks cached variables as stale. This method is called every time vertices or edges are added or removed from the graph.
inherited
vertexExists(T vertex) → bool
Returns true if vertex is a graph vertex. Returns false otherwise.
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