Como converter Directed acíclico Graph (DAG) a Árvore

Question

I foram à procura de exemplos de C # para transformar um DAG em uma árvore.

Alguém tem uma exemplos ou ponteiros na direção certa?

Clarificação Atualização

Eu tenho um gráfico que contém uma lista de módulos que o meu pedido é necessário para carga. Cada módulo tem uma lista de módulos que ele depende. Por exemplo, aqui estão os módulos A, B C, D e E

• A não tem dependências
• B depende de A, C e E
• C depende A
• D depende A
• E depende C e A

Quero dependências resolver e gerar uma árvore que se parece com esta ...

- A

- + - B

----- + - C

--------- + - D

- + - E

topológica Sort

Obrigado pela informação, se eu executar uma ordenação topológica e reverter a saída i terão a seguinte ordem

• A
• B
• C
• D
• E

Eu quero manter a estrutura hierárquica para que meus módulos são carregados no contexto correto, por exemplo ... módulo de E deve ser no mesmo recipiente como B

Graças

Rohan

Answer 1

Não é a resposta teórica gráfico e a resposta do programador para isso. Eu suponho que você pode lidar com os programadores separar-se. Para a resposta teórico gráfico:

• A DAG é um conjunto de módulos onde nunca acontece que A precisa B, e, ao mesmo tempo, B (ou uma das necessidades módulos B) precisa A, em módulos-falar: nenhuma dependência circular. Eu vi dependências circulares acontecer (procurar os fóruns do Gentoo para exemplos), para que você não pode mesmo estar 100% certo você tem um DAG, mas vamos supor que você tem. Ele não muito difícil de fazer uma verificação sobre dependências circulares, então eu recomendo que você fazê-lo em algum lugar no seu carregador de módulo.
• Em uma árvore, algo que nunca pode acontecer é que A depende de B e C e que tanto B e C dependem D (um diamante), mas isso pode acontecer em um DAG.
• Além disso, uma árvore tem exatamente um nó raiz, mas um DAG pode ter vários nós "root" (ou seja, módulos que nada depende). Por exemplo, um programa como o GIMP, o programa GIMP será o nó raiz do conjunto de módulos, mas para o Gentoo, quase todo o programa com uma interface gráfica é um nó "raiz", enquanto a bibliotecas etc são dependências deles. (Ou seja, tanto Konqueror e Kmail dependem Qtlib, mas nada depende Konqueror, e nada depende Kmail)

A resposta teórico Graph à sua pergunta, como outros apontaram, é que um DAG não pode ser convertido em uma árvore, enquanto cada árvore é um DAG.

No entanto, (programadores de alto nível de resposta) se você deseja que a árvore para representações gráficas, você está interessado apenas nas dependências de um módulo específico, não o que está de acordo com esse módulo. Deixe-me dar um exemplo:

A depends on B and C
B depends on D and E
C depends on D and F

Eu não posso mostrar isso como uma árvore de ASCII-art, pela simples razão de que isso não pode ser convertida em uma árvore. No entanto, se você quer mostrar o que A depende, você pode mostrar o seguinte:

A
+--B
|  +--D
|  +--E
+--C
   +--D
   +--F

Como você pode ver, você tem entradas duplas em sua árvore - neste caso, "apenas" D mas se você fizer um "expandir tudo" na árvore Gentoo, eu garanto que sua árvore terá pelo menos 1000 vezes a quantidade de nodos como existem módulos. (Há pelo menos 100 pacotes que dependem Qt, por isso tudo Qt depende estará presente pelo menos 100 vezes na árvore).

Se você tem um "grande" ou "complexo" de árvore, pode ser melhor para expandir a árvore de forma dinâmica, não com antecedência, caso contrário, você pode ter um processo muito intensivo de memória.

A desvantagem da árvore acima é que se você clicar aberta B, então D, você vê que A e B dependem D, mas não que também C depende D. No entanto, dependendo da sua situação, isso pode não ser importante em tudo - se você manter uma lista de módulos carregados, aquando do carregamento C você ver que você tem D carregado já, e não importa que não foi carregado para C, mas para B. ele é carregado, isso é tudo que importa. Se você mantém dinamicamente o que depende diretamente de um determinado módulo, você pode lidar com o problema oposto (descarga) também.

No entanto, o que você não pode fazer com uma árvore é o que está em sua frase final: preservar a ordem topológica, ou seja, se B é carregado no mesmo recipiente como C, você nunca vai chegar ao carregar C no mesmo recipiente como bem. Ou você pode ter que ser colocado em colocar tudo em um recipiente (não que eu entender completamente o que você quer dizer com "carregamento no mesmo recipiente")

Boa sorte!

Answer 2

A DAG e uma árvore não são a mesma coisa matematicamente. Assim, qualquer conversão introduz ambiguidade. Uma árvore, por definição, não tem ciclos, período.

Answer 3

O que você está procurando, a fim de encontrar a ordem para carregar seus módulos dentro, é o ordenação topológica do seu DAG. Se as bordas ir de um módulo para os módulos de que depende (que eu acho que é o mais provável), você vai ter que carregar os módulos na ordem inversa da ordenação topológica porque um módulo aparecerá -before- todos os módulos do qual depende.

Se você representa a DAG de tal forma que as bordas vão do dependia de módulos para os módulos que dependem deles (você pode obter este, invertendo todas as arestas no gráfico acima), você pode simplesmente carregar os módulos na ordem do tipo topológico.

Answer 4

Depende muito de como você está representando a sua DAG. Por exemplo, pode ser uma matriz de adjacência (a [i, j] = 1, se há uma borda de nó i para o nó j, mais 0), ou como um sistema de ponteiros, ou como uma matriz de nós e uma matriz de bordas ....

Além disso, não é claro o que a transformação que você está tentando aplicar. A conectado DAG é uma árvore, então eu tenho medo que você precisa esclarecer sua pergunta um pouco.

Answer 5

Você só pode fazer isso se todas as subárvores ter um único nó raiz.