#1 Declined

Pruning of the recursive search tree for detecting cycles in graphs

  1. dirkbaechle

Hi there,

I'd like to propose this patch for the file common/graph.py. While trying to analyze the source tree of SCons (www.scons.org), I noticed that pylint took forever to finish a single run. I tracked the problem down a little and finally ended my search at the _get_cycles() function that gets called recursively. They way it is implemented at the moment, you will get a very high number of calls for medium to large graphs that are also very dense in nature (have a high vertex degree). In the case of SCons there are about 176 packages involved, which import each other a lot. This results in 130869104 calls of _get_cycles() and a runtime of 27minutes and 6.835seconds fo the whole pylint run. With this patch you get 10156 calls, taking 30.893s for the complete pylint call. Note, that the pruning of the search tree also reduces the list of output results, since all manifolds that are simple rotated versions of each other, get suppressed automatically.

Best regards,


Comments (5)

  1. dirkbaechle author

    Hi Pierre,

    and thanks for your quick reply. Sorry that I missed the pylint ticket, although I probably wouldn't have recognized it as being connected to logilab_common if I actually had run across it. ;)

    I can try to amend the changeset, but have no idea how to do this in a clean way. Locally I could use "hg commit --amend", but since I already pushed my changes this isn't possible anymore right? Do you have an idea and can suggest a series of commands for this case? My best bet would be to create a new changeset on top (adding a comment somewhere in the code) and add the description/ticket ref to that...

    1. Pierre-Yves David

      Bitbucket is a lacking proper support for amending pull request.

      You can either:

      • add more commit above this one and let the integrator fold them
      • Amend you commit locally and creates a new pull request
  2. dirkbaechle author

    Ahh, don't mind...now I got it. I'll fix the code according to your comments below (didn't see them at first) and add the full description to that changeset.