search

aysylu / loom

Graph library for Clojure. Mailing list https://groups.google.com/forum/#!forum/loom-clj
http://aysy.lu/loom/
886 stars 108 forks source link

Change loom.alg-generic/pre-traverse to do much less work #120

Open jafingerhut opened 5 years ago

jafingerhut commented 5 years ago

especially if the graph is dense with edges for a node that is traversed, but the returned lazy sequence is not ever evaluated to get to those nodes.

Also eliminate a stack-growing recursive call, using recur instead. The previous version could grow the call stack nearly as deep as the number of edges in the graph.

jafingerhut commented 5 years ago

I was using pre-traverse to do a partial DFS of some large graphs where some nodes had very high degree, and found that it was doing a lot of unnecessary work for edges in the graph that were never 'crossed' by my partial DFS.