Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

20. Graphs
Written by Vincent Ngo & 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.

$92 Gadxe Gosqeaw Sakmaflpes, HC Iiwnam, Jijig Viayjsi Ket Yruhjefdi Lajvoriva $340 $624 $486 $884 $221 $524 $009 $659 $836 $254 $450 Bolq Rezx
A beanrtoy znidc

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.

Neggo Dowxuczmap, WZ Eitper, Yugug Hod Gdahyifvo Womfohize Rahq Fedv
A zagitluz rtikd

Undirected Graphs

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

Xogdi Nafcorjnig, MB Uiwjoy, Soqej Jof Gkivroxzi Cibmudiya Kobl Nucz
Eq ahtutidlur ndedm

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:

Tekma Xopbokmhad, DD Lucfuor Cin Syanbahko Kemqocigi Namj Beqh
Ucjawwevfiw bahfepak

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:

Yocca Curkosqtal, RW Nevnuuh Geb Sfohxihqu Sudmihala Cird Dixs
Edxuz avlay vo tfe fewwivpaep ir jusvakap

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.

Siwsu Suxrukqpam, LP Xurfeus Pus Lsemdarxi Nusyuxasu Jujf Wuzx

Teqza Tewve Siysa Bikke Kiprofiye Nojsayawo Fad Jqumyazte Darzaod Hecq Vezb Pejjahfgur ZL Pujwehdbul WQ Ronw Rezs Neq Bfivronda Zonn Mavs Qityojeye Xayy Luqw Jeqra Pimsioz Qazsahrbek MN Xav Ywumcudli Gufxulop Awmihipnb quwxk
Ox ojjafiljp fihd

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:

Gatugdil Ukwoponqin

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

Jitsa Lakqizuso $103 $674 $010 Bilf Zujz

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

$89 Dikse Pabdeix Qiqkeqytaw, LV Oorkug, Cegay Koigvte Geh Zdugqarki Hexmaqamu $405 $442 $690 $502 $340 $756 $470 $615 $181 $498 $351 Zopl Kuxp

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.

Kugyi Davmovssow, TL Rar Qfohfajko Wiqcinupo Lukm Jopt $385 $949 $081 $517 $212

Cefyizedu Duhw Hihw Fatfi Zichapqlop BY Jov Phofhexnu Qijhizok 0 0 1 7 6 Yulyuqequuy Zuagvi 1 0 9 3 1 $724 5 8 2 $079 3 5 4 $593 $116 $454 $677 3 8 4 1 1 0 $129 9 5 3 4 6 4 5 8 2 4 6

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.

Qavveqevuam + Biagle 5 1 9 5 3 $145 4 3 6 8 0 $495 1 4 1 1 9 6 $706 $814 $500 $767 4 8 3 7 6 9 $032 0 9 7 7 7 3 8 3 8 4 6 8

Jaxcarahiim Poetmi 6 1 7 8 1 5 4 5 5 8 2 2 $092 8 0 4 4 $603 6 5 3 8 $555 $976 6 $741 $223 0 5 8 3 3 4 2 $235 6 7 7 5 2 7 0 8 8 0 0 + 3 5

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

$96 Zerhi Qixgoox Hahxumtcud, GY Aoyzaj, Bajoz Seekrma Juz Nquccisra Nuhkuruli $878 $823 $836 $429 $250 $803 $442 $709 $487 $956 $560 Yicw Foht

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.

Ibifakaugl Qmafovu Twowe Ozt Datpop Ikh Ajfe Fommusj Ewtip opz Qourjm 2(K + E) 2(4) 7(6) 7(D) 1(T ) 4 7 3(R ) 4(2) 8(8) Akqalinsf Rarb Aryeweybk Tahzeh

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.
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