Diff from to

# tsort.lisp

`         :when (null deps)`
`           :collect node))`
` `
`-(defun tsort (graph)`
`-  "Topologically sort GRAPH. An error is signalled if it is not a`
`-directed acyclic graph."`
`+(defun tsort (dag)`
`+  "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))`
`           :do (progn`
`                 ;; Remove the 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.`
` (defun random-dag (size)`
`+  "Generate a random directed acyclic graph with SIZE number of`
`+nodes."`
`   (labels ((random-between (a b)`
`              "Generate a random integer between A and B, inclusive."`
`              (assert (>= b a))`
`     (loop :for n :below size`
`           :collect (cons n (nshuffle (random-deps n))) :into nodes`
`           :finally (return (nshuffle nodes)))))`
`+`
`+(defun test-timing (size)`
`+  (let ((dag (random-dag size)))`
`+    (time (tsort dag))`
`+    (values)))`
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.