Swift Algorithm Club: Graphs with Adjacency List

Graphable Protocol

Now that you have defined your vertex and edge. You have one more thing you have to do, which is to create an interface to build a graph.

To do this, create a new file called Graphable.swift under Sources group and add the following code:

protocol Graphable {
  associatedtype Element: Hashable // 1
  var description: CustomStringConvertible { get } // 2
  
  func createVertex(data: Element) -> Vertex<Element> // 3
  func add(_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) // 4
  func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double? // 5
  func edges(from source: Vertex<Element>) -> [Edge<Element>]? // 6
}

Going over the protocol:

1. The protocol requires an associatedType called Element. This allows the protocol to be generic, to hold any type.
2. The description property lets you define custom behavior to print out the contents of a graph. This can help with debugging!
3. createVertex(data:) provides a utility method to create a vertex.
4. add(_:from:to:weight:) provides a utility to add an edge between two vertices. You can specify the weight as well as whether an edge is directed or undirected.
5. weight(from:to:) provides a utility to get the weight of an edge between two vertices.
6. edges(from:) provides a utility to retrieve all the edges that source vertex connects to.

On to implementing the adjacency list!

Adjacency List

First create a new file called AdjacencyList.swift within the Sources group.

Add the following code:

open class AdjacencyList<T: Hashable> {
  public var adjacencyDict : [Vertex<T>: [Edge<T>]] = [:]
  public init() {}
}

You will use adjacencyDict to store your graph. adjacencyDict is a dictionary. The key is a Vertex and the value is an array of edges.

Next add the following after the class declaration:

extension AdjacencyList: Graphable {
  public typealias Element = T
}

Since the AdjacencyList is also generic, the associatedType is set to T

Creating Vertices

To create a vertex add the following code within the extension right after the Element generic property:

public func createVertex(data: Element) -> Vertex<Element> {
  let vertex = Vertex(data: data)
  
  if adjacencyDict[vertex] == nil {
    adjacencyDict[vertex] = []
  }

  return vertex
}

Based on the data passed in you create a Vertex. You check to see if the vertex already exists. If it doesn’t you initialize an array of edges and return the vertex.

Creating Edges

Recall that there are graphs that are directed and graphs that are undirected.

First add the following helper method after init():

fileprivate func addDirectedEdge(from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) {
  let edge = Edge(source: source, destination: destination, weight: weight) // 1
  adjacencyDict[source]?.append(edge) // 2
}

This method takes two vertices, a source and destination with a weight. Let’s go over the code:

1. Creates an edge.
2. Retrieves the array of edges affiliated with source vertex and append the edge to the array.

Now add the following method right after addDirectedEdge(from:to:weight:):

fileprivate func addUndirectedEdge(vertices: (Vertex<Element>, Vertex<Element>), weight: Double?) {
  let (source, destination) = vertices
  addDirectedEdge(from: source, to: destination, weight: weight)
  addDirectedEdge(from: destination, to: source, weight: weight)
}

In an undirected graph, you can treat it as a directed graph that goes both ways. You call
addDirectedEdge(from:to:weight:) twice, but with the source and destination vertices swapped.

Now you can make use of the two helper methods! Add the following code in the AdjacencyList extension, right after createVertex(data:):

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

add(_:from:to:weight:) checks to see if the type is directed or undirected and creates the correct edge.

Retrieving information

You will now finish up the conformance to Graphable by providing ways to retrieve the weight.

How much is the flight from Singapore to Hong Kong?

Add the following code below the previous method:

public func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double? {
  guard let edges = adjacencyDict[source] else { // 1
    return nil
  }
  
  for edge in edges { // 2
    if edge.destination == destination { // 3
      return edge.weight
    }
  }
  
  return nil // 4
}

Let’s go over how to get the weight:

1. Retrieve all the edges from the source vertex. If no edges, return nil.
2. Loop through each edge.
3. Check to see if there is an edge that leads to the destination vertex.
4. Return nil if no weight found.

Next add the following code below:

public func edges(from source: Vertex<Element>) -> [Edge<Element>]? {
  return adjacencyDict[source]
}

edges(from:) is straightforward. You access the dictionary based on a given vertex and return the array of edges.

The final piece to the puzzle is visualizing the adjacency list. You must create the final method to fulfill the Graphable protocol.

Visualizing the adjacency list

Add the following code below:

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

The description property goes through every key-value pair in the dictionary. It prints out the vertex, and all the vertices it’s connected to by an edge.

The adjacency list is finally complete! You must be all excited to use your first graphing data structure!

Testing out the Adjacency List

Now it’s time to go back to the flights pricing network example.

Within the root Playground, add the following code:

import UIKit
import XCPlayground

let adjacencyList = AdjacencyList<String>()

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

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

adjacencyList.description

The code above creates the flight network pricing graph using the adjacency list. Swift Playgrounds should show the following output:

Isn’t this cool? This is a visual description of an adjacency list! It shows you all the flights available from Austin Texas, all the flights from Toyko, and etc!