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

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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 is made up of vertices connected by edges.

Circles in the graph below represent the vertices, and the edges are the lines that connect them.

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.

Take the airline industry as an example and think of a network with varying flight paths:

$50 Tokyo Detroit Washington, DC Austin, Texas Seattle San Francisco Singapore $300 $600 $300 $500 $450 $250 $292 $277 $337 $218 $297 Hong Kong

In this example, the vertices represent a state or country, while the edges represent a route from one place to another. The weight associated with each edge represents the airfare between those two points. Using this network, you can determine the cheapest flights from San Francisco to Singapore for all those budget-minded digital nomads out there!

Directed graphs

As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse, as an edge may only permit traversal in one direction. The diagram below represents a directed graph.

Lekye Dikwadvzad, ZD Iirgum, Dujub Seh Pnukginxa Begyorehu Coth Vaxz
A zuniwqoj zzapd

Undirected graphs

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

Lahxe Cavxorrxap, LD Iimtor, Jetaz Gaf Knetparba Duzmunora Nisn Wuty
Od ussiwomtec ccetx

Common operations

Let’s establish a protocol for graphs.

public enum EdgeType {

  case directed
  case undirected
}

public protocol Graph {

  associatedtype Element

  func createVertex(data: Element) -> Vertex<Element>
  func addDirectedEdge(from source: Vertex<Element>,
                       to destination: Vertex<Element>,
                       weight: Double?)
  func addUndirectedEdge(between source: Vertex<Element>,
                         and destination: Vertex<Element>,
                         weight: Double?)
  func add(_ edge: EdgeType, from source: Vertex<Element>,
                             to destination: Vertex<Element>,
                             weight: Double?)
  func edges(from source: Vertex<Element>) -> [Edge<Element>]
  func weight(from source: Vertex<Element>,
              to destination: Vertex<Element>) -> Double?
}

Defining a vertex

Tokyo Washington, DC Detroit San Francisco Singapore Hong Kong
A collection of vertices — not yet a graph

public struct Vertex<T> {

  public let index: Int
  public let data: T
}
extension Vertex: Hashable where T: Hashable {}
extension Vertex: Equatable where T: Equatable {}
extension Vertex: CustomStringConvertible {

  public var description: String {
    "\(index): \(data)"
  }
}

Defining an edge

To connect two vertices, there must be an edge between them!

Qurfa Jobqoqfpet, WR Rojmauj Sar Cgafjozjo Qillejore Sezf Tewx
Acroc irnus ro jma pikqosnaet ub guhkufas

public struct Edge<T> {

  public let source: Vertex<T>
  public let destination: Vertex<T>
  public let weight: Double?
}

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.

Wopqo Vukbajwqug, RH Tozzaeh Rix Gdogfande Purqamoxe Mens Peqs

Kokbi Cavso Nukzi Vobne Xokjapozo Terdilude Dec Ycezrafra Hammaez Zuhxaog Daxjajbgij WP Pomsaygmah VS Rutr Majn Mah Djuzyijce Rovp Xabq Hohmonuni Pevb Ginn Kazdu Qizceiy Wefwezbruj HY Gej Kviwmezga Xijqipun Itvulikgx boyss

Implementation

Create a new file named AdjacencyList.swift and add the following:

public class AdjacencyList<T: Hashable>: Graph {

  private var adjacencies: [Vertex<T>: [Edge<T>]] = [:]

  public init() {}

  // more to come ...
}

Creating a vertex

Add the following method to AdjacencyList:

public func createVertex(data: T) -> Vertex<T> {
  let vertex = Vertex(index: adjacencies.count, data: data)
  adjacencies[vertex] = []
  return vertex
}

Creating a directed edge

Recall that there are directed and undirected graphs.

Cihuzkif Ifnomaqxev

public func addDirectedEdge(from source: Vertex<T>,
                            to destination: Vertex<T>,
                            weight: Double?) {
  let edge = Edge(source: source,
                  destination: destination,
                  weight: weight)
  adjacencies[source]?.append(edge)
}

Creating an undirected edge

You just created a method to add a directed edge between two vertices. How would you create an undirected edge between two vertices?

extension Graph {

  public func addUndirectedEdge(between source: Vertex<Element>,
                                and destination: Vertex<Element>,
                                weight: Double?) {
    addDirectedEdge(from: source, to: destination, weight: weight)
    addDirectedEdge(from: destination, to: source, weight: weight)
  }
}
public func add(_ edge: EdgeType, from source: Vertex<Element>,
                                  to destination: Vertex<Element>,
                                  weight: Double?) {
  switch edge {
  case .directed:
    addDirectedEdge(from: source, to: destination, weight: weight)
  case .undirected:
    addUndirectedEdge(between: source, and: destination, weight: weight)
  }
}

Retrieving the outgoing edges from a vertex

Back in AdjacencyList.swift, continue your work on conforming to Graph by adding the following method:

public func edges(from source: Vertex<T>) -> [Edge<T>] {
  adjacencies[source] ?? []
}

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Tetba Jomqigomo $205 $404 $628 Hipx Qajf

public func weight(from source: Vertex<T>,
                   to destination: Vertex<T>) -> Double? {
  edges(from: source)
     .first { $0.destination == destination }?
     .weight
}

Visualizing the adjacency list

Add the following extension to AdjacencyList so that you can print a nice description of your graph:

extension AdjacencyList: CustomStringConvertible {

  public var description: String {
    var result = ""
    for (vertex, edges) in adjacencies { // 1
      var edgeString = ""
      for (index, edge) in edges.enumerated() { // 2
        if index != edges.count - 1 {
          edgeString.append("\(edge.destination), ")
        } else {
          edgeString.append("\(edge.destination)")
        }
      }
      result.append("\(vertex) ---> [ \(edgeString) ]\n") // 3
    }
    return result
  }
}

Building a network

Let’s go back to the flights example and construct a network of flights with the prices as weights.

$70 Napje Nossuad Yobsujmjej, SZ Iilhiq, Kalag Xuedlje Ner Mqonlorzi Falhoweme $392 $552 $398 $274 $047 $932 $132 $379 $724 $002 $269 Porh Winh

let graph = AdjacencyList<String>()

let singapore = graph.createVertex(data: "Singapore")
let tokyo = graph.createVertex(data: "Tokyo")
let hongKong = graph.createVertex(data: "Hong Kong")
let detroit = graph.createVertex(data: "Detroit")
let sanFrancisco = graph.createVertex(data: "San Francisco")
let washingtonDC = graph.createVertex(data: "Washington DC")
let austinTexas = graph.createVertex(data: "Austin Texas")
let seattle = graph.createVertex(data: "Seattle")

graph.add(.undirected, from: singapore, to: hongKong, weight: 300)
graph.add(.undirected, from: singapore, to: tokyo, weight: 500)
graph.add(.undirected, from: hongKong, to: tokyo, weight: 250)
graph.add(.undirected, from: tokyo, to: detroit, weight: 450)
graph.add(.undirected, from: tokyo, to: washingtonDC, weight: 300)
graph.add(.undirected, from: hongKong, to: sanFrancisco, weight: 600)
graph.add(.undirected, from: detroit, to: austinTexas, weight: 50)
graph.add(.undirected, from: austinTexas, to: washingtonDC, weight: 292)
graph.add(.undirected, from: sanFrancisco, to: washingtonDC, weight: 337)
graph.add(.undirected, from: washingtonDC, to: seattle, weight: 277)
graph.add(.undirected, from: sanFrancisco, to: seattle, weight: 218)
graph.add(.undirected, from: austinTexas, to: sanFrancisco, weight: 297)

print(graph)
2: Hong Kong ---> [ 0: Singapore, 1: Tokyo, 4: San Francisco ]
4: San Francisco ---> [ 2: Hong Kong, 5: Washington DC, 7: Seattle, 6: Austin Texas ]
5: Washington DC ---> [ 1: Tokyo, 6: Austin Texas, 4: San Francisco, 7: Seattle ]
6: Austin Texas ---> [ 3: Detroit, 5: Washington DC, 4: San Francisco ]
7: Seattle ---> [ 5: Washington DC, 4: San Francisco ]
0: Singapore ---> [ 2: Hong Kong, 1: Tokyo ]
1: Tokyo ---> [ 0: Singapore, 2: Hong Kong, 3: Detroit, 5: Washington DC ]
3: Detroit ---> [ 1: Tokyo, 6: Austin Texas ]
graph.weight(from: singapore, to: tokyo)
print("San Francisco Outgoing Flights:")
print("--------------------------------")
for edge in graph.edges(from: sanFrancisco) {
  print("from: \(edge.source) to: \(edge.destination)")
}

Adjacency matrix

An adjacency matrix uses a square matrix to represent a graph. This matrix is a two-dimensional array wherein the value of matrix[row][column] is the weight of the edge between the vertices at row and column.

Gipxa Wekyajznuw, JG Poj Vpasfodgi Dodvuzizu Kobd Hoqw $845 $073 $810 $960 $347

Fixqecafo Vafd Mirq Luqtu Dochudytuk QY Wed Klewwapse Tacrewak 0 0 9 9 5 Wiwecvb Miwj 1 1 3 2 8 $799 8 2 3 $373 1 4 0 $885 $257 $855 $698 9 1 8 8 5 9 $141 9 5 6 1 8 0 5 6 0 9 8

Implementation

Create a new file named AdjacencyMatrix.swift and add the following to it:

public class AdjacencyMatrix<T>: Graph {

  private var vertices: [Vertex<T>] = []
  private var weights: [[Double?]] = []

  public init() {}

  // more to come ...
}

Creating a Vertex

Add the following method to AdjacencyMatrix:

public func createVertex(data: T) -> Vertex<T> {
  let vertex = Vertex(index: vertices.count, data: data)
  vertices.append(vertex) // 1
  for i in 0..<weights.count { // 2
    weights[i].append(nil)
  }
  let row = [Double?](repeating: nil, count: vertices.count) // 3
  weights.append(row)
  return vertex
}
Vupafbv + Molg 5 4 3 4 2 $432 4 5 3 7 0 $870 9 8 7 9 3 2 $266 $705 $217 $454 4 9 7 8 8 5 $455 8 6 7 8 3 2 5 5 8 5 9 3

Foyenxp Zijg 8 6 7 9 1 3 5 7 0 5 2 4 $509 5 4 5 7 $016 1 1 3 3 $553 $585 0 $172 $170 0 3 2 8 6 5 3 $806 4 3 8 5 9 1 1 4 2 5 1 + 3 3

Creating edges

Creating edges is as simple as filling in the matrix. Add the following method:

public func addDirectedEdge(from source: Vertex<T>,
                            to destination: Vertex<T>, weight: Double?) {
  weights[source.index][destination.index] = weight
}

Retrieving the outgoing edges from a vertex

Add the following method:

public func edges(from source: Vertex<T>) -> [Edge<T>] {
  var edges: [Edge<T>] = []
  for column in 0..<weights.count {
    if let weight = weights[source.index][column] {
      edges.append(Edge(source: source,
                        destination: vertices[column],
                        weight: weight))
    }
  }
  return edges
}

Retrieving the weight of an edge

It is very easy to get the weight of an edge; simply look up the value in the adjacency matrix. Add this method:

public func weight(from source: Vertex<T>,
                   to destination: Vertex<T>) -> Double? {
  weights[source.index][destination.index]
}

Visualize an adjacency matrix

Finally, add the following extension so you can print out a nice, readable description of your graph:

extension AdjacencyMatrix: CustomStringConvertible {

  public var description: String {
    // 1
    let verticesDescription = vertices.map { "\($0)" }
                                      .joined(separator: "\n")
    // 2
    var grid: [String] = []
    for i in 0..<weights.count {
      var row = ""
      for j in 0..<weights.count {
        if let value = weights[i][j] {
          row += "\(value)\t"
        } else {
          row += "ø\t\t"
        }
      }
      grid.append(row)
    }
    let edgesDescription = grid.joined(separator: "\n")
    // 3
    return "\(verticesDescription)\n\n\(edgesDescription)"
  }
}

Building a network

You will reuse the same example from AdjacencyList:

$75 Sesbu Vaghaaj Socnomvtaz, WR Eivsey, Muboq Laehvve Neg Wyewcifxe Fophabari $309 $782 $289 $748 $697 $558 $988 $492 $041 $086 $936 Sutg Xuqb

let graph = AdjacencyList<String>()
let 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 ø   ø   
San Francisco Outgoing Flights:
--------------------------------
from: 4: San Francisco to: 2: Hong Kong
from: 4: San Francisco to: 5: Washington DC
from: 4: San Francisco to: 6: Austin Texas
from: 4: San Francisco to: 7: Seattle

Graph analysis

This chart summarizes the cost of different operations for graphs represented by adjacency lists versus adjacency matrices.

Ihomenuuvd Fhaqara Vyuqo Uhy Temtac Uvq Esbi Mafwecr Ofmij ahs Buoybp 7(Y + E) 8(3) 9(9) 3(W) 1(Z ) 9 9 3(D ) 7(7) 3(0) Oqrojabvm Winj Iqturexwg Xuhwex

Key points

  • You can represent real-world relationships through vertices and edges.
  • Think of vertices as objects and edges as the relationship between the objects.
  • Weighted graphs associate a weight with every edge.
  • Directed graphs have edges that traverse in one direction.
  • Undirected graphs have edges that point both ways.
  • Adjacency list stores a list of outgoing edges for every vertex.
  • Adjacency matrix uses a square matrix to represent a graph.
  • Adjacency list is generally good for sparse graphs when your graph has the least amount of edges.
  • Adjacency matrix is generally suitable for dense graphs when your graph has 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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

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 raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.