City Planning Using Graph Theory

Let’s wear our “city-planner’s” hats for this article. Assume that we are building a new city with n neighborhoods and m one-way roads between them.

Being city planners, we have a passion for pizza, and we want to place a minimal amount of pizzerias such that from each pizzeria the delivery guy could drive to a certain neighborhood and go back as well.

Right now, we are trying to determine in which neighborhood should we place a pizzeria.
Let’s go over an example to better understand.

Placing a pizzeria at N4 means that this pizza branch can deliver to N3 and N2 as well, why?

From N4 I can get to N3 using one road. can I go back from N3 to N4? yes — using the N3 to N2 road and then the N2 to N4 road.

From N4 I can get to N2 using two roads — N4 to N3 and then N3 to N2. can I go back to N4 now? yes — using the road from N2 to N4.

Why can’t we go to N1? from N4 we can find a road leading to N1, but from N1 there is no way back to N4.

In this example, the minimal pizzerias placement is 2.
The first one will be placed in one of N4, N3, N2 and the second one will be placed in one of N1, N5.

Can We Generalize This?

In the previous example, you might have noticed that I drew these neighborhoods as vertices in a graph and the one-way roads are directed edges — so we can actually transform our city overview into a graph.

Every neighborhood is a vertex. Every one-way road from neighborhood A to neighborhood B will be a directed edge between the matching vertices.

Before I introduce you to the algorithm, we need to understand two definitions.

1. Strongly connected component —(Let’s call SCC from now on)

2. Transpose graph

A transpose graph of a directed graph G is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of the corresponding edges in G.

Algorithm

Given a directed graph G(V, E) we can find it’s strongly connected components in the following manner

1. Call DFS(G) to compute retreat time of each vertex in V
2. Compute G^T
3. Call DFS(G^T) with a decreasing order of the retreat time
4. Output the vertices in each DFS tree generated in (3) as seperate component

If you are not familiar with DFS algorithm or just want to refresh it — there are many great tutorials online, for example from MIT.

Using this algorithm, we will get our strongly connected components — in each of them we can place one pizzeria and that branch will be able to deliver to all of the other neighborhoods inside the same component.

Final Words

Reality might be more complex and you probably need some smarter algorithms to determine the optimal placement, but this algorithm is a good foundation in understanding how it generally works.

If you want to see more on this topic and others, check out my blog.