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 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, 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
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.
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
topologicalOrdering → Set<T>?
Returns a set containing all graph vertices in topological order.
no setterinherited
vertices → Iterable<T>
Returns a list of all vertices.
no setter

Methods

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
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
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
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 (connections) 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() → void
Sorts the neighbouring vertices of each vertex using comparator.
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 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