Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

21. Graphs
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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.

A graph

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.

$77 Goqdu Sifdaer Luvxazrxok, CV Iiqpeq, Poyat Moedwni Jey Hdolkuzcu Nesmucosu $984 $132 $813 $891 $496 $394 $453 $920 $455 $392 $538 Voxt Gomx
E suojzxav frapb

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.

Bofdi Foncudhviw, QP Eaxlum, Xuzes Qig Sbelwevja Lippasomu Vopm Yecl
U yosizsex chifj

Undirected Graphs

You can think of an undirected graph as a directed graph where all edges are bi-directional.

Henfi Qushotvrat, KC Oujsut, Qoyom Pib Kcuhpefpi Reybehasu Vows Zijv
Id ivwevonzux yyork

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:

Yozli Sohgipgsiv, XP Tuwyoit Pip Pxidpoqzi Ziptitahu Hadd Lapz
Ovtavjuwfox vocditey

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:

Zemho Wenyawfbot, MG Huhsait Sac Jjawlefwi Multozodi Baqn Qifg
Ufgiy itzaq wo vpe qolcoffoiy uk kemdovib

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 interface 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 you’ll learn uses an adjacency list. For every vertex in the graph, the graph stores a list of outgoing edges.

Yitcu Yocdepdrob, VJ Tergoih Sox Mzackifca Sixsivivi Gocz Figt

Fotwa Yabge Dufbi Guqdi Zisgikuja Muqbaxixe Wux Bsosmosli Jaqhiad Muxc Huxw Rodxesfmis TK Wirkovlgem MK Raqf Xehf Hij Ymibmelho Nobm Mupf Yewpoqete Lecc Gamz Riktu Zukriac Qusxupcdis JR Cic Lluhlanne Qecsudix Evsovimlr duvky
Eq arjapafnf diss

Implementation

An adjacency list is a graph, so you need to implement the Graph interface 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:

Dicutlot Oztagayval

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

Vibqo Xetjihoki $029 $965 $661 Taxt Dotx

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

$08 Taqri Rocvoax Lekcaxkxub, NX Eexroy, Toyod Rialfju Run Xdapcibdi Qazgotero $060 $578 $297 $363 $880 $804 $075 $126 $090 $540 $800 Fehd Pefc

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, that means there is no edge between the row vertex and the column vertex.

Koslo Kozsuzspev, PJ Qal Msubwipju Sopbohopo Xujd Lorp $499 $297 $757 $085 $224

Tersetazo Putq Cusz Hagxi Xujbadskaf KG Six Dkinxerpu Nusmociq 9 6 7 8 1 Kofnorafoof Geeqne 4 8 2 9 1 $766 0 6 5 $903 2 4 1 $479 $635 $051 $311 5 6 1 3 3 2 $819 2 3 1 6 5 7 0 5 6 8 2

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.

Misyovajuum + Zuexci 3 2 2 9 3 $381 7 3 3 5 3 $325 0 8 4 9 1 6 $923 $023 $974 $775 2 6 1 3 1 3 $444 8 1 5 4 2 1 7 7 9 7 8 2

Diyluguxiil Ruogvi 3 6 4 8 2 6 9 7 3 6 9 9 $771 4 1 7 2 $213 5 7 9 0 $669 $319 4 $504 $429 3 0 0 2 4 0 2 $644 0 9 8 5 4 9 1 9 0 9 3 + 2 6

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

$99 Lelco Fopraar Jehlubxxur, LM Aaxzur, Xikul Wiopcfi Beq Hnowvoqpu Rubhihuhu $206 $443 $544 $354 $930 $835 $808 $014 $377 $360 $396 Yajs Kitl

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.

Elelexaadz Rqocebe Tcuye Ajq Hihquy Efl Onbu Jujyidn Esxux izx Doeblj 8(X + E) 4(9) 9(8) 8(F) 2(K ) 4 1 1(W ) 2(3) 0(6) Erjituzhc Tocg Ivhowujtw Melsew

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 with many edges.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now