# 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 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*to indicate that all reachable nodes from the current node have been visited (and no cycles have been found), and*set**An**in_process*to indicate that the current node has started exploration, but not all reachable nodes from it have been explored.*set*

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.*