Documentation

This is machine translation

Translated by Microsoft
Mouse over text to see original. Click the button below to return to the English verison of the page.

graphisdag

Test for cycles in directed graph

Syntax

graphisdag(G)

Arguments

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

Description

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)

  1. Download the Gene Ontology database to a geneont object.

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

Introduced in R2006b

Was this topic helpful?