Graph Walking (Modern Common Lisp with FSet)

Next: Case Study: CL-Cont, Previous: Histogram Construction, Up: Examples [Contents][Index]

2.2 Graph Walking ¶

This section presents a simple example of code that might be written to walk a (potentially cyclic) directed graph, calling a provided function on each node (presumably, the function has some useful side-effect). First, here’s one way it might be written in plain CL:

(defun map-graph-nodes-cl-1 (fun graph)
  (let ((seen (make-hash-table :test 'eq))
        (workset (list (graph-start graph))))
    (loop while workset
      (let ((node (pop workset)))
        (unless (gethash node seen)
          (funcall fun node)
          (setf (gethash node seen) t)
          (dolist (succ (node-successors node))
            (pushnew succ workset)))))))

Things to note about this:

It uses a hash table to represent the “seen” set, but a list for the workset.
It does some nil punning (while workset).
pop removes the first element of the list and returns it.
pushnew is O(n).

Even though the seen set uses a hash table, because of the linear-time pushnew used to update workset, this version will bog down on large graphs. Of course, CL does give you ways to fix this, but the code gets more verbose:

(defun map-graph-nodes-cl-2 (fun graph)
  (let ((seen (make-hash-table :test 'eq))
        (workset (make-hash-table :test 'eq)))
    (setf (gethash (graph-start graph) workset) t)
    (loop while (plusp (hash-table-count workset))
      (let ((node (block arb
                    (maphash (lambda (k v)
                               (declare (ignore v))
                               (return-from arb k))
                             workset))))
        (remhash node workset)
        (unless (gethash node seen)
          (funcall fun node)
          (setf (gethash node seen) t)
          (dolist (succ (node-successors node))
            (setf (gethash succ workset) t)))))))

Here workset is also a hash table, instead of a list, but the code is noticeably longer, mostly because CL has no hash table operation like FSet’s arb; one has to be hacked up using maphash and a nonlocal return.

Here’s what it looks like using FSet — elegant and fast:

(defun map-graph-nodes-fset (fun graph)
  (let ((seen (set))
        (workset (set (graph-start graph))))
    (loop while (nonempty? workset)
      (let ((node (arb workset)))
        (excludef workset node)
        (unless (contains? seen node)
          (funcall fun node)
          (includef seen node)
          (unionf workset
                  (node-successors node)))))))