20.
Graphs
Written by Vincent Ngo & Jonathan Sande
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs.
A graph is a data structure that captures relationships between objects. It’s made up of vertices connected by edges.
Circles in the graph below represent the vertices, and the edges are the lines that connect them.
Types of Graphs
Graphs come in a few different flavors. The following sections will describe their characteristics.
Weighted Graphs
In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. These weights let you choose the cheapest or shortest path between two vertices.
Directed Graphs
As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse because an edge may only permit traversal in one direction. The diagram below represents a directed graph.
Undirected Graphs
You can think of an undirected graph as a directed graph where all edges are bi-directional.
Common Operations
There are a number of common operations that any graph needs to implement. Before you get to those, though, you need the basic building blocks, that is, the vertices and edges.
Defining a Vertex
The image below shows a collection of vertices. They’re not yet a graph:
class Vertex<T> {
const Vertex({
required this.index,
required this.data,
});
final int index;
final T data;
@override
String toString() => data.toString();
}
Defining an Edge
To connect two vertices, there must be an edge between them. These are the lines in the image below:
class Edge<T> {
const Edge(
this.source,
this.destination, [
this.weight,
]);
final Vertex<T> source;
final Vertex<T> destination;
final double? weight;
}
Defining a Graph Interface
Now it’s time to define the common operations that the various flavors of graphs all share.
enum EdgeType { directed, undirected }
abstract class Graph<E> {
Iterable<Vertex<E>> get vertices;
Vertex<E> createVertex(E data);
void addEdge(
Vertex<E> source,
Vertex<E> destination, {
EdgeType edgeType,
double? weight,
});
List<Edge<E>> edges(Vertex<E> source);
double? weight(
Vertex<E> source,
Vertex<E> destination,
);
}
Adjacency List
The first graph implementation that you’ll learn uses an adjacency list. For every vertex in the graph, the graph stores a list of outgoing edges.
Implementation
An adjacency list is a graph, so you need to implement the Graph interface that you created earlier. Add the following code to graph.dart:
class AdjacencyList<E> implements Graph<E> {
final Map<Vertex<E>, List<Edge<E>>> _connections = {};
var _nextIndex = 0;
@override
Iterable<Vertex<E>> get vertices => _connections.keys;
// more to come ...
}
Creating a Vertex
Add the missing createVertex method to AdjacencyList:
@override
Vertex<E> createVertex(E data) {
// 1
final vertex = Vertex(
index: _nextIndex,
data: data,
);
_nextIndex++;
// 2
_connections[vertex] = [];
return vertex;
}
Adding an Edge
To connect two vertices, you need to add an edge. Recall that there are directed and undirected edges:
@override
void addEdge(
Vertex<E> source,
Vertex<E> destination, {
EdgeType edgeType = EdgeType.undirected,
double? weight,
}) {
// 1
_connections[source]?.add(
Edge(source, destination, weight),
);
// 2
if (edgeType == EdgeType.undirected) {
_connections[destination]?.add(
Edge(destination, source, weight),
);
}
}
Retrieving the Outgoing Edges From a Vertex
Continue your work on implementing Graph by adding the edges method to AdjacencyList:
@override
List<Edge<E>> edges(Vertex<E> source) {
return _connections[source] ?? [];
}
Retrieving the Weight of an Edge
Recall that the weight is the cost of going from one vertex to another. For example, if the cost of a ticket between Singapore and Tokyo is $500, the weight of this bidirectional edge is 500:
@override
double? weight(
Vertex<E> source,
Vertex<E> destination,
) {
final match = edges(source).where((edge) {
return edge.destination == destination;
});
if (match.isEmpty) return null;
return match.first.weight;
}
Making Adjacency List Printable
The required methods for AdjacencyList are complete now, but it would also be nice to be able to print a description of your graph. To do that, override toString like so:
@override
String toString() {
final result = StringBuffer();
// 1
_connections.forEach((vertex, edges) {
// 2
final destinations = edges.map((edge) {
return edge.destination;
}).join(', ');
// 3
result.writeln('$vertex --> $destinations');
});
return result.toString();
}
Singapore --> Hong Kong, Tokyo
Building a Network
For this example, you’ll go back to the diagram you saw earlier and construct a network of flights with the prices as weights:
import 'package:starter/graph.dart';
void main() {
final graph = AdjacencyList<String>();
final singapore = graph.createVertex('Singapore');
final tokyo = graph.createVertex('Tokyo');
final hongKong = graph.createVertex('Hong Kong');
final detroit = graph.createVertex('Detroit');
final sanFrancisco = graph.createVertex('San Francisco');
final washingtonDC = graph.createVertex('Washington DC');
final austinTexas = graph.createVertex('Austin Texas');
final seattle = graph.createVertex('Seattle');
graph.addEdge(singapore, hongKong, weight: 300);
graph.addEdge(singapore, tokyo, weight: 500);
graph.addEdge(hongKong, tokyo, weight: 250);
graph.addEdge(tokyo, detroit, weight: 450);
graph.addEdge(tokyo, washingtonDC, weight: 300);
graph.addEdge(hongKong, sanFrancisco, weight: 600);
graph.addEdge(detroit, austinTexas, weight: 50);
graph.addEdge(austinTexas, washingtonDC, weight: 292);
graph.addEdge(sanFrancisco, washingtonDC, weight: 337);
graph.addEdge(washingtonDC, seattle, weight: 277);
graph.addEdge(sanFrancisco, seattle, weight: 218);
graph.addEdge(austinTexas, sanFrancisco, weight: 297);
print(graph);
}
Singapore --> Hong Kong, Tokyo
Tokyo --> Singapore, Hong Kong, Detroit, Washington DC
Hong Kong --> Singapore, Tokyo, San Francisco
Detroit --> Tokyo, Austin Texas
San Francisco --> Hong Kong, Washington DC, Seattle, Austin Texas
Washington DC --> Tokyo, Austin Texas, San Francisco, Seattle
Austin Texas --> Detroit, Washington DC, San Francisco
Seattle --> Washington DC, San Francisco
Finding the Weight
You can also obtain other helpful information such as the cost of a flight from Singapore to Tokyo. This is the weight of the edge between those two vertices.
final cost = graph.weight(singapore, tokyo)?.toInt();
print('It costs \$$cost to fly from Singapore to Tokyo.');
// It costs $500 to fly from Singapore to Tokyo.
Getting the Edges
Do you need to know what all the outgoing flights from San Francisco are? For that, you just call edges.
print('San Francisco Outgoing Flights: ');
print('-------------------------------- ');
for (final edge in graph.edges(sanFrancisco)) {
print('${edge.source} to ${edge.destination}');
}
San Francisco Outgoing Flights:
--------------------------------
San Francisco to Hong Kong
San Francisco to Washington DC
San Francisco to Seattle
San Francisco to Austin Texas
Adjacency Matrix
An adjacency matrix uses a two-dimensional grid or table to implement the graph data structure. Each vertex has its own row and column in the table. The cells where rows and columns intersect hold the edge weights. If any particular cell is empty, that is, if the weight is null, then that means there is no edge between the row vertex and the column vertex.
Implementation
Add a new class to graph.dart called AdjacencyMatrix:
class AdjacencyMatrix<E> implements Graph<E> {
final List<Vertex<E>> _vertices = [];
final List<List<double?>?> _weights = [];
var _nextIndex = 0;
@override
Iterable<Vertex<E>> get vertices => _vertices;
// more to come ...
}
Creating a Vertex
For every new vertex that you create, you have to add an additional column and row to the matrix.
@override
Vertex<E> createVertex(E data) {
// 1
final vertex = Vertex(
index: _nextIndex,
data: data,
);
_nextIndex++;
_vertices.add(vertex);
// 2
for (var i = 0; i < _weights.length; i++) {
_weights[i]?.add(null);
}
// 3
final row = List<double?>.filled(
_vertices.length,
null,
growable: true,
);
_weights.add(row);
return vertex;
}
Adding Edges
Creating edges is as simple as adding weights to the matrix. There’s no Edge class to worry about.
@override
void addEdge(
Vertex<E> source,
Vertex<E> destination, {
EdgeType edgeType = EdgeType.undirected,
double? weight,
}) {
// 1
_weights[source.index]?[destination.index] = weight;
// 2
if (edgeType == EdgeType.undirected) {
_weights[destination.index]?[source.index] = weight;
}
}
Retrieving the Outgoing Edges From a Vertex
Add the edges method to AdjacencyMatrix:
@override
List<Edge<E>> edges(Vertex<E> source) {
List<Edge<E>> edges = [];
// 1
for (var column = 0; column < _weights.length; column++) {
final weight = _weights[source.index]?[column];
// 2
if (weight == null) continue;
// 3
final destination = _vertices[column];
edges.add(Edge(source, destination, weight));
}
return edges;
}
Retrieving the Weight of an Edge
It’s easy to get the weight of an edge. Simply look up the value in the adjacency matrix.
@override
double? weight(Vertex<E> source, Vertex<E> destination) {
return _weights[source.index]?[destination.index];
}
Making an Adjacency Matrix Printable
Finally, override toString so you can print out a readable description of your graph:
@override
String toString() {
final output = StringBuffer();
// 1
for (final vertex in _vertices) {
output.writeln('${vertex.index}: ${vertex.data}');
}
// 2
for (int i = 0; i < _weights.length; i++) {
for (int j = 0; j < _weights.length; j++) {
final value = (_weights[i]?[j] ?? '.').toString();
output.write(value.padRight(6));
}
output.writeln();
}
return output.toString();
}
Building a Network
You will reuse the same example from AdjacencyList:
final graph = AdjacencyList<String>();
final graph = AdjacencyMatrix<String>();
0: Singapore
1: Tokyo
2: Hong Kong
3: Detroit
4: San Francisco
5: Washington DC
6: Austin Texas
7: Seattle
. 500.0 300.0 . . . . .
500.0 . 250.0 450.0 . 300.0 . .
300.0 250.0 . . 600.0 . . .
. 450.0 . . . . 50.0 .
. . 600.0 . . 337.0 297.0 218.0
. 300.0 . . 337.0 . 292.0 277.0
. . . 50.0 297.0 292.0 . .
. . . . 218.0 277.0 . .
Graph Analysis
This chart compares the cost of different graph operations for adjacency lists and adjacency matrices. V represents the number of vertices, and E represents the number of edges.
Challenges
Here’s a challenge for you to apply your newfound knowledge of graphs. You can find the answer in the Challenge Solutions section as well as in the supplemental materials that accompany this book.
Challenge 1: Graph Your Friends
Megan has three friends: Sandra, Pablo and Edith. Pablo has friends as well: Ray, Luke, and a mutual friend of Megan’s. Edith is friends with Manda and Vicki. Manda is friends with Pablo and Megan. Create an adjacency list that represents this friendship graph. Which mutual friend do Pablo and Megan share?
Key Points
- You can represent real-world relationships through vertices and edges.
- Think of vertices as objects and edges as the relationships between the objects.
- Weighted graphs associate a number with every edge.
- Directed graphs have edges that traverse in one direction.
- Undirected graphs have edges that point both ways.
- An adjacency list is a graph that stores a list of outgoing edges for every vertex.
- An adjacency matrix uses a two-dimensional list to represent a graph.
- An adjacency list is generally good for sparse graphs, which have a low number of edges.
- An adjacency matrix is generally suitable for dense graphs, which have lots of edges.