graphisdag

Протестируйте на циклы в ориентированном графе

Синтаксис

graphisdag(G)

Аргументы

G N на n разреженная матрица, которая представляет ориентированного графа. Ненулевые записи в матричном G укажите на присутствие ребра.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

graphisdag(G) возвращает логическую единицу (true) если ориентированный граф представлен матричным G направленный граф без петель (DAG) и логический ноль (false) в противном случае. G N на n разреженная матрица, которая представляет ориентированного графа. Ненулевые записи в матричном G укажите на присутствие ребра.

Примеры

Пример 33. Тестирование на циклы в ориентированных графах
  1. Создайте и просмотрите направленный граф без петель (DAG) с шестью узлами и восемью ребрами.

    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. Протестируйте на циклы в DAG.

    graphisdag(DG)
    
    ans =
    
         1
  3. Добавьте ребро в DAG, чтобы сделать его циклическим, и затем просмотреть ориентированного графа.

    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. Протестируйте на циклы в новом графике.

    graphisdag(DG)
    
    ans =
    
         0
Пример 34. Тестирование на циклы в очень Большом графике (Больше, чем 20 000 узлов и 30 000 ребер)
  1. Загрузите базу данных Gene Ontology на объект geneont.

    GO = geneont('live',true);
  2. Преобразуйте объект geneont в матрицу.

    CM = getmatrix(GO);
  3. Протестируйте на циклы в графике.

    graphisdag(CM)
Пример 35. Создание случайного DAG
  1. Создайте и просмотрите случайный направленный граф без петель (DAG) с 15 узлами и 20 ребрами.

    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. Протестируйте на циклы в графике.

    graphisdag(g)

Ссылки

[1] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

Представленный в R2006b
Для просмотра документации необходимо авторизоваться на сайте