Find all reachable nodes in a graph

Question

You are given a directed graph in an adjacency dictionary format. This can be whatever format is most natural for your language. For instance, in python, this would be a dictionary with keys of nodes and values which are lists of nodes which that node has an edge to. For instance:

G={1: [2, 3], 2: [3], 3: [1], 4:[2]}

Be reasonable. A dictionary of frozen sets is not allowed, even if it makes your code shorter. A list of lists is fine, if your language doesn't have dictionaries.

Your task is to implement a function that takes a directed graph and a starting node, and outputs all nodes reachable from the starting node. The output format is also flexible. A return value from a function is fine, so is print, etc.

Test case:

G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
s=1

R(G,s)
{1,2,3}

Fewest characters wins. I will clarify if needed.

Answer 1

Mathematica 63 40 37

My earlier submission was incorrect. I had misinterpreted what ConnectedComponents returns. The present approach relies on Belisarius' suggestion to useVertexOutComponent. 3 additional chars saved by alephalpha.

The following generates an 11 by 11 adjacency matrix of 0's and 1's, where 1 indicates that the vertex with the row number is connected directly to the vertex corresponding to column number of the cell. (SeedRandom ensures that your matrix a will match mine.)

SeedRandom[21]
a = Array[RandomChoice[{0.9, 0.1} -> {0, 1}] &, {11, 11}];

---

Example

(37 chars)

 AdjacencyGraph@a~VertexOutComponent~4

{4, 1, 7, 8, 9, 3}

---

Verifying

The directed graph displays how to reach vertices {1, 7, 8, 9, 3} from vertex 4.

AdjacencyGraph[a, ImagePadding -> 30, VertexLabels -> "Name"]

Answer 2

Python 2.7 - 80 65

def R(G,s):
 k=a={s}
 while k:a=a|k;k|=set(G[k.pop()])-a
 print a

Answer 3

GolfScript, 27 24 characters

{:G,{G{1$&},{)||}/}*}:C;

This code implements the operator C which takes starting node and graph on the stack and leaves a list of reachable notes on the stack after execution.

Example (online):

[1] [[1 [2 3]][2 [3]][3 [1]][4 [2]]] C
# returns [1 2 3]

Answer 4

J - 19 15 char

J doesn't have a dictionary type, and is generally garbage with representing things the way people are used to in other languages. This is a bit idiosyncratic with how it represents things, but that's because J and graphs don't blend well, and not because I'm looking for optimal ways of representing directed graphs. But even if it doesn't count, I think it's a concise, interesting algorithm.

~.@(],;@:{~)^:_

This is a function which takes a graph on the left and a list of nodes to start with on the right.

Graphs are lists of boxed lists, and the nodes are indices into the list that represents the graph. J indexes from zero, so nodes are nonnegative integers, but you can skip 0 and pretend to have 1-based indexing by using an empty list ('') in the 0 place. (Indented lines are input to the J console, lines flush with the margin are output.)

   2 4;1 2 4;0;0 2;1   NB. {0: [2, 4], 1: [1, 2, 4], 2: [0], 3: [0, 2], 4:[1]}
+---+-----+-+---+-+
|2 4|1 2 4|0|0 2|1|
+---+-----+-+---+-+
   '';2 3;3;1;2        NB. {1: [2, 3], 2: [3], 3: [1], 4:[2]}
++---+-+-+-+
||2 3|3|1|2|
++---+-+-+-+
   '';'';2;9;1 7 8 9;3 6;4 8;7;'';3;'';7   NB. the big Mathematica example
+++-+-+-------+---+---+-++-++-+
|||2|9|1 7 8 9|3 6|4 8|7||3||7|
+++-+-+-------+---+---+-++-++-+

Lists of numbers are just space-separated lists of numbers. In general a scalar (just one number in a row) is not the same as a one-item list, but I use only safe operations that end up promoting scalars to one-item lists, so everything's cool.

The function explained (supposing we invoke as graph ~.@(],;@:{~)^:_ nodes):

• {~ - For each node in nodes, take the list of adjacent nodes from graph.
• ;@: - Turn the list of adjacencies into a list of nodes.
• ], - Prepend nodes to this list.
• ~.@ - Throw out any duplicates.
• ^:_ - Repeat this procedure with the same graph until it results in no change to the right hand argument, i.e. there are no new nodes to discover.

The verb in action:

   ('';2 3;3;1;2) ~.@(],;@:{~)^:_ (1)           NB. example in question
1 2 3
   f =: ~.@(],;@:{~)^:_                         NB. name for convenience
   (2 4;1 2 4;0;0 2;1) f 2
2 0 4 1
   ('';'';2;9;1 7 8 9;3 6;4 8;7;'';3;'';7) f 4  NB. Mathematica example
4 1 7 8 9 3

If you don't like this graph representation, here's a couple quick verbs for converting to/from adjacency matrices.

   a=:<@#i.@#        NB. adj.mat. to graph
   mat=:0,0,.0 1 1 0,0 0 1 0,1 0 0 0,:0 1 0 0
   mat               NB. adj.mat. for {1:[2,3],2:[3],3:[1],4:[2]}
0 0 0 0 0
0 0 1 1 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0
   a mat
++---+-+-+-+
||2 3|3|1|2|
++---+-+-+-+
   A=:+/@:=&>/i.@#   NB. graph to adj.mat.
   A a mat
0 0 0 0 0
0 0 1 1 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0

For anyone wondering why the graph is the left argument to the verb, it's because that's the general convention in J: control information on the left, data on the right. Consider list search, list i. item, and the sequential machine dyad, machine ;: input.

Answer 5

Python 2.7 (using networkx) - 71

from networkx import*
single_source_shortest_path(DiGraph(G),s).keys()

Sample Run

>>> G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
>>> s=1
>>> from networkx import*
>>> single_source_shortest_path(DiGraph(G),s).keys()
[1, 2, 3]

Answer 6

JavaScript (ECMAScript 6) - 70 Characters

f=(G,s)=>{y=Set([s]);y.forEach(x=>G[x].forEach(z=>y.add(z)));return y}

Test

G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
s=1
f(G,s)

Returns a set containing:

1,2,3

Answer 7

Mathematica, 29 chars

{s}//.l_List:>(l⋃##&@@(l/.G))

Example:

G = {1 -> {2, 3}, 2 -> {3}, 3 -> {1}, 4 -> {2}}; s = 1;
{s}//.l_List:>(l⋃##&@@(l/.G))

{1, 2, 3}

Answer 8

Python – 54 52 + 7 + 7

def R(G,s,A):
    A|={s}
    for n in set(G[s])-A:R(G,n,A)

R needs to be called with an empty set as an additional argument. This set contains the output, when R has finished. Example of usage:

G = {1: [2, 3], 2: [3], 3: [1], 4:[2]}
A=set()
R(G,1,A)
print A

If you consider this way of output cheating, keep in mind that it’s very normal in C, for example. Anyway, you may want to charge 7 additional chars for the intialisation of the empty set (A=set()) and 7 for the print line.

Answer 9

Haskell, 64 bytes

import Data.List
n#v=nub$id=<<length n`take`iterate(>>=(n!!))[v]

Takes input as a zero-based list of lists, try it online!

Explanation / Ungolfed

The term vertices >>= (adjacencyList !!) takes a list of vertices, looks up all reachable vertices of them and returns them as a list.

So we repeatedly do this starting with the input vertex [v]

                       iterate(>>=(n!!))[v]

take as many elements from that list as there are nodes in the graph

         length n`take`

concatenate the result

    id=<<

and finally remove all the duplicates

nub$

.

Answer 10

Java 10, 130 characters

A curried lambda that takes the graph as a Map<Integer, List<Integer>> and an int start node. Output is returned as a Set<Integer>.

import java.util.*;

g->s->{var o=new TreeSet();o.add(s);for(var x:g.keySet())for(var n:new TreeSet(o))o.addAll(g.get(n));return o;}

Try It Online

This carries out a slightly stupid breadth-first search just past a maximum possible non-cyclical path length (the number of graph nodes).

Answer 11

Clojure, 52 bytes

#(nth(iterate(fn[A](set(mapcat % A)))[%2])(count %))

This implicitly assumes that all nodes have outgoing vertices.

54 bytes

#(loop[A[%2]B[]](if(= A B)A(recur(set(mapcat % A))A)))

The nifty part is the (mapcat % A), which uses the input argument {1 [2, 3], 2 [3], 3 [1], 4 [2]} as a function (given a key it returns the corresponding value) and concatenates all the ids together. Then it is just a matter of iterating this procedure until we have converged.

Answer 12

Python, 72 chars

def R(G,s):
 r=[s]
 for i in G:r+=sum((G[x]for x in r),[])
 print set(r)

Terribly inefficient because nodes can appear in r multiple times. Fortunately, not a judging criterion.

Answer 13

K4 , 12 bytes

The code is:

{?,/x,G x}/1

Here's an example of its use:

  G:1 2 3 4!(2 3;3;1;2)
  {?,/x,G x}/1
1 2 3
  H:(!12)!(();();2;9;1 7 8 9;3 6;4 8;7;();3;();7)
  {?,/x,H x}/4
4 1 7 8 9 3

input is a dictionary from int to int or list of int

the basic op is G s, retrieve the child nodes for s

this is then stuffed into the built-in convergence operator /

the rest is to, at each stage, prepend the parent node, flatten the results down to a vector, and dedupe them -- this is needed to make the answer actually converge

btw, for an extra three characters, you can have all the reachability lists:

  {G(?,/,)'G x}/G
1 2 3 4!(2 3 1;3 1 2;1 2 3;2 3 1)
  {H(?,/,)'H x}/H
0 1 2 3 4 5 6 7 8 9 10 11!(();();,2;9 3;1 7 8 9 3;3 6 9 4 8 1 7;4 8 1 7 9 3;,7;();3 9;();,7)

this is the same general idea, applied to the basic op of G G