`isdag`

Testa se um dígrafo é um grafo acíclico dirigido.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

tf = isdag(D)

Retorna true se D não tem ciclo dirigido.

Descrição

Um DAG admite uma ordenação dos nós em que toda aresta aponta para frente, que é a estrutura de dependências de tarefas, sistemas de build e pré-requisitos de disciplinas. O teste falha assim que existe um ciclo dirigido, mesmo longo.

isdag(D) equivale a ~hascycles(D).

Argumentos de entrada

D: Um digraph.

Argumentos de saída

tf: Escalar lógico.

Exemplo

Corrente contra laço

isdag(digraph([1 2], [2 3]))
isdag(digraph([1 2 3], [2 3 1]))

Saída

ans = logical
   1
ans = logical
   0

Veja também

hascycles condensation conncomp digraph