DirectedGraph<T> class

Generic directed graph. Data of type T is stored in vertices of type Vertex. The graph consists of a mapping _edges of each Vertex<T> to a list of connected vertices List<Vertex<T>>.

Inheritance

Constructors

DirectedGraph(Map<Vertex<T>, List<Vertex<T>>> edges, {Comparator<Vertex<T>> comparator})
Constructs a directed graph. edges is of type Map<Vertex<T>, List<Vertex<T>>>, mapping each vertex to a list of connected vertices.
DirectedGraph.from(DirectedGraph<T> directedGraph)
Constructs a directed graph from another directed graph.
DirectedGraph.fromData(Map<T, List<T>> data, {Comparator<Vertex<T>> comparator})
Constructs a directed graph from a map of type Map<T, List<T>>. [...]

Properties

comparator Comparator<Vertex<T>>
read / write
cycle List<Vertex<T>>
Returns the first cycle detected or an empty list if the graph is acyclic. [...]
read-only
data Map<T, List<T>>
Returns the underlying graph data as a map of type Map<T, List<T>>.
read-only
displayStructure String
Returns a String representation of the graph using the vertex id instead of the vertex data.
read-only
edgeMap Map<Vertex<T>, List<Vertex<T>>>
Mapping each graph vertex to a list of connected vertice.
read-only
first → dynamic
Returns the first element. [...]
read-only, inherited
hashCode int
The hash code for this object. [...]
read-only, inherited
inDegreeMap Map<Vertex<T>, int>
Returns a (modifiable) copy of the inDegreeMap.
read-only
isAcyclic bool
Returns true if the graph is a directed acyclic graph.
read-only
isEmpty bool
Returns true if there are no elements in this collection. [...]
read-only, inherited
isNotEmpty bool
Returns true if there is at least one element in this collection. [...]
read-only, inherited
iterator Iterator<Vertex<T>>
Returns a new Iterator that allows iterating the elements of this Iterable. [...]
read-only, override
last → dynamic
Returns the last element. [...]
read-only, inherited
length int
Returns the number of elements in this. [...]
read-only, inherited
localSources List<List<Vertex<T>>>
Returns a list of type List<List<Vertex<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. [...]
read-only
outDegreeMap Map<Vertex<T>, int>
Returns a mapping between vertex and number of outgoing connections (edges).
read-only
runtimeType Type
A representation of the runtime type of the object.
read-only, inherited
single → dynamic
Checks that this iterable has only one element, and returns that element. [...]
read-only, inherited
sortedTopologicalOrdering List<Vertex<T>>
Returns a list of all vertices in topological order. [...]
read-only
stronglyConnectedComponents List<List<Vertex<T>>>
Returns a valid reverse topological order ordering of the strongly connected components. Acyclic graphs will yield components containing one vertex only.
read-only
topologicalOrdering List<Vertex<T>>
Returns List<Vertex<T>>, a list of all vertices in topological order. [...]
read-only
vertices UnmodifiableListView<Vertex<T>>
Unmodifiable ListView of all vertices in the graph. The vertices will be sorted if a vertex comparator was specified during instantiation of the graph or by invoking the comparator setter.
read-only

Methods

addEdges(Vertex<T> vertex, List<Vertex<T>> connectedVertices) → void
Adds edges (connections) pointing from vertex to connectedVertices. If the graph does not contain vertex it will be added.
any(bool test(dynamic element)) bool
Checks whether any element of this iterable satisfies test. [...]
inherited
cast<R>() Iterable<R>
Provides a view of this iterable as an iterable of R instances. [...]
inherited
contains(Object element) bool
Whether the collection contains an element equal to element. [...]
inherited
edges(Vertex<T> vertex) List<Vertex<T>>
Returns a list of the connected vertices of vertex. Note: Mathematically, an edge is an ordered pair (vertex, connected-vertex).
elementAt(int index) → dynamic
Returns the indexth element. [...]
inherited
every(bool test(dynamic element)) bool
Checks whether every element of this iterable satisfies test. [...]
inherited
expand<T>(Iterable<T> toElements(dynamic element)) Iterable<T>
Expands each element of this Iterable into zero or more elements. [...]
inherited
findCycle() List<Vertex<T>>
Returns the first cycle detected or an empty list if the graph is acyclic. In general, the getter method cycle is faster, but findCycle() is efficient if the graph is sparcely connected. [...]
firstWhere(bool test(dynamic element), {dynamic orElse()}) → dynamic
Returns the first element that satisfies the given predicate test. [...]
inherited
fold<T>(T initialValue, T combine(T previousValue, dynamic element)) → T
Reduces a collection to a single value by iteratively combining each element of the collection with an existing value [...]
inherited
followedBy(Iterable other) Iterable
Returns the lazy concatenation of this iterable and other. [...]
inherited
forEach(void action(dynamic element)) → void
Invokes action on each element of this iterable in iteration order.
inherited
inDegree(Vertex<T> vertex) int
Returns the number of incoming directed edges for vertex.
join([String separator = ""]) String
Converts each element to a String and concatenates the strings. [...]
inherited
lastWhere(bool test(dynamic element), {dynamic orElse()}) → dynamic
Returns the last element that satisfies the given predicate test. [...]
inherited
map<T>(T toElement(dynamic e)) Iterable<T>
The current elements of this iterable modified by toElement. [...]
inherited
noSuchMethod(Invocation invocation) → dynamic
Invoked when a non-existent method or property is accessed. [...]
inherited
outDegree(Vertex<T> vertex) int
Returns the number of outgoing directed edges for vertex.
reduce(dynamic combine(dynamic value, dynamic element)) → dynamic
Reduces a collection to a single value by iteratively combining elements of the collection using the provided function. [...]
inherited
remove(Vertex<T> vertex) → void
Completely remove vertex from the graph, including outgoing and incoming edges.
removeEdges(Vertex<T> vertex, [List<Vertex<T>> connectedVertices]) → void
Removes edges (connections) pointing from vertex to connectedVertices. If connectedVertices is not specified all outgoing edges are removed from the graph.
removeIncomingEdges(Vertex<T> vertex) → void
Removes edges ending at vertex from the graph.
shortestPath(Vertex<T> start, Vertex<T> target) List<Vertex<T>>
Returns the shortest path between start and target. Returns null if start is not connected to target.
shortestPaths(Vertex<T> start) Map<Vertex<T>, List<Vertex<T>>>
Returns a Map of the shortest paths from start to each node in the directed graph defined by edges.
singleWhere(bool test(dynamic element), {dynamic orElse()}) → dynamic
Returns the single element that satisfies test. [...]
inherited
skip(int count) Iterable
Returns an Iterable that provides all but the first count elements. [...]
inherited
skipWhile(bool test(dynamic value)) Iterable
Returns an Iterable that skips leading elements while test is satisfied. [...]
inherited
take(int count) Iterable
Returns a lazy iterable of the count first elements of this iterable. [...]
inherited
takeWhile(bool test(dynamic value)) Iterable
Returns a lazy iterable of the leading elements satisfying test. [...]
inherited
toList({bool growable = true}) List
Creates a List containing the elements of this Iterable. [...]
inherited
toSet() Set
Creates a Set containing the same elements as this iterable. [...]
inherited
toString() String
Returns a string representation of the graph.
override
where(bool test(dynamic element)) Iterable
Returns a new lazy Iterable with all elements that satisfy the predicate test. [...]
inherited
whereType<T>() Iterable<T>
Returns a new lazy Iterable with all elements that have type T. [...]
inherited

Operators

operator ==(Object other) bool
The equality operator. [...]
inherited