7
\$\begingroup\$

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.

\$\endgroup\$

13 Answers 13

8
\$\begingroup\$

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"]

graph

\$\endgroup\$
  • \$\begingroup\$ 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] \$\endgroup\$ – Dr. belisarius Apr 20 '14 at 6:18
  • \$\begingroup\$ I'll check and get back to you. \$\endgroup\$ – DavidC Apr 20 '14 at 12:28
  • \$\begingroup\$ Nope. Mine is wrong. Not sure about yours. \$\endgroup\$ – Dr. belisarius Apr 20 '14 at 15:48
  • \$\begingroup\$ 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. \$\endgroup\$ – Dr. belisarius Apr 20 '14 at 15:55
  • 1
    \$\begingroup\$ Nah, I think one Mma answer per Q is enough. Please be my guest to use the code if that fits you :) \$\endgroup\$ – Dr. belisarius Apr 20 '14 at 20:27
4
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ 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$&},{~||}/ \$\endgroup\$ – Peter Taylor Apr 19 '14 at 10:41
  • \$\begingroup\$ @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. \$\endgroup\$ – Howard Apr 19 '14 at 13:15
4
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ networkx is not really core Python. \$\endgroup\$ – isaacg Apr 23 '14 at 9:40
  • \$\begingroup\$ @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. \$\endgroup\$ – Abhijit Apr 23 '14 at 11:54
  • \$\begingroup\$ Is that so? I must have been unclear on the accepted practice of the forum. I will remove my downvote at the next opportunity. \$\endgroup\$ – isaacg Apr 23 '14 at 11:57
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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}

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – isaacg Apr 22 '14 at 5:25
  • \$\begingroup\$ @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? \$\endgroup\$ – Wrzlprmft Apr 22 '14 at 13:29
  • \$\begingroup\$ 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. \$\endgroup\$ – isaacg Apr 22 '14 at 17:48
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can shave 2 characters and make it even more inefficient by changing the empty list to r and += to +. \$\endgroup\$ – isaacg Apr 20 '14 at 23:56
  • \$\begingroup\$ I mean += to =. \$\endgroup\$ – isaacg Apr 21 '14 at 0:01
  • \$\begingroup\$ 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) \$\endgroup\$ – isaacg Apr 21 '14 at 0:05
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This should be the accepted answer... \$\endgroup\$ – cat Apr 10 '16 at 16:31
0
\$\begingroup\$

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$

.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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