docs/05-changelog.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
author |
Steve Losh <steve@stevelosh.com> |
date |
Mon, 14 Dec 2020 20:13:51 -0500 |
parents |
e5f60ffb3dc4 |
children |
7e80eda84170 |
Changelog
=========
Here's the list of changes in each released version.
[TOC]
v1.3.2
------
[Fixed a bug](https://github.com/sjl/cl-digraph/issues/4) where certain kinds of
cycles were not correctly detected during topological sorting.
v1.3.1
------
[Fixed a bug](https://github.com/sjl/cl-digraph/pull/3) for recent SBCL versions
when creating a digraph without a custom hash function.
v1.3.0
------
Added the `arbitrary-vertex` function to return an arbitrary vertex of
a digraph.
v1.2.1
------
Fixed a bug in `copy-digraph`.
v1.2.0
------
Added `rootp` and `leafp` predicates to check whether a vertex is a root/leaf in
a digraph.
v1.1.0
------
Minor internal cleanup.
If you pass an invalid `strategy` argument to `reachablep` there will now be
a restart available to supply a new value, instead of just crashing and burning.
v1.0.0
------
Initial version.