36. Graphs

Written by Vincent Ngo

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.

In the graph below, the vertices are represented by circles, 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. This lets 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:

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.

You can tell a lot from this diagram:

• There is a flight from Hong Kong to Tokyo.
• There is no direct flight from San Francisco to Tokyo.
• You can buy a roundtrip ticket between Singapore and Tokyo.
• There is no way to get from Tokyo to San Francisco.

Undirected graphs

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

In an undirected graph:

• Two connected vertices have edges going back and forth.
• The weight of an edge applies to both directions.

Common operations

Let’s establish a protocol for graphs.

Open up the starter project for this chapter. Create a new file named Graph.swift and add the following inside the file:

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?
}

This protocol describes the common operations for a graph:

• createVertex(data:): Creates a vertex and adds it to the graph.
• addDirectedEdge(from:to:weight:): Adds a directed edge between two vertices.
• addUndirectedEdge(between:and:weight:): Adds an undirected (or bi-directional) edge between two vertices.
• add(from:to:): Uses EdgeType to add either a directed or undirected edge between two vertices.
• edges(from:): Returns a list of outgoing edges from a specific vertex.
• weight(from:to:): Returns the weight of the edge between two vertices.

In the following sections, you’ll implement this protocol in two ways:

• Using an adjacency list.
• Using an adjacency matrix.

Before you can do that, you must first build types to represent vertices and edges.

Defining a vertex

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

public struct Vertex<T> {
  
  public let index: Int
  public let data: T
}

Here, you’ve defined a generic Vertex struct. A vertex has a unique index within its graph and holds a piece of data.

You’ll use Vertex as the key type for a dictionary, so you need to conform to Hashable. Add the following extension to implement the requirements for Hashable:

extension Vertex: Hashable where T: Hashable {}
extension Vertex: Equatable where T: Equatable {}

The Hashable protocol inherits from Equatable, so you must also satisfy this protocol’s requirement. The compiler can synthesize conformance to both protocols, which is why the extensions above are empty.

Finally, you want to provide a custom string representation of Vertex. Add the following right after:

extension Vertex: CustomStringConvertible {

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

Defining an edge

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

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

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

An Edge connects two vertices and has an optional weight. Simple, isn’t it?

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.

Take as an example the following network:

The adjacency list below describes the network of flights depicted above:

There is a lot you can learn from this adjacency list:

1. Singapore’s vertex has two outgoing edges. There is a flight from Singapore to Tokyo and Hong Kong.
2. Detroit has the smallest number of outgoing traffic.
3. Tokyo is the busiest airport, with the most outgoing flights.

In the next section you will create an adjacency list by storing a dictionary of arrays. Each key in the dictionary is a vertex, and, in every vertex, the dictionary holds a corresponding array of edges.

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

Here, you’ve defined an AdjacencyList that uses a dictionary to store the edges. Notice that the generic parameter T must be Hashable, because it is used as a key in a dictionary.

You’ve already adopted the Graph protocol but still need to implement its requirements. That’s what you’ll do in the following sections.

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
}

Here, you create a new vertex and return it. In the adjacency list, you store an empty array of edges for this new vertex.

Creating a directed edge

Recall that there are directed and undirected graphs.

Start by implementing the addDirectedEdge requirement. Add the following method:

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)
}

This method creates a new edge and stores it in the adjacency list.

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?

Remember that an undirected graph can be viewed as a bidirectional graph. Every edge in an undirected graph can be traversed in both directions. This is why you’ll implement addUndirectedEdge on top of addDirectedEdge. Because this implementation is reusable, you’ll add it as a protocol extension on Graph.

In Graph.swift, add the following extension:

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)
  }
}

Adding an undirected edge is the same as adding two directed edges.

Now that you’ve implemented both addDirectedEdge and addUndirectedEdge, you can implement add by delegating to one of these methods. In the same protocol extension, add:

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)
  }
}

The add method is a convenient helper method that creates either a directed or undirected edge. This is where protocols can become very powerful!

Anyone that adopts the Graph protocol only needs to implement addDirectedEdge in order to get addUndirectedEdge and add for free!

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] ?? []
}

This is a straightforward implementation: You either return the stored edges or an empty array if the source vertex is unknown.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Add the following right after edges(from:):

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

Here, you find the first edge from source to destination; if there is one, you return its 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
  }
}

Here’s what’s going on in the code above:

1. You loop through every key-value pair in adjacencies.
2. For every vertex, you loop through all its outgoing edges and add an appropriate string to the output.
3. Finally, for every vertex you print both the vertex itself and its outgoing edges.

You have finally completed your first graph! Let’s now try it out by building a network.

Building a network

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

Within the main playground page, add the following code:

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)

You should get the following output in your playground:

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 ]

Pretty cool, huh? This shows a visual description of an adjacency list. You can clearly see all the outbound flights from any place!

You can also obtain other useful information such as:

• How much is a flight from Singapore to Tokyo?

graph.weight(from: singapore, to: tokyo)

• What are all the outgoing flights from San Francisco?

print("San Francisco Outgoing Flights:")
print("--------------------------------")
for edge in graph.edges(from: sanFrancisco) {
  print("from: \(edge.source) to: \(edge.destination)")
}

You have just created a graph using an adjacency list, wherein you used a dictionary to store the outgoing edges for every vertex. Let’s take a look at a different approach to how to store vertices and edges.

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.

Below is an example of a directed graph that depicts a flight network traveling to different places. The weight represents the cost of the airfare.

The following adjacency matrix describes the network for the flights depicted above.

Edges that don’t exist have a weight of 0.

Compared to an adjacency list, this matrix is a little harder to read. Using the array of vertices on the left, you can learn a lot from the matrix. For example:

• [0][1] is 300, so there is a flight from Singapore to Hong Kong for $300.
• [2][1] is 0, so there is no flight from Tokyo to Hong Kong.
• [1][2] is 250, so there is a flight from Hong Kong to Tokyo for $250.
• [2][2] is 0, so there is no flight from Tokyo to Tokyo!

Note: There is a pink line in the middle of the matrix. When the row and column are equal, this represents an edge between a vertex and itself, which is not allowed.

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

Here, you’ve defined an AdjacencyMatrix that contains an array of vertices and an adjacency matrix to keep track of the edges and their weights.

Just as before, you’ve already declared conformance to Graph but still need to implement the requirements.

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
}

To create a vertex in an adjacency matrix, you:

1. Add a new vertex to the array.

2. Append a nil weight to every row in the matrix, as none of the current vertices have an edge to the new vertex.

3. Add a new row to the matrix. This row holds the outgoing edges for the new vertex.

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
}

Remember that addUndirectedEdge and add have a default implementation in the protocol extension, so this is all you need to do!

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
}

To retrieve the outgoing edges for a vertex, you search the row for this vertex in the matrix for weights that are not nil.

Every non-nil weight corresponds with an outgoing edge. The destination is the vertex that corresponds with the column in which the weight was found.

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)"
  }
}

Here are the steps:

1. You first create a list of the vertices.
2. Then you build up a grid of weights, row by row.
3. Finally, you join both descriptions together and return them.

Building a network

You will reuse the same example from AdjacencyList:

Go to the main playground page and replace:

let graph = AdjacencyList<String>()

With:

let graph = AdjacencyMatrix<String>()

AdjacencyMatrix and AdjacencyList conform to the same protocol Graph, so the rest of the code stays the same.

You should get the following output in your playground:

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

In terms of visual beauty, an adjacency list is a lot easier to follow and trace than an adjacency matrix. Let’s analyze the common operations of these two approaches and see how they perform.

Graph analysis

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

V represents vertices, and E represents edges.

An adjacency list takes less storage space than an adjacency matrix. An adjacency list simply stores the number of vertices and edges needed. As for an adjacency matrix, recall that the number of rows and columns is equal to the number of vertices. This explains the quadratic space complexity of O(V²).

Adding a vertex is efficient in an adjacency list: Simply create a vertex and set its key-value pair in the dictionary. It is amortized as O(1). When adding a vertex to an adjacency matrix, you are required to add a column to every row, and create a new row for the new vertex. This is at least O(V) and if you choose to represent your matrix with a contiguous block of memory, can be O(V²).

Adding an edge is efficient in both data structures, as they are both constant time. The adjacency list appends to the array of outgoing edges. The adjacency matrix simply sets the value in the two-dimensional array.

Adjacency list loses out when trying to find a particular edge or weight. To find an edge in an adjacency list, you must obtain the list of outgoing edges and loop through every edge to find a matching destination. This happens in O(V) time. With an adjacency matrix, finding an edge or weight is a constant time access to retrieve the value from the two-dimensional array.

Which data structure should you choose to construct your graph?

If there are few edges in your graph, it is considered a sparse graph, and an adjacency list would be a good fit. An adjacency matrix would be a bad choice for a sparse graph, because a lot of memory will be wasted since there aren’t many edges.

If your graph has lots of edges, it’s considered a dense graph, and an adjacency matrix would be a better fit as you’d be able to access your weights and edges far more quickly.

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 good for dense graphs, when your graph has lots of edges.