[cl-graph-devel] Bug in toposort, or actually rootp

[Willem Rein Oudshoorn]

Gary King <gwking at metabang.com> writes:

> I agree with your fix and will push it out later today / tomorrow.

Thank you.

>> Also when looking at the code for the topological sort I noticed that
>> 
>> 1 - it is not the most efficient
>> 2 - it will loop forever when there are cycles in the graph
>> 
>> For my personal use I might want to change that.  Are you interested in 
>> patches for such improvements?
>
>
> Yes, please!
>
> thanks for letting me know about the rootp problem.

I have attached a diff file which changes assign-level to be more
performant and hopefully correct.  The semantics has changed but I
think the old behaviour was not what you would expect.  In the old
behaviour the assigned depth depended on the order in which the edges 
are traversed by iterate-edges.  Also it did not do what the
documentation of depth suggested.

Few things to note:

1. (depth graph) might need fixing because it now only works for
   directed graphs.  But I think the old behaviour did also not work
   for non direted graphs.
2. I have never before used cl-graph, cl-containers etc. I tried to code 
   in the style of these projects.  But please let me know if you want
   the patch to be changed in anyway.
3. There is still some small room for improvement for the performance, 
   but now the perforamance should be O(#edges + #nr-vertices)
   
Kind regards,
Wim Oudshoorn.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: cl-graph-toposort.diff
Type: text/x-patch
Size: 3812 bytes
Desc: Patch for assign-level (and thus toposort)
URL: <https://mailman.common-lisp.net/pipermail/cl-graph-devel/attachments/20110321/f43a3df7/attachment.bin>