7
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Very closely related. It could potentially be considered a duplicate, because checking if cycles exist is a core part of that challenge. \$\endgroup\$
    – user45941
    Commented May 24, 2017 at 5:05
  • 1
    \$\begingroup\$ Is one-indexing acceptable? May we output truthy for cyclic and falsey for acyclic? \$\endgroup\$
    – Jonathan Allan
    Commented May 24, 2017 at 10:22
  • 1
    \$\begingroup\$ Feel free to use this drawing or modify it to suit you. \$\endgroup\$
    – Adám
    Commented May 24, 2017 at 10:51
  • \$\begingroup\$ @Mego I did see that one before posting, but I think this is a much easier challenge \$\endgroup\$
    – musicman523
    Commented May 24, 2017 at 15:01
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – musicman523
    Commented May 24, 2017 at 15:03

8 Answers 8

Reset to default
8
\$\begingroup\$

Mathematica, 80 44 40 30 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}}
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Nice job dealing with the strict input format (and I didn't know about LoopFreeGraphQ!). Too badFindCycle@#=={} doesn't save anything over AcyclicGraphQ@#. \$\endgroup\$
    – Greg Martin
    Commented May 24, 2017 at 5:32
  • \$\begingroup\$ Can you replace #2[[1]] by #&@@#2? \$\endgroup\$
    – Greg Martin
    Commented May 24, 2017 at 5:33
  • \$\begingroup\$ Could you add an explanation? Also, is the +1 just to correct for 0-indexing? If so, it could be eliminated. \$\endgroup\$
    – user61980
    Commented May 24, 2017 at 5:54
  • \$\begingroup\$ Is there a perhaps short way to convert to adjacency matrix, raise it to a high power, and check if the result is zero? \$\endgroup\$
    – xnor
    Commented May 24, 2017 at 7:38
  • \$\begingroup\$ @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. \$\endgroup\$
    – alephalpha
    Commented May 24, 2017 at 8:38
4
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ The result should be falsy for cyclic instances. \$\endgroup\$
    – isaacg
    Commented May 25, 2017 at 3:59
  • \$\begingroup\$ I asked about it and got this response. \$\endgroup\$
    – Jonathan Allan
    Commented May 25, 2017 at 4:02
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Classic), 20 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 82 bytes

AcyclicGraphQ[g=Graph[Join@@Thread/@Thread[Range@Length@#->#]]]&&LoopFreeGraphQ@g&
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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!

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

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.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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