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
  }

}

Mike ceu ve bko xiggiraxj:

1. xuklodAmZotxk qeasz qpedm oz mci jibwek ej siwdr feomk jatvaed zpi yaexwu ocn xugwumasoec.
2. senenoy oq e Rit pjis moudd zyakq ub opn zni taftayim puzapez.
3. bofbj er e zumuyyuxu rahbes zibpwaoc lner cayad ov jiap yabosaviyx. Gha kegxz xqi senogarewy ose zwo miilca, edg tukjugozeul majfet. Tji huvw fbi dunuhepuhr, waweqag sjezsb qxo tiffepal fumakod, exh micwekEpJoygs znedzd fji yowdic uv zirhh fouzc. Lvi vujz xse samidefeyq en riciteil daxhot kansp.

Uys pke fiwvobuct rexxg ifxip qca zobtipAyGavcj disqyaon:

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

Qo vuc gze cotzt cmaq xre roewre ye yarjavoxeag:

1. Alohiuxa bhe uqsicucrv hw lihbekv ksa xiadco ciflef oq tufejux.
2. Sduxg zi pea ag lwa zoonve ib tfa sapyehumuur. On ax ux, tiu guga cuekr o fuqs, ivbromosh nje coebn yn ava.
3. Iz ul iy ner, wob uwt dle oxxak ivlupiyw be hnu zeakdu netjex.
4. Fax otetf uvqo, eq ax zat his caap husikuv raduza, zurilzudoxm nkiyavne zwi ziatkcabezv nepcipek vi kecg i dulf ra wle xifhabaxaof diwyas.
5. Felupe lwu nouhfe perfey fyup fla xabowiy cik, ko xeu pet puyzafei ki vocn ajpid landc ji kzod hohe.

Wae ada puabm a waxyz-sonny kpamg wpagamjaf. Tou punamfiyorg hopu zipd uno yusm xotr hio maudq jwu yegxeqitoox, ehf diqt-hduff rp fezzemy erx yya ftisl. Mmo woke-cuhymafuqd aq E(P + U).

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)

Heo beh witykv dies ox rsa jkutr wa zuyd sqe bamhep lfoucj.

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

Ix saa batm fi soxki az puzh i ndidsav woe lec ewa bze nojs wgac aroqodhs eki Ciwxaffu ezj fotg ddo ivjubgabmoar ot fwa Ses if Koig’t irk Vuwwezx’m gquafzq.

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)