HomePhorge

Feature #2597 -- really find and report cycles.
34a57b846319Unpublished

Unpublished Commit ยท Learn More

Repository Importing: This repository is still importing.

Description

Feature #2597 -- really find and report cycles.

This implements Tarjan's algorithm for finding strongly connected components
in a directed graph, and leverages that to find cycles.

This allows us to report the minimum set of nodes in each cycle, as well as
reporting each cycle discretely if there are multiple of them.

While this can still produce overwhelming and/or unhelpful output, it
represents a large step forward in delivering useful information when a cycle
is detected.

This presently reports the set of nodes that contain the cycle, in no
particular order, rather than the set of edges connecting those nodes.

Sadly, it also suffers a limitation: the implementation of Tarjan's algorithm
used to find strongly connected components is recursive, so is limited by the
maximum Ruby stack depth to dependency chains less than 1,000 nodes deep.

While this is probably not a limit in practice, it is a nasty limitation, and
other considerations (like Ruby stack consumption across versions) could
trigger this much sooner than is desirable.

Details

Provenance
Daniel Pittman <daniel@rimspace.net>Authored on
vanmeeuwenPushed on Jun 2 2015, 2:22 PM
Parents
rPU403adb8af42c: Feature #2597 -- nicer reporting of relationships.
Branches
Unknown
Tags
Unknown

Event Timeline

Daniel Pittman <daniel@rimspace.net> committed rPU34a57b846319: Feature #2597 -- really find and report cycles. (authored by Daniel Pittman <daniel@rimspace.net>).Feb 4 2011, 1:45 AM