Documentation |
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(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.
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)