Detect *all* cycles during topological sort
Previously the cycle detection was limited to detecting when we hit
a currently-being-visited node during a traversal. So something like this would
be correctly found:
A --> B --> C
^ |
| |
+-----+
We start at the root (A), go to B, then to C, then to B, and detect that we're
still working on B and signal the error.
But this doesn't find all cycles, because we *start* at the root nodes, and if
a cycle doesn't have any outcropping branches we'll never reach it at all. For
example:
A --> B
^ |
| |
+-----+
This graph has no roots, so we incorrectly ignore the cycle.
This patch fixes the problem by keeping a count of visited nodes and and making
sure it matches the digraph's size at the end.
Fixes https://github.com/sjl/cl-digraph/issues/4
| author |
Steve Losh <steve@stevelosh.com> |
| date |
Mon, 14 Dec 2020 20:13:51 -0500 |
| parents |
0434eb58dde3 |
| children |
(none) |
.PHONY: vendor test test-sbcl test-ccl test-ecl test-abcl pubdocs
heading_printer = $(shell which heading || echo 'true')
sourcefiles = $(shell ffind --full-path --literal .lisp)
docfiles = $(shell ls docs/*.markdown)
apidocs = $(shell ls docs/*reference*.markdown)
# Vendor ----------------------------------------------------------------------
vendor/quickutils.lisp: vendor/make-quickutils.lisp
cd vendor && sbcl --noinform --load make-quickutils.lisp --eval '(quit)'
vendor: vendor/quickutils.lisp
# Testing ---------------------------------------------------------------------
test: test-sbcl test-ccl test-ecl test-abcl
test-sbcl:
$(heading_printer) computer 'SBCL'
sbcl --load test/run.lisp
test-ccl:
$(heading_printer) slant 'CCL'
ccl --load test/run.lisp
test-ecl:
$(heading_printer) roman 'ECL'
ecl -load test/run.lisp
test-abcl:
$(heading_printer) broadway 'ABCL'
abcl --load test/run.lisp
# Documentation ---------------------------------------------------------------
$(apidocs): $(sourcefiles)
sbcl --noinform --load docs/api.lisp --eval '(quit)'
docs/build/index.html: $(docfiles) $(apidocs) docs/title
cd docs && ~/.virtualenvs/d/bin/d
docs: docs/build/index.html
pubdocs: docs
hg -R ~/src/docs.stevelosh.com pull -u upstream
rsync --delete -a ./docs/build/ ~/src/docs.stevelosh.com/cl-digraph
hg -R ~/src/docs.stevelosh.com commit -Am 'cl-digraph: Update site.'
hg -R ~/src/docs.stevelosh.com push upstream
hg -R ~/src/docs.stevelosh.com push