scribeGriff Studios

Books • Algorithms • Dart • HTML5 • CSS3

To content | To menu | To search

Collections in Dart: The Directed Graph

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 V2 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:

directed_graph.png

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?

submit to reddit
Google+
Richard Griffith

Author: Richard Griffith

Keep in touch with the latest updates. Subscribe to the RSS Feed for this category.

Comments (0)

Be the first to comment on this article

Add a comment This post's comments feed

no attachment



You might also like

angular-and-dart-iconj.jpg

Today's @Directive: Get Up to Speed Using Angular with Dart

Although I spend most of my time working with Dart using Polymer, it's hard not to find the announcement of AngularDart a compelling reason to take it out for a spin. And I confess, the more I use Angular with Dart, the more I'm convinced it is going to be a major component of my Dart toolbox for the foreseeable future. I had come across Jesus Rodriguez's introduction to the model driven framework with his appropriately named blog post Why Does Angular.js Rock?. In this article, we look at the Dart equivalents of the examples Jesus presented.

Continue reading

future-word-cloud-dart.png

Iterables, Futures, and Future.wait() in Dart

Several days ago while working with Dart, I was coding up a problem that required that I iterate over a function that returns its value represented as a Future. The variables that I needed to pass to this function were read from an external file and stored in a List using a Stream. To evaluate the function for each element in the List, I was tempted to use a simple forEach() to pass the elements to the function returning a Future. But I was soon going to discover a much better way for dealing with a scenario such as this.

Continue reading