`isdag`

Tests whether a digraph is a directed acyclic graph.

Category: Mathematics > Graph and Network Algorithms

Syntax

tf = isdag(D)

Returns true if D has no directed cycle.

Description

A DAG has an ordering of its nodes in which every edge points forward, which is the structure of task dependencies, build systems and course prerequisites. The test fails as soon as a directed cycle exists, even a long one.

isdag(D) is the same as ~hascycles(D).

Input arguments

D: A digraph.

Output arguments

tf: Logical scalar.

Example

Chain versus loop

isdag(digraph([1 2], [2 3]))
isdag(digraph([1 2 3], [2 3 1]))

Output

ans = logical
   1
ans = logical
   0

isdag