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 |
c44027e04989 |
children |
3443da60edaa |
516585a909d096895330ff634f0eb06c63b4a9f8 v1.0.0
cd7d9aaa93858246761e11ea719433f93a215669 v1.1.0
6f56512ea85afe720f6dc57172b4663f4109f4c2 v1.2.0
8cf220c55f134e63a3c27e560750095ce58e3abb v1.2.1
0434eb58dde39dce2c6f9d99df163e4c80246ebc v1.3.0
e5f60ffb3dc49309d263484a021a04a149e3ac60 v1.3.1