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.

\$\endgroup\$
  • 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\$ – Mego May 24 '17 at 5:05
  • 1
    \$\begingroup\$ Is one-indexing acceptable? May we output truthy for cyclic and falsey for acyclic? \$\endgroup\$ – Jonathan Allan May 24 '17 at 10:22
  • 1
    \$\begingroup\$ Feel free to use this drawing or modify it to suit you. \$\endgroup\$ – Adám May 24 '17 at 10:51
  • \$\begingroup\$ @Mego I did see that one before posting, but I think this is a much easier challenge \$\endgroup\$ – musicman523 May 24 '17 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 May 24 '17 at 15:03
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}}
\$\endgroup\$
  • \$\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 May 24 '17 at 5:32
  • \$\begingroup\$ Can you replace #2[[1]] by #&@@#2? \$\endgroup\$ – Greg Martin May 24 '17 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\$ – ngenisis May 24 '17 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 May 24 '17 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 May 24 '17 at 8:38
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

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

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

Mathematica, 82 bytes

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

APL (Dyalog Classic), 20 bytes

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

Try it online!

\$\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!

\$\endgroup\$
  • \$\begingroup\$ This doesn't work for [[], [2], [1]] (aside from the dubious interpretation of I/O rules). \$\endgroup\$ – xnor May 24 '17 at 19:31
  • \$\begingroup\$ Thanks, I knew I was missing something. This should work now, though it is significantly longer. \$\endgroup\$ – musicman523 May 24 '17 at 22:26
  • \$\begingroup\$ I think this still doesn't work, like for [[],[0]]. \$\endgroup\$ – xnor May 24 '17 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 May 24 '17 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 May 25 '17 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.

\$\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.