Accelerating the pace of engineering and science

# graphisdag

Test for cycles in directed graph

graphisdag(G)

## Arguments

 G N-by-N sparse matrix that represents a directed graph. Nonzero entries in matrix G indicate the presence of an edge.

## Description

 Tip   For introductory information on graph theory functions, see Graph Theory Functions.

graphisdag(G) returns logical 1 (true) if the directed graph represented by matrix G is a directed acyclic graph (DAG) and logical 0 (false) otherwise. G is an N-by-N sparse matrix that represents a directed graph. Nonzero entries in matrix G indicate the presence of an edge.

## Examples

Testing for Cycles in Directed Graphs

1. Create and view a directed acyclic graph (DAG) with six nodes and eight edges.

```DG = sparse([1 1 1 2 2 3 4 6],[2 4 6 3 5 4 6 5],true,6,6)

DG =

(1,2)        1
(2,3)        1
(1,4)        1
(3,4)        1
(2,5)        1
(6,5)        1
(1,6)        1
(4,6)        1

view(biograph(DG))```

2. Test for cycles in the DAG.

```graphisdag(DG)

ans =

1```
3. Add an edge to the DAG to make it cyclic, and then view the directed graph.

```DG(5,1) = true

DG =

(5,1)        1
(1,2)        1
(2,3)        1
(1,4)        1
(3,4)        1
(2,5)        1
(6,5)        1
(1,6)        1
(4,6)        1

view(biograph(DG))```

4. Test for cycles in the new graph.

```graphisdag(DG)

ans =

0```

Testing for Cycles in a Very Large Graph (Greater Than 20,000 Nodes and 30,000 Edges)

`GO = geneont('live',true);`
2. Convert the geneont object to a matrix.

`CM = getmatrix(GO);`
3. Test for cycles in the graph.

`graphisdag(CM)`

Creating a Random DAG

1. Create and view a random directed acyclic graph (DAG) with 15 nodes and 20 edges.

```g = sparse([],[],true,15,15);
while nnz(g) < 20
edge = randsample(15*15,1); % get a random edge
g(edge) = true;
g(edge) = graphisdag(g);
end
view(biograph(g))```
2. Test for cycles in the graph.

`graphisdag(g)`

## References

[1] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).