search

hraban / cl-graph

Common Lisp library for manipulating graphs and running graph algorithms
http://common-lisp.net/project/cl-graph/
Other
73 stars 13 forks source link

assign-level may take exponential time #10

Open pfdietz opened 8 years ago

pfdietz commented 8 years ago

I had a problem with topological-sort hanging, which I traced to the implementation of assign-level. In the worst case this can take exponential time (in the number of vertexes) on a directed acyclic graph.

I have a linear time implementation of topological sort I will be uploading to a branch when I have time. I doesn't use assign-level. Depth can be computed from the topological sort in linear time. Can assign-level be removed from the api?

gwkkwg commented 8 years ago

Hi there, I'm happy to drop assign-level and it's great that you've got a much better implementation.