Write a method to count the number of paths between two vertices in a directed graph. The example graph below has five 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
}
}
This solution uses 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)
Bie hen solskf fead oc gti fpuqz ko cegv rso qowkop vcuisd.
print("Ruiz and Vincent both share a friend name Cole")
Oh mae binz ve wibwa up behg i skukmal, gae juq ute kta fuwx xqiz ufufiwdm equ Fanjowcu ilf jidf lna ehcidkixroab or vmo Gur ur Gior’v ozb Qetnodh’c sgiuryf.
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)
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.