Graphs

Graph Terminology

A graph is a general data structure for showing connections among a set of objects. The objects are called nodes or vertices, and we will usually label them with a unique number or string. The connections are called edges; an edge connects two nodes. Depending on the application, there may be additional conditions or properties of edges:

• In an undirected graph, an edge linking $x$ to $y$ is also a link from $y$ to $x$.
• In a directed graph, we distinguish an edge from $x$ to $y$ (we refer to $x$ as the source and $y$ as the target) from an edge going the other way, from $y$ to $x$.
• In a simple graph, there must be at most one edge connecting any pair of nodes, and there are no loops (edges from a node to itself).
• To emphasize that multiple edges are allowed between nodes we may refer to a multigraph; to emphasize that loops are allowed we may refer to a loop graph. A multigraph with loops is sometimes called a pseudograph, although we will generally just refer to all of these variants as graphs and only make distinctions where needed.
• An edge may be labeled with a number or string; we do not generally require edge labels to be unique.
• If there is an edge from $x$ to $y$, then we say that $y$ is adjacent to $x$.

Graph Representations

One representation of an unlabeled graph is simply as a set of ordered pairs of nodes. This corresponds to the usual notion of a relation as a set of pairs (sometimes called, perhaps confusingly, the "graph" of the relation).

Another representation is as a function (often given in the form of a table) from nodes to a set of neighbors (i.e., the adjacent nodes). The set of neighbors of each node is often presented as a list, which leads to the term adjacency list for this presentation.

A third representation is as an adjacency matrix. If the nodes are numbered 1 through $N$, then the adjacency matrix is the two-dimensional array where the entry in row $i$, column $j$ will be 1 (or 'true') if there is an edge from $i$ to $j$ and 0 ('false') if not. This representation is often extended to labeled graphs where the labels are weights: the entry for $(i,j)$ gives the weight (or distance, or cost, …) of the edge between $i$ and $j$. Depending on the application, it may be preferable to use an infinite weight to represent absent edges, rather than 0 (since a weight of 0 might be interpreted as saying there is no cost to go from $i$ to $j$).

Scala Code for Graph Representations

Here is some Scala code defining types for these representations, plus some conversion functions. In each case, the type is parameterized by a node type T, and the representation type is a case class where the first component is the list of nodes (because there is no generic way to get this list for an arbitrary type T, and if T is Int or String we will only want to use a subset of the possible values anyway).

trait Graph[T]:
  def nodes: List[T]
  def pairs: List[(T, T)]
  def neighbors(node: T): List[T]
  def adjacent(node1: T, node2: T): Boolean
  def asPairs = Graph.Pairs(nodes, pairs)
  def asAdjList = Graph.AdjList(nodes, neighbors)
  def asAdjMatrix = Graph.AdjMatrix(nodes, adjacent)

object Graph:
  case class Pairs[T](nodes: List[T], pairs: List[(T, T)]) extends Graph[T]:
    def neighbors(node: T): List[T] = {
      for
        (node1, node2) <- pairs
        if node1 == node
      yield node2
    }

    def adjacent(node1: T, node2: T): Boolean = pairs.contains(node1 -> node2)

    override def toString: String = pairs.mkString("{", ",", "}")

  case class AdjList[T](nodes: List[T], adj: T => List[T]) extends Graph[T]:
    def pairs: List[(T, T)] = {
      for
        node1 <- nodes
        node2 <- adj(node1)
      yield (node1, node2)
    }
    
    def neighbors(node: T): List[T] = adj(node)
    
    def adjacent(node1: T, node2: T): Boolean = adj(node1).contains(node2)

    override def toString: String =
      nodes
        .map(node => s"$node:${adj(node).mkString("{", ",", "}")}")
        .mkString("[", "; ", "]")

  case class AdjMatrix[T](nodes: List[T], matrix: (T, T) => Boolean) extends Graph[T]:
    def pairs: List[(T, T)] = {
      for
        node1 <- nodes
        node2 <- nodes
        if matrix(node1, node2)
      yield (node1, node2)
    }
    
    def neighbors(node: T): List[T] = {
      for
        node2 <- nodes
        if matrix(node, node2)
      yield node2
    }
    
    def adjacent(node1: T, node2: T): Boolean = matrix(node1, node2)

    override def toString: String =
      nodes
        .map(n1 => s"$n1:${nodes.map(n2 => matrix(n1, n2).compare(false)).mkString}")
        .mkString("[", "; ", "]")

// Example 1
val demo1 = Graph.Pairs(
  List(1, 2, 3, 4),
  List(1->1, 1->2, 1->3, 1->4, 2->2, 2->4, 3->3, 4->4)
)
// demo1: Pairs[Int] = Pairs(
//   nodes = List(1, 2, 3, 4),
//   pairs = List((1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4))
// )

println(demo1)
// {(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}
println(demo1.asAdjList)
// [1:{1,2,3,4}; 2:{2,4}; 3:{3}; 4:{4}]
println(demo1.asAdjMatrix)
// [1:1111; 2:0101; 3:0010; 4:0001]

// Example 2
enum Demo2Nodes:
  case A, B, C, D
import Demo2Nodes.*

val demo2 = Graph.AdjList(
  List(A, B, C, D),
  {
    case A => List(B, D)
    case B => List(A, C)
    case C => List(B)
    case D => List(A)
  }
)
// demo2: AdjList[Demo2Nodes] = AdjList(
//   nodes = List(A, B, C, D),
//   adj = repl.MdocSession$MdocApp$$Lambda/0x0000000127ca49d8@775da17c
// )

println(demo2.asPairs)
// {(A,B),(A,D),(B,A),(B,C),(C,B),(D,A)}
println(demo2)
// [A:{B,D}; B:{A,C}; C:{B}; D:{A}]
println(demo2.asAdjMatrix)
// [A:0101; B:1010; C:0100; D:1000]

// Example 3
val demo3 = Graph.AdjMatrix(
  List("red", "green", "yellow"),
  {
    case ("red", "green") => true
    case ("green", "yellow") => true
    case ("yellow", "red") => true
    case _ => false
  }
)
// demo3: AdjMatrix[String] = AdjMatrix(
//   nodes = List("red", "green", "yellow"),
//   matrix = repl.MdocSession$MdocApp$$Lambda/0x0000000127ca5e00@3a47e14b
// )

println(demo3.asPairs)
// {(red,green),(green,yellow),(yellow,red)}
println(demo3.asAdjList)
// [red:{green}; green:{yellow}; yellow:{red}]
println(demo3)
// [red:010; green:001; yellow:100]

Here is a collection of utilities to render a graph with Doodle:

trait NodeLayout[T]:
  def location(node: T): Point

class CircleNodeLayout[T](nodes: List[T], radius: Double) extends NodeLayout[T]:
  def location(node: T): Point = {
    val i = nodes.indexOf(node)
    Point(radius, 90.degrees - 1.turns * i / nodes.length)
  }

class GridNodeLayout[T](nodes: List[T], columns: Int, spacing: Double) extends NodeLayout[T]:
  private val shift = (columns - 1) * spacing / 2

  def location(node: T): Point = {
    val i = nodes.indexOf(node)
    val row = i / columns
    val col = i % columns
    Point(col * spacing - shift, -row * spacing)
  }

trait NodeImage[T]:
  def apply(node: T, point: Point): Image
  def radius(node: T): Double

class DefaultNodeImage[T](diameter: Double) extends NodeImage[T]:
  def apply(node: T, point: Point): Image = {
    (Image.text(node.toString) `on` Image.circle(diameter)).at(point)
  }

  def radius(node: T): Double = diameter / 2

class ColoredNodeImage[T](diameter: Double, nodeColor: T => Color)
extends DefaultNodeImage[T](diameter):
  override def apply(node: T, point: Point): Image = {
    super.apply(node, point).fillColor(nodeColor(node))
  }

trait EdgeImage[T]:
  def apply(
    node1: T, point1: Point,
    node2: T, point2: Point,
    nodeImage: NodeImage[T]
  ): Image

class DefaultEdgeImage[T] extends EdgeImage[T]:
  val arrowLength = 7
  val arrowAngle = 30.degrees
  val loopOut = 120.degrees
  val loopIn = 60.degrees

  def apply(
    node1: T, point1: Point,
    node2: T, point2: Point,
    nodeImage: NodeImage[T]
  ): Image = {
    if node1 == node2 then
      val radius = nodeImage.radius(node1)
      val p1 = point1 + Vec(radius, loopOut)
      val p2 = point1 + Vec(radius, loopIn)
      val c1 = point1 + Vec(4 * radius, loopOut)
      val c2 = point1 + Vec(4 * radius, loopIn)
      val p3 = p2 + Vec(arrowLength, loopIn + arrowAngle)
      val p4 = p2 + Vec(arrowLength, loopIn - arrowAngle)
      Image.path(OpenPath.empty
        .moveTo(p1).curveTo(c1, c2, p2)
        .moveTo(p2).lineTo(p3)
        .moveTo(p2).lineTo(p4)
      )
    else
      val radius1 = nodeImage.radius(node1)
      val radius2 = nodeImage.radius(node2)
      val v = (point2 - point1).normalize
      val p1 = point1 + v * radius1
      val p2 = point2 + v * -radius2
      val p3 = p2 + v.rotate(arrowAngle) * -arrowLength
      val p4 = p2 + v.rotate(-arrowAngle) * -arrowLength
      Image.path(OpenPath.empty
        .moveTo(p1).lineTo(p2)
        .moveTo(p2).lineTo(p3)
        .moveTo(p2).lineTo(p4)
      )
  }

def showGraph[T](
  g: Graph[T],
  layout: NodeLayout[T],
  nodeImage: NodeImage[T],
  edgeImage: EdgeImage[T]
): Image = {
  val nodeImages = g.nodes.map { case node =>
    val point = layout.location(node)
    nodeImage(node, point)
  }

  val edgeImages = g.pairs.map { case (node1, node2) =>
    val point1 = layout.location(node1)
    val point2 = layout.location(node2)
    edgeImage(node1, point1, node2, point2, nodeImage)
  }

  nodeImages.foldLeft(Image.empty)(_ `on` _) `on`
    edgeImages.foldLeft(Image.empty)(_ `on` _)
}

Here are renderings of the example graphs:

val image1 = showGraph(
  demo1, 
  new CircleNodeLayout(demo1.nodes, 50), 
  new DefaultNodeImage(20),
  new DefaultEdgeImage)
val image2 = showGraph(
  demo2,
  new GridNodeLayout(demo2.nodes, 3, 50),
  new DefaultNodeImage(20),
  new DefaultEdgeImage)

def nodeColor(node: String): Color = node match
  case "red" => Color.red
  case "yellow" => Color.yellow
  case "green" => Color.green
  case _ => Color.white
val image3 = showGraph(
  demo3,
  new CircleNodeLayout(demo3.nodes, 50),
  new ColoredNodeImage(40, nodeColor),
  new DefaultEdgeImage)

Graph Traversals

We will consider two main ways of traversing a graph here. In addition to visiting all of the nodes in the graph, each approach will allow us to answer some extra questions about the structure of the graph. The depth-first traversal is analogous to the pre-, in-, and postorder traversals of a tree, in the sense that we will (recursively) visit all of the nodes reachable from one neighbor before backing up and trying another neighbor. The breadth-first traversal by contrast is analogous to the level order traversal of a tree, where we will visit all of the immediate neighbors before continuing on to visit their neighbors, and so on. Just as with level order traversal, the breadth-first traversal does not have as natural a recursive implementation as depth-first, although we will see that both can be expressed with very similar code by making use of an explicit data structure to control the traversal. Graph traversals in general are more complicated than tree traversals, because we have to worry about sharing of descendants of a node (there may be multiple paths to reach the same node) as well as cycles in the graph (there may be paths that loop back on themselves). Indeed, one definition of a tree is that it is a graph with a distinguished node, called the root, such that there is a unique path from the root to any other node; if it is unique, then no descendants are shared and there must not be any cycles.

Depth-First Traversal

To perform a depth-first traversal, we will need to keep track of two additional pieces of information about the nodes. The first is a set of visited nodes; whenever we first arrive at a node, we add it to this set. The other is the finishing list; whenever we have finished examining all of a node's neighbors, we will add it to the head of the finishing list. When working with a graphical representation, we will color in a node when it is first visited, and then write a number (the finishing number) next to the node when it is finished showing its position from the end of the finishing list. This information corresponds to performing actions according to preorder (visiting) and postorder (finishing) traversal of a tree.¹

Here is the basic algorithm for depth-first traversal starting from a node $n$:

• Mark $n$ as visited
• While there is an adjacent unvisited node, $p$
  • Perform a depth-first traversal starting from $p$
• When all nodes adjacent to $n$ are visited, add $n$ to the head of the finishing list.

To traverse all of the nodes in a graph, first choose an arbitrary node and perform a depth-first traversal starting from that node. When that node is finished, if there are any remaining unvisited nodes then choose one and repeat.

Clearly this procedure will eventually visit all of the nodes exactly once. By keeping track of a little more information, it can also answer some interesting questions about a graph. As we are traversing the graph, we will put each edge into one of three categories:

• Tree Edge: an edge that we follow to get to an adjacent unvisited node
• Back Edge: an edge that we do not follow because it leads to a visited, but not yet finished, node
• Forward Edge: an edge that we do not follow because it leads to an already finished node²

Here then is the augmented algorithm for depth-first traversal from $n$:

• Mark $n$ as visited
• For each edge $e$ coming out of $n$ and going to a node $p$:
  • If $p$ is unvisited, perform a depth-first traversal from $p$ and mark $e$ as a tree edge
  • If $p$ is visited but not yet finished, mark $e$ as a back edge
  • If $p$ is finished, mark $e$ as a forward edge
• Add $n$ to the finishing list.

The tree edges form what is known as the depth-first search tree, with the root at the node where we started the traversal. More generally, since we get a separate tree each time we restart the traversal, the result of visiting all of the nodes in a graph will in general be a depth-first search forest (since a forest is just a set of trees).

If we ever find a back edge in traversing a graph, then the graph has a cycle. Suppose that there is a back edge from $n$ to $p$. Since $p$ is visited but not yet finished, there must be a sequence of tree edges leading from $p$ to $n$ (the current path we are exploring). That path plus the back edge will form a cycle. Conversely, if a graph has a cycle, then we will find at least one back edge, because there will be some point in the traversal where we close the loop back to a node on the current path (which will necessarily be visited but not yet finished).

On the other hand, if we find no back edges, then the graph is acyclic. Directed acyclic graphs (often called DAG) share many of the advantages of trees; indeed, we have already encountered them as combinational circuits, which we viewed as a generalization of boolean expression trees (with shared subterms). They are also useful to model dependencies, for example showing which tasks must be completed before others (such as prerequisite courses in a college catalog).

Given an acyclic graph, we may "linearize" the nodes by choosing an order in which to list them that respects the dependencies among them (for example, an order in which to take a sequence of classes where all the prerequisites are taken before the courses that depend on them). This is a generalization of sorting, where the edges in the graph reflect only a "partial" ordering among the items; it is known as topological sorting, and the result is a topological ordering of the nodes. The perhaps surprising fact about the finishing list is that, if there were no cycles, then it gives a topological ordering! The reason is that we can finish a node only after all of the nodes that can be reached from it are finished, so when we put it at the front of the finishing list it will be followed by all of the nodes that depend on it.

As an example of depth-first traversal, consider the following graph:

val demo = Graph.Pairs(
  List("A", "B", "C", "D", "E", "F"),
  List("A"->"B", "A"->"C", "B"->"C", "B"->"D",
    "D"->"A", "E"->"C", "E"->"F", "F"->"D", "F"->"F")
)

Start by marking $A$ visited:

Follow the (tree) edge to $B$:

Follow the (tree) edge from $B$ to $C$:

Node $C$ has no neighbors at all, so mark it finished:

Back at node $B$, follow the (tree) edge to $D$:

The only edge out of $D$ goes to $A$, which is visited but not yet finished, so mark it as a back edge and mark $D$ finished:

Now node $B$ is also finished, so back up to node $A$ and consider its remaining outward edge. It goes to node $C$, which is already finished, so mark it as a forward edge and mark $A$ finished as well:

We still have nodes $E$ and $F$ unvisited. Arbitrarily restart the traversal at $E$, and first consider the edge to $C$. Since $C$ is already finished, this is another forward edge:

Now follow the tree edge from $E$ to $F$, and find the edge from $F$ to $D$ is a forward edge:

Finally, the edge from $F$ to itself is a back edge, after which $F$ and then $E$ are finished:

Since there were back edges, the graph has at least one cycle. In fact, there are two: $A\rightarrow B\rightarrow D\rightarrow A$, and $F\rightarrow F$. In general, there may not be an exact match between the number of back edges and the number of cycles, because several cycles may share a single back edge.

For another example, here is the same graph with the edges $D\rightarrow A$ and $F\rightarrow F$ removed:

println(demoB)
// {(A,B),(A,C),(B,C),(B,D),(E,C),(E,F),(F,D)}

We leave the details of tracing through the traversal as an exercise, but here is the final marked graph:

The finishing list is $E$, $F$, $A$, $B$, $D$, $C$ in this case. Since there were no back edges, this is a topological ordering of the nodes in the graph. Here is the graph with the nodes reordered:

Observe that all of the arrows go from left to right.

Note that other markings are possible, depending on the choices made (which nodes to start at, and the order in which to visit the edges out of each node). As another exercise, perform another traversal of this graph that produces a different marked-up result. Can you find a different topological ordering?

Scala Implementation of Depth-First Traversal

Here is the depth-first traversal algorithm implemented in Scala. For simplicity, we are using a mixed functional and imperative approach; from the outside, the depthFirst function is pure, with no side-effects, but inside its body we are using mutable variables to keep track of the visited and finished nodes, as well as the tree, forward, and back edges. We could avoid this by creating a record to hold the current state of these variables, making a modified copy of the state each time we want to change one, and passing the state around as an input and output to the dfs function, but the external effect would be the same.

enum DFSResult[T]:
  case Cycle(backEdge: (T, T))
  case TopoOrder(nodes: List[T])
import DFSResult.*

def depthFirst[T](g: Graph[T]): (DFSResult[T], Graph[T]) = {
  var visited: List[T] = Nil
  var finished: List[T] = Nil
  var tree: List[(T, T)] = Nil
  var forward: List[(T, T)] = Nil
  var back: List[(T, T)] = Nil

  def dfs(start: T): Unit = {
    visited = start :: visited
    for node <- g.neighbors(start) do
      val edge = (start, node)
      if finished.contains(node) then
        forward = edge :: forward
      else if visited.contains(node) then
        back = edge :: back
      else
        tree = edge :: tree
        dfs(node)
    finished = start :: finished
  }

  for start <- g.nodes do
    if !visited.contains(start) then dfs(start)

  val forest = Graph.Pairs(g.nodes, tree)
  back match
    case Nil => (TopoOrder(finished), forest)
    case e :: _ => (Cycle(e), forest)
}

println(depthFirst(demo))
// (Cycle((F,F)),{(E,F),(B,D),(B,C),(A,B)})
println(depthFirst(demoB))
// (TopoOrder(List(E, F, A, B, D, C)),{(E,F),(B,D),(B,C),(A,B)})

The returned value from depthFirst is a pair of a DFSResult and a Graph. The DFSResult is either Cycle(e), where e is a back edge (pair of nodes) causing a cycle, or TopoOrder(nodes), where nodes is a list of the graph nodes in topological order. The Graph value is the subgraph consisting of just the tree nodes.

Equivalent Imperative Code

Instead of using the recursive helper function dfs, which performs a single depth-first exploration starting from a given node, we may perform all of the exploration by using an explicit stack to keep track of the current path from the starting node. Each entry in the stack can be one of three values:

• Visit(n) says that the current task is to visit node n;
• Finish(n) says that the current task is to finish node n (note that this is pushed on the stack underneath all of the edges out of n, so it will only be done after all of the neighbors are processed); and
• Edge(n1, n2) says that the current task is to consider the edge from n1 to n2.

The main function can now be written as a loop that continually removes a task from the stack and then updates the stack and the state to perform that task:

enum DFSStackItem[T]:
  case Visit(node: T)
  case Finish(node: T)
  case Edge(node1: T, node2: T)
import DFSStackItem.*

def depthFirst2[T](g: Graph[T]): (DFSResult[T], Graph[T]) = {
  import scala.collection.mutable.Stack as MutStack
  val stack: MutStack[DFSStackItem[T]] = MutStack.empty

  var visited: List[T] = Nil
  var finished: List[T] = Nil
  var tree: List[(T, T)] = Nil
  var forward: List[(T, T)] = Nil
  var back: List[(T, T)] = Nil

  for start <- g.nodes do
    if !visited.contains(start)
    then
      stack.push(Visit(start))

      while stack.nonEmpty do
        stack.pop() match
          case Visit(node) =>
            visited = node :: visited
            stack.push(Finish(node))
            for node2 <- g.neighbors(node) do
              stack.push(Edge(node, node2))

          case Finish(node) =>
            finished = node :: finished
            
          case Edge(node1, node2) =>
            val edge = (node1, node2)
            if finished.contains(node2) then
              forward = edge :: forward
            else if visited.contains(node2) then
              back = edge :: back
            else
              tree = edge :: tree
              stack.push(Visit(node2))
      end while
  end for
  
  val forest = Graph.Pairs(g.nodes, tree)
  back match
    case Nil => (TopoOrder(finished), forest)
    case e :: _ => (DFSResult.Cycle(e), forest)
}

println(depthFirst2(demo))
// (Cycle((F,F)),{(E,F),(B,D),(A,B),(A,C)})
println(depthFirst2(demoB))
// (TopoOrder(List(E, F, A, B, D, C)),{(E,F),(B,D),(A,B),(A,C)})

Breath-First Traversal

The big payoff of rewriting the depth-first traversal to use an explicit stack is that we can now explain breadth-first traversal (and level order traversal of a tree) quite simply: instead of a stack, use a queue! The idea is that the queue is maintaining a list of edges yet to be processed. When the algorithm starts, we push all of the edges of the initial node onto the queue and process them in order. As we handle each edge, if its target node has not yet been visited, then we push all of its outgoing edges onto the queue, but they will have to wait until all of the current edges are processed. In this way, we visit all of the immediate neighbors first, and then we continue with their neighbors, followed by their neighbors' neighbors, etc., until the entire graph is traversed.

Breadth-first traversal is desirable when the graph might be large and we want to stop searching when we find the closest match, or if we only want to process items within a given distance (for example, it is used in game-playing strategies to look ahead up to a certain number of moves). Several famous algorithms can also be viewed as variants of breadth-first traversal; details are in the section on Shortest Paths and Minimum Spanning Trees.

Exercises

1. Give the list of pairs, adjacency list, and adjacency matrix representations for the following undirected graph:

Answer

  Pairs: {(A,B),(B,A),(A,C),(C,A),(B,C),(C,B),(A,D),(D,A)}
  Adjacency List: [A:{B,C,D}; B:{A,C}; C:{A,B}; D:{A}]
  Adjacency Matrix: [A:0111; B:1010; C:1100; D:1000]

2. Consider the adjacency matrix representation of a graph. What can you say about the matrix if the graph is undirected? What if the graph has loops on all of the nodes?

Answer

An undirected graph will have a symmetric adjacency matrix: the entry in row $i$, column $j$ is the same as the entry in row $j$, column $i$ (symmetric about the diagonal). A graph with all of the self-loops will have 1's along the diagonal (and a simple graph, with no loops, will have 0's on the diagonal).

3. (Based on a problem from Aho & Ullman) Consider the following directed graph:

• Give two different depth-first traversal trees starting at node $a$. For each, also label the graph to show the forward and back edges, and the finishing number.

Answer

Using depth-first traversal (others are possible):

• Find the distance (length of the shortest path) from $a$ to each of the other nodes.

Answer

Using breadth-first traversal, we find that $b$ and $d$ are one unit away from $a$, while $c$, $d$, and $f$ are each two units away.

Footnotes

1. There is no analogue to inorder, because we don't impose any order on the neighbors of a node, so there is no equivalent of having finished the left child and being about to start the right child. ↩

2. Some authors distinguish between proper forward edges, where there is a path of tree edges leading from the current node to the already finished node, and cross edges, where there is not such a path, but we will not need that distinction. ↩