# Find all reachable nodes in a graph

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: , 4:}


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: , 4:}
s=1

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


Fewest characters wins. I will clarify if needed.

# 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
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"] • Not sure. Methinks it's m = {{0, 1, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 0}}; ConnectedComponents[AdjacencyGraph[m, DirectedEdges -> True], 1] – Dr. belisarius Apr 20 '14 at 6:18
• I'll check and get back to you. – DavidC Apr 20 '14 at 12:28
• Nope. Mine is wrong. Not sure about yours. – Dr. belisarius Apr 20 '14 at 15:48
• This seems to work: m = {{0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 1, 0}}; VertexOutComponent[AdjacencyGraph@m, 3, Infinity]. The DirectedEdges -> True isn't needed. – Dr. belisarius Apr 20 '14 at 15:55
• Nah, I think one Mma answer per Q is enough. Please be my guest to use the code if that fits you :) – Dr. belisarius Apr 20 '14 at 20:27

### 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 [2 3]][2 ][3 ][4 ]] C # returns [1 2 3]  • You can get a reasonable saving with a filter. The best I've got so far is to replace the inner loop with G{1$&},{~||}/ – Peter Taylor Apr 19 '14 at 10:41
• @PeterTaylor Thank you. I was working on a different approach (.{{&}+G?)||}/) which has the same character count but I find your's a bit nicer. – Howard Apr 19 '14 at 13:15

# 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


# 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: , 3: [0, 2], 4:}
+---+-----+-+---+-+
|2 4|1 2 4|0|0 2|1|
+---+-----+-+---+-+
'';2 3;3;1;2        NB. {1: [2, 3], 2: , 3: , 4:}
++---+-+-+-+
||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
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 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.

# APL (Dyalog Extended), 7 bytes

⌂search


Try it online!

A library function that does the job. Takes the graph on its left and the start node on its right, and gives the list of reachable nodes using breadth-first search.

Since APL has neither sets nor dicts, the closest input format is a nested vector of vectors like (2 3)(3)(1)(2). And, just by coincidence, Dyalog APL's graph library uses this exact format as the representation for graphs.

Because a built-in is boring, here is another solution without it (which is still short):

# APL (Dyalog Unicode), 10 bytes

(∪/⊢,⌷⍨)⍣≡


Try it online!

Same input format and left/right argument order. Returns the same result, but nested once. Keeping one level of nesting throughout the ⍣≡-loop gives several advantages in terms of golfing.

### How it works

(∪/⊢,⌷⍨)⍣≡  ⍝ Tacit infix function. left←graph, right←node
(      )⍣≡  ⍝ Repeat until the right arg converges...
⌷⍨     ⍝ Simulate following all possible edges from input node(s)
⍝ which gives a vector of nested vectors of nodes
⊢,       ⍝ Prepend the (nested) list of initial nodes
∪/         ⍝ Reduce by set union;
⍝ preserve the order of existing nodes by
⍝ having the input on the left end

Example run:
graph←(2 3)(3)(1)(2) ⋄ node←1
First iteration:
⌷⍨     ⊂2 3  ⍝ extract index 1 of graph
⊢,       1(2 3)
∪/         ⊂1 2 3
(      )⍣≡  Converged? No.
Second iteration:
⌷⍨     (2 3)(3)(1)  ⍝ extract indices 1, 2, 3 of graph
⊢,       (1 2 3)(2 3)(3)(1)
∪/         ⊂1 2 3
(      )⍣≡  Converged? Yes, stop.


## 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: , 4:}
>>> s=1
>>> from networkx import*
>>> single_source_shortest_path(DiGraph(G),s).keys()
[1, 2, 3]

• networkx is not really core Python. – isaacg Apr 23 '14 at 9:40
• @isaacg: I do not see any restriction to use core Python. It is an accepted practice in this forum to use libraries unless it is explicitly restricted. So I disagree with your comment and downvote. – Abhijit Apr 23 '14 at 11:54
• Is that so? I must have been unclear on the accepted practice of the forum. I will remove my downvote at the next opportunity. – isaacg Apr 23 '14 at 11:57

# 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: , 4:}
s=1
f(G,s)


Returns a set containing:

1,2,3


# 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}

• This is an awesome solution. I don't understand Mathematica, though. Could you explain? – isaacg Apr 23 '14 at 9:10

# 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: , 4:}
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.

• I would allow this method, but charge you six characters for the empty set - A={[]} - and seven characters for the print A line, for a total of 67 characters. YMMV, though. – isaacg Apr 22 '14 at 5:25
• @isaacg: I accept the charge for the empty set, but why the charge for printing? Would you also charge this for a function, which returns the set/list/… in a “regular” manner? – Wrzlprmft Apr 22 '14 at 13:29
• A return value would not be charged for. Eh - it's rather borderline, I could see the A value being free. The issue I see is that you essentially just saved the output to a variable, not returned or output it. – isaacg Apr 22 '14 at 17:48

## 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.

• You can shave 2 characters and make it even more inefficient by changing the empty list to r and += to +. – isaacg Apr 20 '14 at 23:56
• I mean += to =. – isaacg Apr 21 '14 at 0:01
• You can shave another character by changing the for loop to and exec statement and one-lining it: def R(g,s):r=[s];exec'r=sum((G[x]for x in r),r);'*len(G);print set(r) – isaacg Apr 21 '14 at 0:05

# 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

• This should be the accepted answer... – cat Apr 10 '16 at 16:31

import Data.List
n#v=nub$id=<<length ntakeiterate(>>=(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 ntake  concatenate the result  id=<<  and finally remove all the duplicates nub$


.

## 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 , 4 } 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.

# 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).