Exponenta Banner

graphisdag

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

Синтаксис

graphisdag(G)

Аргументы

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

Описание

Совет

Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».

graphisdag(G) возвращает логический 1 (true), если ориентированный граф представлен матрицей G является ориентированным ациклическим графиком (DAG) и логическим 0 (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. Тест на циклы в ДАГ.

    graphisdag(DG)

ans =

     1

  3. Добавьте ребро в ДАГ, чтобы сделать его циклическим, и затем просмотрите ориентированный график. 

    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. Преобразуйте объект генеонта в матрицу.

    CM = getmatrix(GO);

  3. Тест на циклы в графике.

    graphisdag(CM)
Пример 35. Создание случайной ДАГ

  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., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).

См. также

| | | | | | | | | |

Введенный в R2006b

Документация по Bioinformatics Toolbox

Поддержка