Визуализация графика зависимости

22

Цель этой задачи - написать программу, которая визуализирует граф зависимостей в форме дерева. В то время как «граф зависимостей» в этом контексте означает не что иное, как ориентированный граф, описанный здесь метод визуализации лучше всего подходит для графов, описывающих некоторое отношение зависимости (в качестве упражнения, после прочтения задачи, попробуйте изменить направление одного из примеры графиков, и посмотрите, насколько полезен результат.)

Вход в программу состоит из одного или более целевых определений , которые строки вида

Target DirectDependency1 DirectDependency2 ...

определение цели и связанных с ней прямых зависимостей , если таковые имеются. Цели и их зависимости в совокупности называются объектами . Если объект отображается только как зависимость, а не как цель, он не имеет зависимостей. Множество всех объектов, которые появляются на входе, называется Γ . (См. Раздел «Вход и выход» для более подробной информации о формате ввода.)

Для любой пары объектов A и B мы говорим, что:

  • A зависит от B (эквивалентно, B требуется для A ), если A напрямую зависит от B или если A напрямую зависит от B ' , а B' зависит от B , для некоторого объекта B ' ;
  • Образом зависит от B (эквивалентно, В правильно требуемой А ), еслизависит от B , а B не зависит от А .

Мы определили надуманный объект ᴛooᴛ , а не в Γ, такой, что ʀooᴛ не требуется напрямую ни для одного объекта и такой, что для всех объектов A ʀooᴛ напрямую зависит от A тогда и только тогда, когда A находится в Γ, а A не является должным образом требуемый любым объектом в Γ (другими словами, ʀooᴛ напрямую зависит от A, если никакой другой объект не зависит от A , или если все объекты, которые зависят от A , также требуются A. )

Дерево вывода

Мы строим дерево , корневым узлом которого является «oo», и таким образом, что дочерние элементы каждого узла являются его прямыми зависимостями. Например, учитывая вход

Bread Dough Yeast
Dough Flour Water
Butter Milk

полученное дерево

Пример выходного дерева

или в форме ASCII,

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

, Вывод программы - это определенное выше дерево, напечатанное без узла «oo ». Так, например, соответствующий выход для вышеуказанного ввода

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

, Подробное описание макета выходного дерева приведено позже.

Заказ узла

Дочерние узлы данного родительского узла, P , должны быть отсортированы таким образом, чтобы для всех дочерних узлов A и B из P , A появлялся перед B тогда и только тогда, когда

  • существует дочерний узел C в P , так что A должным образом требуется для C , и C предшествует или равен B в соответствии с тем же порядком; или ,
  • По алфавиту предшествует B (более preceisely, A предшествует B с использованием ASCII сортировки,) , и не существует нет дочернего узла С из Р , такие , что В должным образом , требуемом C , и C предшествует или равно, А , в соответствии с тем же порядка ,

(Люди, ищущие математическую задачу, могут захотеть показать, что это отношение хорошо определено и что это, на самом деле, строгий общий порядок. Не забывайте, что Γ конечно!)

Например, учитывая вход

X D C B A
B D
C A

, вывод должен быть

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

, Aпоявляется раньше Bи Bпоявляется раньше Cиз-за их алфавитного порядка; Dпоявляется до B, так как это должным образом требуется для него, и после A, так как оно следует за ним в алфавитном порядке; Bи Cне появляются раньше D, даже если они предшествуют ему в алфавитном порядке, поскольку существует узел, а именно, Bкоторый должным образом требует D, и который равен B(то есть самому себе), и предшествует C, согласно тем же правилам.

Повторы

Один и тот же объект A может появляться более одного раза в выходных данных, если, например, он требуется более чем одному объекту. Если A не имеет собственных зависимостей, в этом случае не требуется никакой специальной обработки. В противном случае, чтобы минимизировать многословность вывода и избежать бесконечной рекурсии из-за циклических зависимостей, зависимости A перечислены только в его первом появлении, для которого ни один из предков не является родным братом другого узла A ; любое другое вхождение A не должно иметь дочерних элементов и должно сопровождаться пробелом и многоточием, как в .A...

Например, учитывая вход

IP Ethernet
TCP IP
UDP IP
WebRTC TCP UDP

, вывод должен быть

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

, В качестве другого примера, показывающего как круговую зависимость, так и соображения предков,

Rock Scissors
Paper Rock
Scissors Paper

, должен привести к

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

, Обратите внимание, что, например, первое вхождение Rockне перечисляет своих зависимостей, так как его родительский Paperэлемент является родственным Rockузлом другого узла. Родитель второго Rockузла, «oo »(который не отображается в выходных данных), не имеет Rockродственного брата, поэтому зависимости Rockэтого узла перечислены на этом узле.

Структура выходного дерева

Я уверен, что вы поняли, как дерево должно быть представлено как искусство ASCII (и не стесняйтесь пропустить этот раздел, если у вас есть), но ради полноты ...

Дочерние узлы ʀooᴛ печатаются в отдельных строках без отступов по порядку. За каждым узлом сразу же следуют его дочерние элементы, если они есть, которые печатаются одинаково, рекурсивно, с отступом в два символа справа. Для каждого узла, у которого есть дочерние элементы, вертикальная линия, состоящая из |символов (трубы), проходит вниз от символа непосредственно под первым символом узла до строки его последнего дочернего узла, не включая дочерние элементы последнего дочернего узла. Если отступ узла ненулевой, ему предшествует +-(на том же уровне отступа, что и его родитель) перезапись вертикальной линии, описанной выше.

Вход и выход

Вы можете прочитать ввод через STDIN , или используя эквивалентный метод . Вы можете предположить, что пустых строк нет , и вам может потребоваться, чтобы последняя строка заканчивалась или не заканчивалась символом новой строки. Вы можете предположить, что имена объектов состоят из печатных символов ASCII (не включая пробел). Вы можете предположить, что объекты в определении цели разделены одним пробелом и что нет начальных или конечных пробелов . Вы можете предположить, что каждая цель определена не более одного раза и что в ее списке зависимостей нет повторений .

Вы можете записать вывод в STDOUT или использовать эквивалентный метод . Все выходные строки, кроме самых длинных, могут включать в себя завершающие пробелы. Последняя строка вывода может или не может заканчиваться символом новой строки.

Гол

Это код-гольф . Самый короткий ответ , в байтах, выигрывает.

Тестовые случаи

Ваша программа должна обрабатывать каждый из следующих тестовых случаев в разумные сроки.

вход

Depender Dependee
Independent

Выход

Depender
+-Dependee
Independent

вход

Earth Turtle
Turtle Turtle

Выход

Earth
+-Turtle
  +-Turtle ...

вход

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

Выход

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

Цивилизация V Технологическое дерево

вход

Показать фрагмент кода

Выход

Показать фрагмент кода

Cygwin syslog-ng График зависимостей пакетов

вход

Показать фрагмент кода

Выход

Показать фрагмент кода

GNU grep regex.cCall Graph

вход

Показать фрагмент кода

Вывод (Ой! Слишком долго для SE для обработки.)

code-golf ascii-art graph-theory флигель
источник
5
Хорошо указано!
Не то, что Чарльз
Самостоятельная ссылка в разделе порядка узлов делает мою голову болит.
рекурсивный

Ответы:

5

Haskell, 512 байт

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

Запустить онлайн на Ideone

Андерс Касеорг
источник
Congrats. Очень хорошо!
Ell