2
$\begingroup$

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
            C

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?

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ If I interpret correctly, you are looking for strongly connected components of a directed graph. $\endgroup$
    – Robin Kothari
    Commented Oct 15, 2010 at 19:13
  • $\begingroup$ Not research level. $\endgroup$
    – Warren Schudy
    Commented 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$
    – Suresh Venkat
    Commented 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$
    – Tsuyoshi Ito
    Commented Oct 17, 2010 at 10:55
  • $\begingroup$ @Tsuyoshi fair enough. I'll add my comments on meta $\endgroup$
    – Suresh Venkat
    Commented Oct 17, 2010 at 17:05

1 Answer 1

Reset to default
2
$\begingroup$

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

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

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