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

[Willem Rein Oudshoorn]

Hi 

I was trying to do a topo sort on a directed graph and it did not work.
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

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

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?

Kind regards,
Wim Oudshoorn.