Cycles in Directed Graphs (In Unexpected Places)
We are taking a break from data science, probability and statistics; and revisiting programming exercises. The problem we are going to tackle in this post comes from graph theory and efficient graph traversal. Graph theory is favorite of many interviewers, because formulating a problem in graph theory terms involves a lot of insight, and really tests a candidate’s skills. Most algorithms fit a few tens of lines of code, and whiteboard coding is a quick and easy way of testing those skills.
Read along for a fun application of graph traversal. The problem was asked by Uber. Feel free to browse older posts for more graph algorithms.
Problem
A rule looks like this:
A NE B
This means this means point A
is located northeast of point B
.
A SW C
means that point A
is southwest of C
.
Given a list of rules, check if the sum of the rules validate. For example:
A N B
B NE C
C N A
does not validate, since A
cannot be both north and south of C
.
A NW B
A N B
is considered valid.
Solution
Distinct points in space, and relations between them (North-South or NorthEast-SouthEast) points to an application of Graph theory. But what graph? What should be the vertices or edges of the graph? And how can we convert the given rules into this graph?
The key insights of the problem come from these observations:
- The north-south or east-west relations between the points are transitive. If A is north of B, and B is north of C, then A is north of C. We can write it as
C -> B -> A
. Here, the->
arrow indicates "north of". - The rules are invalid if and only if there is a cycle in the transitive relations. i.e. if there is a rule
A N B
, and we also conclude thatB N A
through an independent transitive reasoning, then there is a cycle in the arrow (->
) relation (as defined above), and hence the rules are invalid. - There are two independent dimensions for cycle-finding: north-south (vertical), and east-west (horizontal). Cycles can be found in either dimension. Any cycle found, in any of these dimenstions, makes the rules invalid.
These observations lead to the following graph algorithm
- We must maintain two graphs:
north_south
andeast_west
. - All the points in the original problem (e.g. “A”, “B” etc) form the vertices of the graph.
- If A is north of B (
A N B
), then there is an edge from B to A (B -> A
) in thenorth_south
graph. The direction of the edge is reversed when A is south of B. - If A is west of B (
A W B
), then there is an edge from B to A (B -> A
) in theeast_west
graph. The direction of the edge is reversed when A is east of B. - We can combine the rules for east/west/north/south directions to construct edges for the remaining four directions. e.g. when A is north-west of B (
A NW B
), then there is an edge from B to A (B -> A
) in thenorth_south
graph AND there is an edge from B to A (B -> A
) in theeast_west
graph. - We can find cycles in either
east_west
ornorth_south
using Depth-First Search (DFS). If either graph contains a cycle, the rules are invalid.
Let’s first declare and define a Graph
class. Let's add a construction method ( insert
), and a const contains_cycle
method to return true
when the graph contains a cycle.

The bulk of implementation is concerned with implementing the insert
and contains_cycle
public methods of the Graph
class. Insert is the simplest of all (looking up and inserting in the neighbors
map). Let's add a quick implementation for it

Before implementing the contains_cycle
method, let's see how the entire graph class is going to be used from our main algorithm. Using a class usually gives us a better understanding of how the class is implemented. Feel free to change tracks during your interviews and make things as clear as possible.
Let’s implement the is_valid
method that takes a set of rules, and returns true if the rules are valid.

This method does three simple things:
- Declares two different maps
east_west
andnorth_south
- Populates the graphs according to the direction given in a rule. e.g. for the
A NE B
, it adds an edge(B, A)
innorth_south
, and an edge(A, B)
ineast_west
. Remember, there are 8 suchif-else
conditions, one per direction. You can simplify these conditions further if you want. For a white-board interview, you can also write a couple of them down, and omit the rest in the interest of time (Most interviewers won't mind 🙂 ).
We are now ready to implement the contains_cycle
method. Depth-First Search (DFS) is the most appropriate algorithm for finding cycles in a directed graph. Recall that DFS maintains two auxiliary data structures
- A
visited
set to indicate that all reachable nodes from the current node have been visited (and no cycles have been found), and - An
in_process
set to indicate that the current node has started exploration, but not all reachable nodes from it have been explored.
A graph contains a cycle when a node which is present in the in_process
set, and not present in the visited
set is visited again! Here is the private method DFS
that implements this logic, and returns true
if the reachable graph from curr
contains a cycle.

As the final piece of the puzzle, let’s use the DFS
method in our contains_cycle
method, and complete the class implementation.

One last thing … Tests
Never forget to write good tests — makes your interview stand out! ( If you have read some of our earlier posts, you might be familiar with our testing approach with GUnit tests).

Originally published at https://cppcodingzen.com on January 15, 2021.