Visualização de gráfico de dependência

22

O objetivo desse desafio é escrever um programa que visualize um gráfico de dependência na forma de uma árvore. Embora "gráfico de dependência" nesse contexto signifique nada mais que um gráfico direcionado, o método de visualização descrito aqui funciona melhor para gráficos que descrevem alguma relação de dependência (como exercício, depois de ler o desafio, tente reverter a direção de um dos os gráficos de exemplo e veja se o resultado é tão útil.)

A entrada para o programa consiste em uma ou mais definições de destino , que são linhas do formato

Target DirectDependency1 DirectDependency2 ...

, definindo um destino e suas dependências diretas associadas , se houver. Os alvos e suas dependências são chamados coletivamente de objetos . Se um objeto aparecer apenas como uma dependência e não como um destino, ele não terá dependências. O conjunto de todos os objetos que aparecem na entrada é chamado Γ . (Consulte a seção Entrada e saída para obter mais detalhes sobre o formato de entrada.)

Para qualquer par de objetos, A e B , dizemos que:

  • A depende de B (equivalentemente, B é requerido por A ), se A depender diretamente de B ou se A depender diretamente de B ' , e B' depender de B , para algum objeto B ' ;
  • Um depende adequadamente em B (de modo equivalente, B é adequadamente exigido por um ), se A depende de B , e B não depende de uma .

Definimos um objeto artificial, ʀooᴛ , não em Γ, de modo que ʀooᴛ não seja diretamente solicitado por nenhum objeto, e de modo que, para todos os objetos A , dependsooᴛ dependa diretamente de A se, e somente se A estiver em Γ, e A não for adequadamente exigido por qualquer objeto em Γ (em outras palavras, ʀooᴛ depende diretamente de A se nenhum outro objeto depender de A ou se todos os objetos que dependem de A também forem solicitados por A. )

Árvore de saída

Construímos uma árvore , cujo nó raiz é ʀooᴛ, e de modo que os filhos de cada nó sejam suas dependências diretas. Por exemplo, dada a entrada

Bread Dough Yeast
Dough Flour Water
Butter Milk

, a árvore resultante é

Exemplo de árvore de saída

ou, no formato ASCII,

ʀooᴛ
+-Bread
| +-Dough
| | +-Flour
| | +-Water
| +-Yeast
+-Butter
  +-Milk

. A saída do programa é a árvore acima definida, impressa sem o nó ʀooᴛ. Assim, por exemplo, a saída correspondente para a entrada acima é

Bread
+-Dough
| +-Flour
| +-Water
+-Yeast
Butter
+-Milk

. Uma descrição detalhada do layout da árvore de saída é fornecida posteriormente.

Ordem do nó

Os nós filhos de um determinado nó pai, P , devem ser classificados , de modo que, para todos os nós filhos A e B de P , A apareça antes de B se e somente se

  • existe um nó filho C de P , de modo que A seja adequadamente requerido por C e C preceda, ou seja igual a B , de acordo com a mesma ordem; ou ,
  • A precede alfabeticamente B (mais precocemente, A precede B usando agrupamento ASCII) e não existe um nó filho C de P , de modo que B seja adequadamente requerido por C e C preceda ou seja igual a A , de acordo com a mesma ordem .

(Pessoas que procuram um desafio matemático podem querer mostrar que essa relação está bem definida e que é, de fato, uma ordem total estrita. Não se esqueça que Γ é finito!)

Por exemplo, dada a entrada

X D C B A
B D
C A

, a saída deve ser

X
+-A
+-D
+-B
| +-D
+-C
  +-A

. Aaparece antes Be Baparece antes C, devido à sua ordem alfabética; Daparece antes B, pois é adequadamente requerido por ele e depois A, desde que o segue em ordem alfabética; Be Cnão aparecem antes D, mesmo que o precedam em ordem alfabética, uma vez que existe um nó, a saber, Bque requer adequadamente De que é igual a B(ou seja, ele próprio) e precede C, de acordo com as mesmas regras.

Repetições

O mesmo objeto, A , pode aparecer mais de uma vez na saída, se, por exemplo, for exigido por mais de um objeto. Se A não tiver dependências próprias, nenhum tratamento especial será necessário nesse caso. Caso contrário, para minimizar a verbosidade da saída e evitar recursões infinitas devido a dependências circulares, as dependências de A são listadas apenas em sua primeira ocorrência para a qual nenhum dos ancestrais é irmão de outro nó A ; qualquer outra ocorrência de A não deve ter filhos e deve aparecer seguida por um espaço e uma elipse, como em .A...

Por exemplo, dada a entrada

IP Ethernet
TCP IP
UDP IP
WebRTC TCP UDP

, a saída deve ser

WebRTC
+-TCP
| +-IP
|   +-Ethernet
+-UDP
  +-IP ...

. Como outro exemplo, apresentando considerações de dependência circular e de ancestralidade,

Rock Scissors
Paper Rock
Scissors Paper

, deve resultar em

Paper
+-Rock ...
Rock
+-Scissors ...
Scissors
+-Paper ...

. Observe que, por exemplo, a primeira ocorrência de Rocknão lista suas dependências, pois seu pai Paper, é irmão de outro Rocknó. O pai do segundo Rocknó, ʀooᴛ (que não aparece na saída), não tem Rockcomo irmão, portanto, as dependências de Rocksão listadas nesse nó.

Layout da árvore de saída

Tenho certeza que você entendeu como a árvore deve ser representada como arte ASCII (e fique à vontade para pular esta seção, se tiver), mas por uma questão de perfeição ...

Os nós filhos de ʀooᴛ são impressos em linhas separadas, sem nenhum recuo, em ordem. Cada nó é imediatamente seguido por seus filhos, se houver, impressos da mesma maneira, recursivamente, recuados por dois caracteres à direita. Para cada nó que possui filhos, uma linha vertical que consiste em |caracteres (canal) se estende do caractere diretamente abaixo do primeiro caractere do nó até a linha do seu último nó filho, não incluindo os filhos do último nó filho. Se o recuo de um nó for diferente de zero, ele será precedido por +-(no mesmo nível de recuo que seu pai), substituindo a linha vertical descrita acima.

Entrada e saída

Você pode ler a entrada através do STDIN ou usando um método equivalente . Você pode assumir que não há linhas vazias e pode exigir que a última linha termine, ou não, em um caractere de nova linha. Você pode assumir que os nomes dos objetos consistem em caracteres ASCII imprimíveis (sem incluir espaço). Você pode supor que os objetos em uma definição de destino sejam separados por um caractere de espaço único e que não haja espaços à esquerda ou à direita . Você pode assumir que cada destino está definido no máximo uma vez e que não há repetições em sua lista de dependências.

Você pode gravar a saída em STDOUT ou usar um método equivalente . Todas as linhas de saída, exceto as mais longas, podem incluir espaços à direita. A última linha de saída pode ou não terminar em um caractere de nova linha.

Ponto

Isso é código-golfe . A resposta mais curta , em bytes, vence.

Casos de teste

Seu programa deve processar cada um dos seguintes casos de teste em um período de tempo razoável.

Entrada

Depender Dependee
Independent

Saída

Depender
+-Dependee
Independent

Entrada

Earth Turtle
Turtle Turtle

Saída

Earth
+-Turtle
  +-Turtle ...

Entrada

F A C B D I
A B
B A C
D E H
C
G F
J H G C E I
E D
H D
I G

Saída

J
+-C
+-E
| +-D
|   +-E ...
|   +-H ...
+-H
| +-D ...
+-G
| +-F
|   +-C
|   +-A
|   | +-B ...
|   +-B
|   | +-C
|   | +-A ...
|   +-D ...
|   +-I ...
+-I
  +-G ...

Árvore da tecnologia Civilization V

Entrada

Mostrar snippet de código

Saída

Mostrar snippet de código

Gráfico de Dependência de Pacotes Cygwin syslog-ng

Entrada

Mostrar snippet de código

Saída

Mostrar snippet de código

regex.cGráfico de chamada GNU grep

Entrada

Mostrar snippet de código

Saída (Opa! Muito tempo para o SE lidar.)

code-golf ascii-art graph-theory Ell
fonte
5
Bem especificado!
Não que Charles
A auto-referência na seção Ordem dos nós faz minha cabeça doer.
recursivo

Respostas:

5

Haskell, 512 bytes

import Data.List
r=reverse
n j|let(w,s)#p|let a?b=or[q!b<GT|(q,r)<-i,a==r,elem q(h p)>elem(a,q)i];a!b|a==b=EQ|a?b||(a<b)>b?a=LT;_!_=GT;l=nub.sortBy(!)$h p;m(v,s)q|h q==[]=(v,[q]:s)|elem q w=(v,[q++" ..."]:s)|(w,x:y)<-(v,[])#q=(w,(q:(u"| "=<<r y)++u"  "x):s)=foldl m(l++w,[])l;c(p,q)=z$p:q:h q;y=z=<<j;i=iterate(nub.sort.(c=<<))y!!length j;h""=[p|p<-id=<<j,and[elem(p,r)i|(r,q)<-i,p==q]];h p=[r|(q,r)<-y,p==q]=unlines=<<r(snd$mempty#"")
u s(x:y)=("+-"++x):map(s++)y
z(x:y)=(,)x<$>y
main=interact$n.map words.lines

Corra online em Ideone

Anders Kaseorg
fonte
Parabéns. Muito agradável!
Ell