# Is the graph acyclic?

A Directed Acyclic Graph (DAG) is a type of graph that has no cycles in it. In other words, if there is a link from node A to node B, there exists no path from B to A (via any nodes).

# Challenge

Determine whether the directed graph given as input is acyclic.

# Input

A list of lists of integers representing the links between nodes, where a node is identified by its index in the list.

# Output

Standard I/O for decision problems; generally a truthy value for acyclic graphs, and a falsy one for cyclic graphs. Additionally, your program may halt/not halt to indicate truthy and falsy, if you wish.

# Test Cases

[[1, 2], [3, 4], [5], [], [6], [6], []]


Represents the following graph (where all edges are directed downwards):

        0
/   \
1     2
/ \   /
3  4  5
| /
6


This example is acyclic, so the result should be truthy.

[[1, 3], [2], [0], [1]]


Represents the following graph:

 -----<-----<----
/                \
0 --> 3 --> 1 --> 2
\---->----/


This example is cyclic, so the result should be falsey. (Sorry for my terrible drawing; if this is unclear let me know.)

# Constraints

• No input will ever be invalid; i.e. no node will link to a node that does not exist
• Self loops must be handled ([[0]] is a cyclic graph)

This is , so the fewest bytes in each language wins.

• Very closely related. It could potentially be considered a duplicate, because checking if cycles exist is a core part of that challenge. – Mego May 24 '17 at 5:05
• Is one-indexing acceptable? May we output truthy for cyclic and falsey for acyclic? – Jonathan Allan May 24 '17 at 10:22
• Feel free to use this drawing or modify it to suit you. – Adám May 24 '17 at 10:51
• @Mego I did see that one before posting, but I think this is a much easier challenge – musicman523 May 24 '17 at 15:01
• @JonathanAllan One-indexing is fine. And yes, based on standard I/O for decision problems you may use false for true and true for false. – musicman523 May 24 '17 at 15:03

# Mathematica, 80444030 22 bytes

#//.x_:>#[[Union@@x]]&


Uses 1-based indexing for input. Returns an empty list iff the graph is acyclic.

### Example:

In[1]:= #//.x_:>#[[Union@@x]]&[{{2,3},{4,5},{6},{},{7},{7},{}}]

Out[1]= {}

In[2]:= #//.x_:>#[[Union@@x]]&[{{2,4},{3},{1},{2}}]

Out[2]= {{2, 4}, {3}, {1}, {2}}

In[3]:= #//.x_:>#[[Union@@x]]&[{{1}}]

Out[3]= {{1}}

• Nice job dealing with the strict input format (and I didn't know about LoopFreeGraphQ!). Too badFindCycle@#=={} doesn't save anything over AcyclicGraphQ@#. – Greg Martin May 24 '17 at 5:32
• Can you replace #2[[1]] by #&@@#2? – Greg Martin May 24 '17 at 5:33
• Could you add an explanation? Also, is the +1 just to correct for 0-indexing? If so, it could be eliminated. – ngenisis May 24 '17 at 5:54
• Is there a perhaps short way to convert to adjacency matrix, raise it to a high power, and check if the result is zero? – xnor May 24 '17 at 7:38
• @xnor The graph is acyclic if and only if the only eigenvalue of its adjacency matrix is 0. But I can't find any short way. f@g_:={0}==Union@Eigenvalues[SparseArray[#+1->1&/@#,Length@g]&/@g] is 66 chars. – alephalpha May 24 '17 at 8:38

# Python 2, 70 bytes

f=lambda G,s=0,v=-1:G[s:]and all(f(G,s+1,x)for x in(G+[sum(G,[])])[v])


Try it online!

An n-vertex graph is cyclic only if one can take an n-step path. In an acyclic graph, no vertex on the path can repeat so it must hit a dead end.

This recursive function tries all paths in the graph G, tracking the current number of steps s and current vertex v. Once s is at least len(G), we the Falsey value of [] is returned. To allow the walk to start on any vertex, the initial phantom vertex v=-1 connects to every (reachable) node of G, extracted as sum(G,[]).

An iterative version tied in length.

Python 2, 70 bytes

G=input()
r=sum(G,[])
for _ in G:r=sum([G[v]for v in r],[])
print[]==r


Try it online

# Jelly,  8  7 bytes

µị³FµL¡


A full program, printing no output for an acyclic input; or some output for a cyclic input.

Try it online!

### How?

µị³FµL¡ - Main link: list of lists of natural numbers, g
µ   µ ¡ - repeat
L  - length times:
³     -   program's 3rd command line argument, 1st program input, g
ị      -   index into
F    -   flatten (makes a list of nodes that are reachable, possibly with repeats)
- implicit print - If cyclic:  it contains integers, and the Jelly representation
is a [] enclosed ,  separated string of them.
If acyclic: it contains nothing, anf the Jelly representation
is an empty string (the [] is not even printed)

• The result should be falsy for cyclic instances. – isaacg May 25 '17 at 3:59
• I asked about it and got this response. – Jonathan Allan May 25 '17 at 4:02

# Haskell, 28 bytes (halts or doesn’t halt)

f g|let s=(>>=s.(g!!))=g>>=s


Try it online!

For any list xs of nodes, s xs = xs >>= s . (g !!) = [y | x <- xs, y <- s (g !! x)] does a recursive search through all nodes reachable from them. We run this on all nodes in the graph with g >>= s.

# Haskell, 36 bytes (returns True or False)

f g=null$foldr(=<<)(id=<<g)$(g!!)<$g  Try it online! For any list xs of nodes, (g!!) =<< xs = [y | x <- xs, y <- g !! x] is the list of endpoints of all edges starting at nodes in xs. Now if g has length n, then foldr(=<<)(id=<<g)$(g!!)<\$g
= foldr (=<<) (id =<< g) [(g!!), (g!!), …, (g!!), (g!!)] (n repetitions)
= (g!!) =<< (g!!) =<< … =<< (g!!) =<< (g!!) =<< id =<< g
= (g!!) =<< (g!!) =<< … =<< (g!!) =<< (g!!) =<< concat g
= (g!!) =<< (g!!) =<< … =<< (g!!) =<< (g!!) =<< [endpoints of all edges, i.e., paths of length 1]
= (g!!) =<< (g!!) =<< … =<< (g!!) =<< [endpoints of all paths of length 2]
= …
= (g!!) =<< [endpoints of all paths of length n]
= [endpoints of all paths of length n + 1],

which is null if and only if the graph is acyclic.

## Mathematica, 82 bytes

AcyclicGraphQ[g=Graph[Join@@Thread/@Thread[Range@Length@#->#]]]&&LoopFreeGraphQ@g&


# APL (Dyalog Classic), 20 bytes

⍳∘≢∨.∊⊂{⍵∪∊⍺[⍵]}⍣≡¨⊢


Try it online!

# Python 2, 53 bytes

f=lambda i:map(f,l[i]);l=input();map(f,range(len(l)))


Crashes if and only if the graph is cyclic, due to infinite recursion. Takes input via stdin.

Try it online!

• This doesn't work for [[], [2], [1]] (aside from the dubious interpretation of I/O rules). – xnor May 24 '17 at 19:31
• Thanks, I knew I was missing something. This should work now, though it is significantly longer. – musicman523 May 24 '17 at 22:26
• I think this still doesn't work, like for [[],[0]]. – xnor May 24 '17 at 22:35
• You are correct. I was trying to over-zealously golf my fix, which caused that issue. Now it really should work, for real :) – musicman523 May 24 '17 at 22:44
• I don't like infinite recursion as an output method. In particular, this will also crash on a sufficiently large acyclic graph. – isaacg May 25 '17 at 3:53

## JavaScript (ES6), 98 bytes

f=(a,b=[...a.keys()],c=b.filter(i=>b.some(b=>a[b].some(b=>b==i))))=>1/b[c.length]?f(a,c):!(1/c[0])


Returns true for acyclic, false for cyclic. Explanation: Starting with the set b of all the nodes in a, the subset of all nodes of b which are the target of a link is iterated until it doesn't change. If the resulting subset is empty then the graph is acyclic.