<p>As Robin says, you want strongly connected components.  They can be easily found using <a href="http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm" rel="nofollow">Tarjan's algorithm</a>, <a href="http://en.wikipedia.org/wiki/Gabow%27s_algorithm" rel="nofollow">Gabow's algorithm</a>, or several others.</p>

CC BY-SA 2.5
2010-10-18T12:35:01.660Z
Thanks - Strongly Connected Components rings an old (very old) graph theory bell!  That's exactly what I was looking for.
shindigo
CC BY-SA 2.5
2010-10-16T21:56:58.913Z
2010-10-16T21:56:58.913Z
Ian
<p>I am working on GIS project where we are making use of road maps that may contain one-way streets.</p>

<p>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.</p>

<p>Here is an example:</p>

<pre><code>A&lt;----------------------&gt; B
\                        /
 \                      /
  \                    /
   \                  /
    \                /
     \              /
      \            /
       \          /
        \        /
         \      /  
         v     v
            C
</code></pre>

<p>In this case the islands are {c} and {a,b}.</p>

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

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

CC BY-SA 2.5
2010-10-15T19:13:37.730Z
If I interpret correctly, you are looking for [strongly connected components](http://en.wikipedia.org/wiki/Strongly_connected_component) of a directed graph.
Robin Kothari
CC BY-SA 2.5
2010-10-16T01:17:46.097Z
Not research level.
Warren Schudy
CC BY-SA 2.5
2010-10-17T03:14:50.273Z
I'd like people voting to close to take a look at [this meta discussion](http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions) 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.
Suresh Venkat
CC BY-SA 2.5
2010-10-17T10:55:55.647Z
@Suresh: I had stated in my comments to [John Berryman’s answer](http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions/518#518) 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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-17T17:05:36.530Z
@Tsuyoshi fair enough. I'll add my comments on meta
Suresh Venkat
<ds.algorithms><graph-theory><graph-algorithms><formal-modeling>
Finding islands of vertices in a network of roads containing one-way streets
shindigo
# Finding islands of vertices in a network of roads containing one-way streets

(Asked by: username_0 on 2010-10-15)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, formal-modeling
> **Comments:**
> **username_1**: If I interpret correctly, you are looking for [strongly connected components](http://en.wikipedia.org/wiki/Strongly_connected_component) of a directed graph.  
> **username_2**: Not research level.  
> **username_3**: I'd like people voting to close to take a look at [this meta discussion](http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions) 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.  
> **username_4**: @Suresh: I had stated in my comments to [John Berryman’s answer](http://meta.cstheory.stackexchange.com/questions/514/how-to-model-this-questions/518#518) 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.  
> **username_3**: @Tsuyoshi fair enough. I'll add my comments on meta  

---

## 1 answers

### Answer by username_5 on 2010-10-16. Score: 2 | Accepted answer

As Robin says, you want strongly connected components. They can be easily found using [Tarjan's algorithm](http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm), [Gabow's algorithm](http://en.wikipedia.org/wiki/Gabow%27s_algorithm), or several others.

> **Comments:**
> **username_0**: Thanks - Strongly Connected Components rings an old (very old) graph theory bell!  That's exactly what I was looking for.  

---

