On Jan 23, 2011, at 5:52 PM, Nigel Kersten wrote:
> On Sun, Jan 23, 2011 at 12:39 AM, Daniel Pittman <[email protected]>
> wrote:
>> From: Daniel Pittman <[email protected]>
>>
>> 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.
>
> No code comment, but I'm very happy to see active work on this. It's
> very frustrating to debug these situations.
I second this.
I'd always planned on producing subgraphs (in dot format) when cycles were
encountered, since that's what I've always done for visual debugging, but I
never got around to it.
--
The chief lesson I have learned in a long life is that the only way to
make a man trustworthy is to trust him; and the surest way to make him
untrustworthy is to distrust him and show your distrust.
-- Henry L. Stimson
---------------------------------------------------------------------
Luke Kanies -|- http://puppetlabs.com -|- +1(615)594-8199
--
You received this message because you are subscribed to the Google Groups
"Puppet Developers" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/puppet-dev?hl=en.
