Documentation Center

  • Trial Software
  • Product Updates

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

See Also

| | | | | | | | | |

Was this topic helpful?