lisp-random / tsort.lisp

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.