Modeling Problems as Graphs

For graph theory to be more than a pursuit in academic trivia — and it is much more than that — we must be able to take problems we wish to solve and reduce them to graph problems. There are two important points here. First, if we cannot turn specific “real” problems into graph problems, we cannot apply graph theory. Second, if we don’t know what kinds of features graphs can have, we cannot use graphs to solve problems at all.

In the service of modeling and solving problems using graph theory we’re introducing one of the most straightforward features a graph can have: a path between two nodes. In graph theory a path between two nodes exists if you can connect those two nodes by traversing edges. Consider this undirected graph representing a (very) simplified version of the internet:

Note that although we’ve used different shapes to differentiate between houses, servers, and routing systems, all of these are still considered nodes in the graph — there is no requirement of graphs that all nodes be of the same “type”.

In this graph there are paths from Tim, Sabah, and Bo’s houses to Google, Facebook, and Amazon. However, Yang’s local ISP has not yet connected to the broader internet. As such, no path exists between Yang’s house, Google, Facebook, and Amazon. Similarly, there are paths between Tim’s house and Bo’s house (via the Verizon node) but no paths between Yang’s house and any of the other houses in the graph.

A path can include a single edge (there is always a path between two neighbors) or it can be a long series of nodes and edges. The length of a path is the number of edges in that path. The length of the path between Tim’s house and Google is two; the length of the path between Tim’s house and Amazon is three.

In a weighted graph the total weight of the path is the sum of the edge weights for the edges in the path. In a weighted graph both the length and the total weight may be interesting, depending on the graph. In an unweighted graph the concept of “total weight” does not exist, since individual weights do not exist either. Note that the path with the least weight and the path with the fewest edges are not always the same. Consider this weighted, undirected graph representing routes between cities:

The shortest path between Miami and Los Angeles is to fly through both Atlanta and Denver for 50+45+90 = 185 total weight, whereas taking the path with the fewest edges is to travel directly from Atlanta to Los Angeles for a cost of 50+150 = 200. When we say “shortest path” in reference to a weighted graph we typically mean the path with the least total weight, not the path with the fewest edges.

Paths are frequently the subject of interest in graphs. Sometimes we’d like to know the shortest path between two nodes (what is the fastest way home from here?), other times finding any path is good enough (can I even get home from here?), sometimes we’d like to know if a path exists under some length threshold (can I be there in under 30 minutes?).

Soon we will examine algorithms for finding paths between nodes, but first we should practice the skill of reducing real problems into graphs. What we mean by “reducing” a problem to a graph is describing the problem in the language of graph theory. Because graphs are so flexible, trying to use a graph to model a problem is one of my favorite strategies for solving a problem. Even if I don’t end up using a graph API, the process frequently helps me understand the problem better, and pushes me closer to a solution. Here is a straightforward process for modeling a problem as a graph:

1. Decide what things in my problem should be represented by nodes.
2. Decide what relationships between these things should be codified into edges.
3. Decide if my edges should be weighted — if so, how?
4. Decide if my edges should be directed — if so, how?
5. Can I think of a property in this graph that represents a solution to my problem?
6. If so — we’re done.
7. If not — can I add properties to the nodes or edges that get me closer?
8. If not — can I redefine the nodes or edges to get me closer?

Sometimes it takes a few attempts at modeling the problem before the crucial insight appears. Other times the modeling is obvious and easy. One thing that has helped me immensely is learning about all the clever tricks people use when defining nodes and edges; there are many kinds of things and relationships that I did not initially think to model as nodes and edges.

First, a straightforward example: Google Maps. While getting all the features of Google Maps working is rather complex (especially at the scale of Google’s business) using a graph to model the problem of traveling along roadways is fairly simple.

What are the nodes? Intersections, freeway onramps, and any place drivers can make a decision to get on other roads (or off the road entirely) are nodes. Notice that many different kinds of things are nodes — once we’re trying to answer the question “what’s the fastest way from A to B” we don’t really care about the difference between an onramp and an intersection except that at both of these places we can change where we go next.

What are the edges? Roads. The relationship we care about is that the places we visit are connected by something we can drive our car on.

What kind of edges? Because roads can be one way, and because Google wants to give users the fastest route home our edges should be directed and weighted. Deciding how to weight the edges could be tricky — an accurate estimate of driving time needs to consider traffic, speed limits, distance, and potentially driving conditions such as rain or snow — but the path with the fewest edges is clearly not always going to be the fastest one.

Let’s apply this process to something that I think is a less intuitive (but powerful) application of graph theory. We’re going to construct a graph, such that a path in our graph is a solution to a riddle sometimes called the three glass riddle. Here is the problem description:

You have 3 containers of different sizes. One holds 12 liters, one holds 8 liters, and the last holds 5 liters. The 12 liter container is full of liquid, the other two are empty. Using only the three containers and no other measuring tools, can you fill one of the containers with exactly 6 liters of liquid? As a fun aside, this puzzle dates back to 1484 and a variant of it features in the plot of Die Hard 3.

Can you use graph theory to solve the riddle? Try to model the problem using graph theory before reading the solution in the next section.

Next article in the series: The Three Glass Riddle

Table of contents