transreduction

Redução transitiva de um grafo direcionado acíclico.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

R = transreduction(G)

Descrição

Uma aresta u -> v é redundante quando já existe outro caminho de u a v. A redução transitiva remove todas as arestas redundantes, preservando quais nós alcançam quais.

Ela é o inverso de transclosure no sentido de que ambos os grafos têm o mesmo fecho. Um uso típico é desenhar um diagrama de dependências sem excesso de linhas.

Argumentos de entrada

G

Um objeto digraph, normalmente acíclico.

Argumentos de saída

R

Um digraph com os mesmos nós e apenas as arestas que não são implicadas por caminhos mais longos.

Exemplo

Removendo a aresta de atalho 1 -> 3

G = digraph([1 2 1], [2 3 3]);
R = transreduction(G);
R.Edges

ans = 2×1 table

    EndNodes
    ________

     1    2 
     2    3

Veja também

transclosure digraph toposort isdag