Bioinformatics Toolbox™

graphisdag - Test for cycles in directed graph

Syntax

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 in the Bioinformatics Toolbox User's Guide.

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

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))

Test for cycles in the DAG.
```
graphisdag(DG)

ans =

     1
```

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))

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)

Download the Gene Ontology database to a geneont object.
```
GO = geneont('live',true);
```
Convert the geneont object to a matrix.
```
CM = getmatrix(GO);
```
Test for cycles in the graph.
```
graphisdag(CM)
```

Creating a Random DAG

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))

Test for cycles in the graph.
```
graphisdag(g)
```

References