teaching machines

CS 240: Lecture 38 – Graph Algorithms

November 29, 2021 by . Filed under cs3, fall-2021, lectures.

Dear students:

I don’t know about you, but my mind has been elsewhere. Our routine striving was cut into by a break. I’m glad it did. Sometimes I think that I’ll only have peace when I get all the things done. What a lie that is. I will never be done. And even if something I’m working on gets finished, I won’t have peace afterward, not for long anyway. It’s better that breaks just interrupt us without waiting for a convenient time.

We pick up our conversation of algorithms and data structures with a couple of tricks for finding meaningful paths through graphs. First we’ll find a path that navigates through a prerequisite chain. Second we’ll find the shortest path from a vertex to another. These problems are pretty easy for humans to solve visually when the number of vertices is small. Don’t be deceived. As with every other topic in this class, we must assume that the size of our data structure will exceed our capacity to deal with it. Yet when we introduce the topic, we use small examples.

Topological Sort

Imagine a series of tasks in a multi-task process. Some tasks must be completed before others. For example, maybe you’re planning a space flight. You’ve got to get some new o-rings before you assemble the solid rocket booster before you install the booster. Other tasks can be scheduled more freely, like celebrating a successful launch with a glass of Blue Powerade. They can happen any time after earlier stages. You can find a path through this process by making each stage a vertex. If a stage is a prerequisite for another, then there’s a directed and unweighted edge from the prerequisite to its successor. Then you run a topological sort on the graph.

The Greek word topos means place. The topological sort orders the vertices by their place in the prerequisite chain, not by any numeric value. The algorithm can be implemented a couple of different ways. We can run a depth-first traversal, chasing out the longest prerequisite chain in the graph and adding its vertices in backward order and branching recursively through the neighbors. A pseudocode implementation might look like this:

function topologicalSort(graph g)
  for each vertex v
    mark v as unvisited
  order = []
  for each vertex v
    if v is unvisited
      depthTraverse(g, v, order) 

function depthTraverse(graph g, vertex v, list order)
  mark v as visited 
  for each neighbor n
    if n is unvisited
      depthTraverse(g, n) 
  prepend v to order

Alternatively, if we wish to avoid the recursion, we can implement this with a breadth-first traversal. This implementation works by keeping a count of how many incoming edges each vertex has from unvisited vertices. When that number goes to 0, a vertex’s prerequisites have been visited and thus it is safe to visit the vertex. Here’s how it might be implemented in pseudocode:

function topologicalSort(graph g)
  create queue
  order = []
  
  for each vertex v
    inCounts[v] = 0

  for each vertex v
    for each neighbor n
      increment inCounts[n]

  for each vertex v
    if inCounts[v] is 0
      enqueue v

  while queue isn't empty
    v = dequeue
    append v to order
    for each neighbor n
      decrement inCounts[n] 
      if inCounts[n] is 0
        enqueue n

There are more legal topological sorts than these deterministic algorithms will generate. Consider this graph:

How many possible topological sorts are there for this graph? We’ll answer this as a peer instruction exercise.

Shortest Paths

The second algorithm we’ll look at today finds the quickest route from a starting vertex to all the other vertices in the graph. This algorithm was invented by Edsger Dijkstra, an opinionated computer scientist from the Netherlands. It works by maintaining a record of how distant each vertex is. Initially all vertices are infinitely far away, except for the starting vertex, which has a distance of 0. It advances to the next nearest vertex. If that vertex makes reaching other vertices cheaper, then those vertices’ distances are lowered. Then it advances again and again, until all vertices have been visited.

To actually trace out a path, the algorithm must keep track of which vertex provided the cheapest route. We walk this list of predecessors backward to generate the complete path.

function shortestPaths(graph g, vertex from, int[] distances, vertex[] predecessors)
  for each vertex v
    distances[v] = infinity
    predecessors[v] = null
    mark v as unvisited

  distances[from] = 0
  repeat g.vertices.size
    v = find closest unvisited vertex
    mark v as visited
    if distances[v] is infinity
      return as there's no way to reach any more vertices

    for each neighbor n
      distanceViaV = distances[v] + g.weight(v, n)
      if distances[n] > distanceViaV
        distances[n] = distanceViaV
        predecessors[n] = v

To find the shortest path to a particular destination, we trace backward through the predecessors list, starting at the at destination and stopping at from.

Exercises

For the remainder of our time, we will work through an exercise on Dijkstra’s algorithm.

TODO

You have some work to do before the next class:

See you next time.

Sincerely,

P.S. It’s time for a haiku!

Course N won’t make sense
Not until course N + 1
Thus post-requisites