## Collections in Dart: The Directed Graph

By Richard Griffith on Tuesday, February 19 2013, 12:18 - Dart - Permalink

A directed graph, or digraph, can be considered as a set of objects with pairwise connections with a defined orientation. For example, a one way street on a map, outbound or inbound links between web pages, and dependencies in software modules. Real world digraphs tend to be sparse and, as a result, the proper representation of the digraph involves a tradeoff between the efficient use of memory and the ease of graph manipulation.

### Introduction

In this article, we explore some of the features of Dart's [1] collection library [2] to implement an adjacency set representation of a directed graph given a list of graph edges. A directed graph, or digraph, can be considered as a set of objects with pairwise connections with a defined orientation. For example, a one way street on a map, outbound or inbound links between web pages, and dependencies in software modules. Real world digraphs tend to be sparse and, as a result, the proper representation of the digraph involves a tradeoff between the efficient use of memory and the ease of graph manipulation [3].

Representation | Space | Find Edge | Enumerate Incident Edges |
---|---|---|---|

edge list |
E | E | E |

adjacency matrix |
V^{2} |
1 | V |

adjacency list |
E + V | degree(V) | degree(V) |

adjacency set |
E + V | log(degree(V)) | degree(V) |

Since graph algorithms are largely based on iterating over the edges incident to a particular vertex, a simple edge list becomes impractical for even a relative small number of edges. For dense graphs (ie, the number of edges E approaches the square of the number of vertices V), the adjacency matrix offers an excellent way to rapidly determine if an edge exists between two vertices. In fact, in several future posts, we will look at a number of algorithms where the graph is ideally represented as an adjacency matrix (Prim's MST and Floyd-Warshall's all pairs shortest path are two examples). However, for large, sparse graphs, the memory requirement of an adjacency matrix can be difficult to justify and may not be practical to implement. A more common approach is to represents sparse graphs as adjacency lists or adjacency sets [4]. We will use an adjacency set implementation to structure our directed graph class.

### The Directed Graph Class

We begin by creating a new class that extends the `IterableBase`

abstract class in the collections library, `dart:collection`

. By extending `IterableBase`

, we will be able to explore our directed graph using the for-in construct of the `HashMap`

object that is used to store our graph. Since our class will make use of both the `HashMap`

and `HashSet`

classes as well as `IterableBase`

, we will need to import the collections library at our `graphlab`

library level. This class will need to provide methods for adding a node, adding and removing an edge, checking for the existence of an edge, as well as providing a set of all edges incident on a node. The class is implemented as follows [5]:

```
part of graphlab;
class DirectedGraph extends IterableBase {
final HashMap dGraph = new HashMap();
/// Adds a new node to the graph. If the node already exists, then the
/// graph is unchanged.
HashMap addNode(var node) {
if (!dGraph.containsKey(node)) {
dGraph[node] = new HashSet();
}
}
/// Given a start and destination node, adds an arc from the start node
/// to the destination. If the edge already exists, then the graph is
/// unchanged. If either endpoint does not exist in the graph, throws a
/// NoSuchElementException.
HashMap addEdge(var start, var dest) {
if (dGraph.containsKey(start) && dGraph.containsKey(dest)) {
dGraph[start].add(dest);
} else {
throw new NoSuchElementException("Both nodes must be in the graph.");
}
}
/// Removes the edge from start to dest from the graph. If the edge does
/// not exist, then returns the HashMap unchanged. If either endpoint does
/// not exist in the graph, throws a NoSuchElementException.
HashMap removeEdge(var start, var dest) {
if (dGraph.containsKey(start) && dGraph.containsKey(dest)) {
dGraph[start].remove(dest);
} else {
throw new NoSuchElementException("Both nodes must be in the graph.");
}
}
/// Given two nodes in the graph, returns whether there is an edge from
/// the first node to the second node. If either node does not exist in
/// the graph, throws a NoSuchElementException.
bool edgeExists(var start, var end) {
if (dGraph.containsKey(start) && dGraph.containsKey(end)) {
return dGraph[start].contains(end);
} else {
throw new NoSuchElementException("Both nodes must be in the graph.");
}
}
/// Given a node in the graph, returns set of the edges leaving that
/// node as a set of endpoints. If the node doesn't exist, throws a
/// NoSuchElementException.
HashSet edgesFrom(var node) {
final HashSet arcs = dGraph[node];
if (arcs == null) {
throw new NoSuchElementException("Source node does not exist.");
} else {
return arcs;
}
}
/// Getter iterator returns an iterator to the directed graph's
/// keys to allow traversing the nodes in the graph.
Iterator get iterator => dGraph.keys.iterator;
/// Getter length returns the length of the directed graph.
int get length => dGraph.length;
}
```

The `NoSuchElementException()`

extends from the library's standard exception class. Let's take a look at an example.

### Example

Let's assume we are provided an edge list for the directed graph illustrated below:

One way to represent an edge list in Dart is as a List of Lists. Let's define the `graphlib`

library, import the `dart:collection`

library and add the necessary graphlib Dart files:

```
library graphlab;
import 'dart:collection';
part 'directed_graph.dart';
part 'graphlab_exception.dart';
part 'no_such_element_exception.dart';
void main() {
List<List> edgeList = [[1, 1],
[1, 3],
[3, 2],
[2, 1],
[3, 5],
[4, 1],
[4, 2],
[4, 12],
[4, 13],
[5, 6],
[5, 8],
[6, 7],
[6, 8],
[6, 10],
[7, 10],
[8, 9],
[8, 10],
[9, 5],
[9, 11],
[10, 9],
[10, 11],
[10, 14],
[11, 12],
[11, 14],
[12, 13],
[13, 11],
[13, 15],
[14, 13],
[15, 14]];
}
```

Now it's time to create a new `DirectedGraph`

object and populate it with our edge list.

```
// Create a new directed graph.
DirectedGraph graph = new DirectedGraph();
/// Populate the directed graph with the vertices from the edge list.
for (List list in edgeList) {
for (var element in list) {
graph.addNode(element);
}
}
/// Populate the directed graph with the directed edges.
for (List list in edgeList) {
graph.addEdge(list[0], list[1]);
}
```

Now we can explore our directed graph efficiently, For example, to print a list of the adjacency set representation of our graph:

```
/// Iterate over the nodes and print their incident edges.
graph.forEach((node) =>
print('Node $node has incident edge(s) ${graph.edgesFrom(node)}'));
/// Or, equivalently...
for (var node in graph) {
print('Node $node has incident edge(s) ${graph.edgesFrom(node)}');
}
```

Prints:

Node 1 has incident edge(s) {1, 3}

Node 2 has incident edge(s) {1}

Node 3 has incident edge(s) {2, 5}

Node 4 has incident edge(s) {1, 2, 12, 13}

Node 5 has incident edge(s) {8, 6}

Node 6 has incident edge(s) {8, 10, 7}

Node 7 has incident edge(s) {10}

Node 8 has incident edge(s) {9, 10}

Node 9 has incident edge(s) {11, 5}

Node 10 has incident edge(s) {9, 11, 14}

Node 11 has incident edge(s) {12, 14}

Node 12 has incident edge(s) {13}

Node 13 has incident edge(s) {11, 15}

Node 14 has incident edge(s) {13}

Node 15 has incident edge(s) {14}

In our next article, we will implement an iterative version of Kosaraju's algorithm using our directed graph data structure.

### Additional Information on Dart Collections

Google Developer Advocate Seth Ladd posed and then answered a question on StackOverflow [6] regarding different map implementations in Dart. He discusses the differences between Dart's HashMap, LinkedHashMap, and SplayTreeMap implementations. He also put together the following excellent video covering collections in Dart.

#### Works Cited

[1] The Dart Programming Language for Structured Web Apps

[2] Dart Collection Library API Reference

[3] Directed Graphs - Princeton University - Sedgewick & Wayne (pdf)

[4] Graph Implementation - University of Maryland (pdf)

[5] Keith Schwarz (Stanford U) - DirectedGraph.java

[6] StackOverflow: What are the differences between the different Map implementations in Dart?