Hello,
I have been using Moose for some graph analysis and I noticed that Tarjan was a little
slow. Analyzing further, I noticed that even though the complexity of Tarjan is linear,
building the graph is O(n*m) where n is the number of nodes, and m is the number of edges
of the graph.
This happen because Moose creates its own graph nodes using as a model my nodes, and then
for building each edge of the graph it looks for the corresponding node using detect: [ :n
| n model = aModel ] over the OrderedCollection of nodes.
I fixed it by replacing the nodes OrderedCollection for a Dictionary and replacing the
MalTarjan>>findNode:ifAbsent: implemented with a detect:ifAbsent: by a Dictionary
lookup. In my benchmark of 2 seconds before the fix, now takes 38ms, and my other
experiment that I got bored of waiting after 10 hours now it takes less than 1 hour and a
half.
I already committed it, the tests look fine but let me know if something goes bad.
Cheers,
Alejandro