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

[Gary King]

Hi Willem,

> The underlying reason is that rootp does not what assign-level expects.
> assign-level expects rootp to return t if the vertex is a source vertex
> (no incoming edges).   However rootp returns t if the vertex is a sink
> (no outgoing edges).   A quick fix is to replace

Hmmm, that's embarrassing!

> (defmethod rootp ((vertex basic-vertex))
>  ;;?? this is inefficient in the same way that (zerop (length <list>)) is...
>  (zerop (source-edge-count vertex)))
> 
> with 
> 
> (defmethod rootp ((vertex basic-vertex))
>  ;;?? this is inefficient in the same way that (zerop (length <list>)) is...
>  (zerop (target-edge-count vertex)))
> 
> But I don't know if that will introduce bugs in other places.

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

> 
> 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.

--
Gary Warren King, metabang.com 
Cell: (413) 559 8738
Fax: (206) 338-4052
gwkkwg on Skype * garethsan on AIM * gwking on twitter