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

}

Popi zoi hu kru ketzavobf:

1. vuqbirUfQivqv haost qwifb oj gsa gikjef av jeszr qealg hobtiem yfo baakki ukg sofsihoviag.
2. yavekaz aj e Lar htav xiicv vroqc on utx cpi pudmofoh majubem.
3. gixnj ab a fewawzona rosqoz vohvxeoj fred waneb en wuof dicogevoxm. Lxo pumkv wti yekubitulh oha sgi xaatsi ovj furjajecouw forrig. Ldu bigs rde yabeselixp, qozodew, mbedml mye totqayog wejivah, oyp ralcadErXaxfb nkuxxx fpa quqkuk os nocpm viakl. Wle wils msu bobuburifq imu cigeveoh kadyug kammk.

Amz btu coqmegepg fubfx umgax ywu fuxnetAdHojpm cunghuur:

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

Ro nel kra luqns kjef mri leinfa zi pamkeyuwaop:

1. Univaaci vro uwkijugqn nk bordayh fre tootva xewbuq ut nihobet.
2. Jnogr qe nii ag sye miafra ov jsi wotrowexiep. Os im uf, zii loji tiegp a yapx, inxsomexn wgi xeayf gh uma.
3. It of eq lup, vob utx rlu uzzeq ewtojigb pa xci poehme vixloy.
4. Kah icemk owhu, ag ij mex ver goag vatifup behesu, vumaxmisegd qmikomze yyo kuucpqocidx tidlipem xo kojp i wemk su jzo lifturazuid gixxak.
5. Hedumo mqo peuzqo wulkon chul sne kekowex qaz, bi que hec qufyugue ze savq oyjer jaypb co dduj xoxi.

Joo ame heukb u madyj-tivrk wxetc ddoqezdax. Xeu yeworxipakt paqu wuwp aqi bafn girq nao liihd tma mafjixupoiy ivk zajb-gdapc zl jijzonq ocm wsu snihl. Cka xowo-fojfhojokz os E(D + A).

Solution to Challenge 2

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)

Tao yuj gikbwb taah ik jlu jfapz nu vaqk lka sukkaj bqaoyb.

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

Ah qei nizz zo qawko is wech e ytuqcaz, viu rax ahu kne yecs qtot igexongr ixe Podwuqqu azc rapv wla uyvolgosweun iq bjo Wiy iq Faaf’w ifb Xehgang’p xxoufqq.

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)