HomePhorge

Feature #2597 -- use iterative DFS in Tarjan clustering.
f547118462caUnpublished

Unpublished Commit ยท Learn More

Repository Importing: This repository is still importing.

Description

Feature #2597 -- use iterative DFS in Tarjan clustering.

In order to bypass the limitations of the C stack, which is also the Ruby
stack, we replace the simple and clear recursive Trajan implementation with an
iterative version that uses the heap as the stack.

This is somewhat harder to read, but can now run a 10,000 vertex deep linear
dependency relationship where, previously, 1,250 was about the limit on my
machine.

This should now be bounded by the size of the heap rather than the stack on
all platforms -- though it would be nice to get rid of the magic and return to
the recursive version if Ruby ever follows Perl down the sensible path of
essentially unlimited recursion by writing that code for us in the
interpreter...

Details

Provenance
Daniel Pittman <daniel@rimspace.net>Authored on
vanmeeuwenPushed on Jun 2 2015, 2:22 PM
Parents
rPU34a57b846319: Feature #2597 -- really find and report cycles.
Branches
Unknown
Tags
Unknown

Event Timeline

Daniel Pittman <daniel@rimspace.net> committed rPUf547118462ca: Feature #2597 -- use iterative DFS in Tarjan clustering. (authored by Daniel Pittman <daniel@rimspace.net>).Feb 4 2011, 1:45 AM