The Art of Concurrency

Chapter 10. Graph Algorithms

A graph is a computation object that is used to model relationships among things. For example, constituent atoms within a molecule, components within an electrical circuit, and nodes in a communication network are all things that you can represent and manipulate as graphs. Trees are graphs with special properties, so you could represent a hierarchical chart or family tree as a graph. There is a lot of terminology involved with graph theory. The next few paragraphs give a quick overview of the basic terminology needed to study concurrent algorithms to compute with graphs. If you’re already familiar with graph theory terms, feel free to skip ahead a bit. Of course, if you’ve made it this far through the book, what’s another page and a half between reader and author?

A graph is made up of two finite sets: a set of nodes (or vertices) and a set of edges. Each node has a label to identify it and distinguish it from other nodes. Edges in a graph connect exactly two nodes and are denoted by the labels of the pair of nodes that are related. If you have a graph of three nodes—A, B, and C—the two edges connecting A with B and B with C would be written as (A,B) and (B,C).

A graph is directed if all edge pairs are ordered. Directed edges represent a one-way relationship from one node to another. If the node pairs are unordered, the graph is undirected. A ...