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

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

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

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

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

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

(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 ***)

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

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

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

//fixed

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

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

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

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

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

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

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

командой dijkstra

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

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

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

А это связано с тем что ли дейкстрой, который против гоуту пер?

Нет, это просто однофамилец.

как точно.