- "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)))