[cl-graph-devel] Bug in toposort, or actually rootp
Willem Rein Oudshoorn
woudshoo+cl-graph at xs4all.nl
Sun Mar 20 07:18:27 UTC 2011
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.
More information about the cl-graph-devel
mailing list