I am working on GIS project where we are making use of road maps that may contain one-way streets.

We are writing some debugging tools one of which I want to design to find "Islands". This would list out all the sets of vertices such that for each pair of vertices A, B in a set you would be able to get from A to B and from B to A.

Here is an example:

A<----------------------> B
\                        /
 \                      /
  \                    /
   \                  /
    \                /
     \              /
      \            /
       \          /
        \        /
         \      /  
         v     v

In this case the islands are {c} and {a,b}.

I expect that this reduces to some well-known graph-theory algorithm, but I don't see it.

Does anyone have any pointers for me to do further research or some ideas about a solution?

  • 7
    $\begingroup$ If I interpret correctly, you are looking for strongly connected components of a directed graph. $\endgroup$ Oct 15, 2010 at 19:13
  • $\begingroup$ Not research level. $\endgroup$ Oct 16, 2010 at 1:17
  • 1
    $\begingroup$ I'd like people voting to close to take a look at this meta discussion on the more general problem of 'modelling'. This is not a homework question, or doesn't seem to be. if we can help the user model some problem in GIS by precisely framing their problem in the language of graph theory, I'm not sure why that's a bad thing. $\endgroup$ Oct 17, 2010 at 3:14
  • $\begingroup$ @Suresh: I had stated in my comments to John Berryman’s answer in the meta thread: “questions do not become suitable on this website just because they are useful for people in applied fields.” I guess that many people disagree, but that is my honest personal opinion. $\endgroup$ Oct 17, 2010 at 10:55
  • $\begingroup$ @Tsuyoshi fair enough. I'll add my comments on meta $\endgroup$ Oct 17, 2010 at 17:05

1 Answer 1


As Robin says, you want strongly connected components. They can be easily found using Tarjan's algorithm, Gabow's algorithm, or several others.

  • $\begingroup$ Thanks - Strongly Connected Components rings an old (very old) graph theory bell! That's exactly what I was looking for. $\endgroup$
    – shindigo
    Oct 18, 2010 at 12:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.