docs/index.markdown @ 884333cfb6fb v1.3.2

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

cl-digraph is an implementation of a mutable [directed graph][] data structure
for Common Lisp.

* **License:** MIT
* **Documentation:** <https://docs.stevelosh.com/cl-digraph/>
* **Mercurial:** <https://hg.stevelosh.com/cl-digraph/>
* **Git:** <https://github.com/sjl/cl-digraph/>

cl-digraph focuses on simplicity, correctness, and usability.  Performance is
not *terrible*, but is not a high priority.

It is currently not thread-safe, but this may happen in the future.

The test suite currently passes in SBCL, CCL, ECL, and ABCL on OS X and Debian.
Further testing is welcome.

[directed graph]: https://en.wikipedia.org/wiki/Directed_graph