(topologically-ordered-p nodes graph) determines if a list of
(topologically-ordered-p nodes graph) → ordered-p
We check that, for every node
This is a weak check in a couple of ways: we don't require that the
We can determine if the nodes are topologically sorted in linear time, assuming constant-time hashing.
(defun topologically-ordered-p (nodes graph) (declare (xargs :guard t)) (let ((__function__ 'topologically-ordered-p)) (declare (ignorable __function__)) (b* ((seen (len nodes)) ((mv ans seen) (topologically-ordered-p-aux nodes graph seen))) (fast-alist-free seen) ans)))