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 that B 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 and east_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 the north_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 the east_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 the north_south graph AND there is an edge from B to A (B -> A) in the east_west graph.
• We can find cycles in either east_west or north_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 and north_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) in north_south, and an edge (A, B) in east_west. Remember, there are 8 such if-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.