Test for cycles in directed graph
graphisdag(
G
)
G | N-by-N sparse matrix that represents a directed graph. Nonzero
entries in matrix G indicate the presence
of an edge. |
Tip For introductory information on graph theory functions, see Graph Theory Functions. |
graphisdag(
returns logical 1 (G
)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.
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)
[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).