- "Topologically sort GRAPH. An error is signalled if it is not a

-directed acyclic graph."

+ "Find the topological sort of GRAPH destructively. An error is

+signalled if it is not a directed acyclic graph."

(let* ((sorted nil) ; Final sorted list.

- (sinks (list-sinks graph)) ; Sinks in the graph.

- (dag (copy-tree graph))) ; Copy of the graph that we will mutate.

+ (sinks (list-sinks dag))) ; Sinks in the graph.

(loop :while (not (null sinks))

(error "Cannot sort a cyclic graph. ~

The cycles are ~S." dag))))))

+(defun tsort-copy (graph)

+ "Topologically sort GRAPH. An error is signalled if it is not a

+directed acyclic graph."

+ (tsort (copy-tree graph)))

;;; Much of the functions in LABELS are taken from QTILITY.

+ "Generate a random directed acyclic graph with SIZE number of

(labels ((random-between (a b)

"Generate a random integer between A and B, inclusive."

:collect (cons n (nshuffle (random-deps n))) :into nodes

:finally (return (nshuffle nodes)))))

+(defun test-timing (size)

+ (let ((dag (random-dag size)))