AdjacencyListGraph<E> class abstract final Graphs

An unweighted graph suitable for sparse graphs.

The adjacency list representation of a graph is a collection of lists, one for each node in the graph. Each list contains the nodes that are adjacent to the node that the list represents, and is associated with the node with a hash table.

Implicitly adds and removes nodes as edges are added and removed, respectively. A node is considered to be in the graph if it is present in the adjacency list of another node or if it has one or more edges originating from it:

final graph = AdjacencyListGraph<String>();

graph.addEdge(Edge('a', 'b'));
graph.addEdge(Edge('b', 'c'));
print(graph.roots); // ['a']
print(graph.isEmpty); // false

graph.removeEdge(Edge('a', 'b'));
print(graph.roots); // []
print(graph.isEmpty); // true

Performance

The adjacency list representation is ideal for sparse graphs, where the number of edges is much smaller than the number of nodes, or small overall; in this case, the adjacency list representation can be more memory efficient than other representations.

Operation	Time Complexity
`containsEdge`	O(1)
`containsRoot`	O(n)
`addEdge`	O(1)
`removeEdge`	O(m)`^1`
`edges`	O(n + m)

^1: Where m is the number of edges in the source node.

Mixed in types

Walkable<E>
Graph<E>

Constructors

AdjacencyListGraph({bool directed = true}): Creates an empty adjacency list graph.
factory
AdjacencyListGraph.from(WalkableBase<E> walkable, {bool directed = true}): Creates an adjacency list graph from a walkable.
factory
AdjacencyListGraph.fromEdges(Iterable<Edge<E>> edges, {bool directed = true}): Creates an adjacency list graph from edges.
factory

Properties

edges → Iterable<Edge<E>>: Each edge in the collection.
no setterinherited
hashCode → int: The hash code for this object.
no setterinherited
isEmpty → bool: Returns true if the walkable collection has no nodes.
no setterinherited
isNotEmpty → bool: Returns true if the walkable collection has one or more nodes.
no setterinherited
roots → Iterable<E>: Each node that is exposed as a root node of the walkable collection.
no setterinherited
runtimeType → Type: A representation of the runtime type of the object.
no setterinherited

Methods

addEdge(Edge<E> edge) → bool: Adds an edge from to the graph.
inherited
addEdges(Iterable<Edge<E>> edges) → void: Adds multiple edges to the graph.
inherited
asUnweighted() → Walkable<E>: Returns a view of this walkable as an unweighted walkable.
inherited
asWeighted(double weight(E source, E target)) → WeightedWalkable<E>: Returns a view of this walkable as a weighted walkable.
inherited
clear() → void: Clears the graph of all nodes and edges.
inherited
containsEdge(Edge<E> edge) → bool: Returns whether the collection contains an edge connecting two nodes.
inherited
containsRoot(E node) → bool: Returns whether the collection contains a root node.
inherited
noSuchMethod(Invocation invocation) → dynamic: Invoked when a nonexistent method or property is accessed.
inherited
removeEdge(Edge<E> edge) → bool: Removes an edge from the graph.
inherited
successors(E node) → Iterable<E>: Returns each distinct node that is a direct successor of the given node.
inherited
toString() → String: Returns a string representation of (some of) the nodes of this.
inherited

Operators

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