What are strongly connected components used for?

Question

I have found several algorithms that explain how to find strongly connected components in a directed graph, but none explain why you would want to do this. What are some applications of strongly connected components?

Answer 1

You should check out Tim Roughgarden's Introduction to Algorithms course on Coursera. For every algorithm he goes over, he explains some applications of it. Very useful, and makes one see the value of studying algorithms!

The use of strongly connected components that I remember him saying is that one could use it to find groups of people who are more closely related in a huge set of data. Think of facebook and how they recommend people that might be your friends...

This could also be used to see chunks of a population. Say, "Wow, this huge component all has the hobby of walking backwards and likes eating moldy pizza!," it could show correlation. Advertisers for moldy pizza would use this data to target people who like walking backwards. Who knows!

Answer 2

One example is in model checking:

Finding strongly connected component is done in explicit model checking in formal verification.

In model checking - we have a state machine, which represents the models of our software/hardware, and we try to prove temporal logic¹ formulas on it.

For example: The formula EG(p) means: there is a path in the graph, where for each state - the logic formula p yields true.

The algorithm for proving if EG(p) is true on a graph (model) is finding the maximal strongly connected components (SCC), and then checking paths leading to it in the graph.

Note that model checking is applied widely in the industry - especially for proving correctness of hardware components.

---

(1) The importance of temporal logic to computer science is great, and its inventor Amir Pnueli recieved a turing award for it!

Answer 3

Another application can be found in vehicle routing applications. A road network can be modeled as a directed graph, with vertices being intersections, and arcs being directed road segments or individual lanes. If the graph isn't Strongly Connected, then vehicles can get trapped in a certain part of the graph (i.e they can get in, but not get out).

In many of these vehicle routing applications, you want to generate routes for a specific area (for instance a routing problem within a city). Prior to generate routes, you would have to extract street data, for instance from Google Maps, Here maps, or Open Street maps. These maps do not just cover the area you are interested in, but they cover the entire world. Consequently you end up taking a snapshot of the area of interest, for instance by computing the induced subgraph of all intersections who's geographical coordinates lay within the area of interest. The resulting subgraph is not necessarily strongly connected (for instance, you can have a road that enters and leaves the area, but is not connected to any other road inside the area). One would then preprocess the subgraph by enumerating all strongly connected components, and throwing away all but the largest component.