Home iOS & Swift Books Data Structures & Algorithms in Swift

37
Graphs Challenges Written by Vincent Ngo

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.

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
  }

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

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)
print("Ruiz and Vincent both share a friend name Cole")
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)

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.