LINUX.ORG.RU

Визуализация дерева зависимостей

 


0

2

Плохо знаком с теорией графов, поэтому формулировка задачи будет на примере зависимостей пакетов.

  • Пусть имеется дерево зависимостей, записанное в таком или подобном виде:
    пакет {перечисление пакетов от которых зависит данный}
    
    Например:
    A {B,C}
    B {C}
    C {}
    
  • Нужно получить другое дерево, включающее для каждого пакета только такие зависимости, которые не являются зависимостями его зависимостей:
    A {B}
    B {C}
    C {}
    
  • И далее преобразовать получившееся в синтаксис DOT:
    A <- B
    B <- C
    

Вопрос: имеет ли это преобразование какое-нибудь название в теории графов, и есть ли какая-нибудь готовая программа CLI, которая умеет решать подобную задачу. Речь не идёт о программах для визуализации зависимостей настоящих пакетов ПО, а о программах преобразования, принимающих на вход текстовый поток в данном формате или в формате DOT. Писать алгоритм тоже не прошу, сам с удовольствием подумаю, если ничего готового нет.

★★

Топологическая нумерация(сортировка) если, если память не подводит.

invy ★★★★★
()
Последнее исправление: invy (всего исправлений: 1)

для случая, когда нам известен «корень» - строим из своего плоского списка дерево, и все. Потом из концевых узлов родителей удаляем концевые узлы потомков. DOT рисуем в обратную сторону.

Топологическая сортировка малость не то.

arkhnchul ★★★
()
Ответ на: комментарий от arkhnchul

вру, не только концевые сносим, но вообще всех потомков второго уровня вложенности.

arkhnchul ★★★
()

че то засомневался, удалил, а потом опять запостил:) Короче, хз, то или не то, но работает вроде так как ты описал.

(define in-list? (lambda(a lst)
   (cond
      ((null? lst) #f)
      ((eq? (car lst) a) a)
      (#t (in-list? a (cdr lst))))))

(define fltr (lambda(the-packet another-packet)
   (cond
      ((null? the-packet) '())
      ((in-list? (car the-packet) another-packet) (fltr (cdr the-packet) another-packet))
      (#t (cons (car the-packet) (fltr (cdr the-packet) another-packet))))))

(define ev (lambda(x) (eval x (interaction-environment))))
(define all (lambda(the-lst)
   (let ((lst (ev the-lst)))
   (if (null? lst) '(***)
; ::: (*** a <- b f *** b <- c *** c <- d e ***)
      (cons '*** (cons the-lst (cons '<- (append (fltr lst (ev (car lst))) (all (car lst)) ))))))))

(define a '(b c d e f))
(define b '(c d e))
(define c '(d e))
(define d '())
(define e '())
(define f '())

(write (all 'a))

; (*** a <- b f *** b <- c *** c <- d e ***)

terminator-101
()
Ответ на: комментарий от terminator-101

Там вот эту строку

; ::: (*** a <- b f *** b <- c *** c <- d e ***)

в середине не нужна, это я тестил когда, забыл удалить.

//fixed

terminator-101
()

вот блин люди дают..уже и lisp`е что-то наваяли

а всё от незнания мат.части :-) То что хочет ТС называется «кратчайший путь в ориентированном графе», о чём не знать в разделах Develop,Admin вообще стыдно и позорно..

в чистой командной строке реализуется одной-единственной командой dijkstra (man 1 dijkstra) http://linux.die.net/man/1/dijkstra, которая входит в состав дистрибутивов с незапамятных времён

зы. или я не понял что хочет автор

MKuznetsov ★★★★★
()
Последнее исправление: MKuznetsov (всего исправлений: 1)
Ответ на: комментарий от MKuznetsov

ТС сформулировал задачу:

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

А затем просто спросил как это ваще называется в графах дейкстрах и прочих недофункторах. Задача, тем не менее была именно такая, реализовать, а как называется — второстепенно.

terminator-101
()
Ответ на: комментарий от MKuznetsov

командой dijkstra

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

terminator-101
()
Ответ на: комментарий от MKuznetsov

а всё от незнания мат.части :-) То что хочет ТС называется «кратчайший путь в ориентированном графе»

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

arkhnchul ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.