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$ – Robin Kothari Oct 15 '10 at 19:13
  • $\begingroup$ Not research level. $\endgroup$ – Warren Schudy Oct 16 '10 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$ – Suresh Venkat Oct 17 '10 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$ – Tsuyoshi Ito Oct 17 '10 at 10:55
  • $\begingroup$ @Tsuyoshi fair enough. I'll add my comments on meta $\endgroup$ – Suresh Venkat Oct 17 '10 at 17:05

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 '10 at 12:35

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