37. Graphs Challenges

Written by Vincent Ngo

Challenge 1: Count the number of paths

Write a method to count the number of paths between two vertices in a directed graph. The example graph below has 5 paths from A to E:

Challenge 2: Graph your friends

Vincent has three friends, Chesley, Ruiz and Patrick. Ruiz has friends as well: Ray, Sun, and a mutual friend of Vincent’s. Patrick is friends with Cole and Kerry. Cole is friends with Ruiz and Vincent. Create an adjacency list that represents this friendship graph. Which mutual friend do Ruiz and Vincent share?

Solutions

Solution to Challenge 1

The goal is to write a function that finds the number of paths between two vertices in a graph. One solution is to perform a depth-first traversal and keep track of the visited vertices.

extension Graph where Element: Hashable {
  public func numberOfPaths(from source: Vertex<Element>,
                            to destination: Vertex<Element>) -> Int {
    var numberOfPaths = 0 // 1
    var visited: Set<Vertex<Element>> = [] // 2
    paths(from: source,
          to: destination,
          visited: &visited,
          pathCount: &numberOfPaths) // 3
    return numberOfPaths
  }

}

Here you do the following:

1. numberOfPaths keeps track of the number of paths found between the source and destination.
2. visited is a Set that keeps track of all the vertices visited.
3. paths is a recursive helper function that takes in four parameters. The first two parameters are the source, and destination vertex. The last two parameters, visited tracks the vertices visited, and numberOfPaths tracks the number of paths found. The last two parameters is modified within paths.

Add the following right after the numberOfPaths function:

func paths(from source: Vertex<Element>,
           to destination: Vertex<Element>,
           visited: inout Set<Vertex<Element>>,
           pathCount: inout Int) {
  visited.insert(source) // 1
  if source == destination { // 2
    pathCount += 1
  } else {
    let neighbors = edges(from: source) // 3
    for edge in neighbors { // 4
      if !visited.contains(edge.destination) {
        paths(from: edge.destination,
              to: destination,
              visited: &visited,
              pathCount: &pathCount)
      }
    }
  }
  // 5
  visited.remove(source)
}

To get the paths from the source to destination:

1. Initiate the algorithm by marking the source vertex as visited.
2. Check to see if the source is the destination. If it is, you have found a path, increment the count by one.
3. If it is not, get all the edges adjacent to the source vertex.
4. For every edge, if it has not been visited before, recursively traverse the neighboring vertices to find a path to the destination vertex.
5. Remove the source vertex from the visited set, so you can continue to find other paths to that node.

You are doing a depth-first graph traversal. You recursively dive down one path till you reach the destination, and back-track by popping off the stack. The time-complexity is O(V + E).

Solution to Challenge 2

This solution of just using the AdjacencyList API you built in the last chapter. You can use any non-nil weight, but a good default is 1.

let graph = AdjacencyList<String>()

let vincent = graph.createVertex(data: "vincent")
let chesley = graph.createVertex(data: "chesley")
let ruiz = graph.createVertex(data: "ruiz")
let patrick = graph.createVertex(data: "patrick")
let ray = graph.createVertex(data: "ray")
let sun = graph.createVertex(data: "sun")
let cole = graph.createVertex(data: "cole")
let kerry = graph.createVertex(data: "kerry")

graph.add(.undirected, from: vincent, to: chesley, weight: 1)
graph.add(.undirected, from: vincent, to: ruiz, weight: 1)
graph.add(.undirected, from: vincent, to: patrick, weight: 1)
graph.add(.undirected, from: ruiz, to: ray, weight: 1)
graph.add(.undirected, from: ruiz, to: sun, weight: 1)
graph.add(.undirected, from: patrick, to: cole, weight: 1)
graph.add(.undirected, from: patrick, to: kerry, weight: 1)
graph.add(.undirected, from: cole, to: ruiz, weight: 1)
graph.add(.undirected, from: cole, to: vincent, weight: 1)
print(graph)

You can simply look at the graph to find the common friend.

print("Ruiz and Vincent both share a friend name Cole")

If you want to solve it with a program you can use the fact that elements are Hashable and find the intersection of the Set of Ruiz’s and Vincent’s friends.

let vincentsFriends = Set(graph.edges(from: vincent).map { $0.destination.data })
let mutual = vincentsFriends.intersection(graph.edges(from: ruiz).map { $0.destination.data })
print(mutual)