The cycles display mode shows useless information and does not work properly for larger projects. about pydeps HOT 8 OPEN

Hi @hartwork and thank you for the test case. Very useful :-)

Adding sorted in a few places improves things, at least to the point where I'm convinced the find_import_cycles method (in depgraph.py) is not correct. It looks like it is doing a DFS and looking for back-edges (it's been nine years since I wrote this code...), and then adding any found cycles to self.cyclerelations. I'm not sure where the bug is yet though.

from pydeps.

Hi @ArturLew and thank you for your interest in pydeps.

The problem you're seeing might be because the graph is pruned too much before cycle analysis is run..? Could you try adding --max-bacon=5 to the command line?

This problem doesn't show up on the examples I have in the testsuite, so I'd likely need something to test against to investigate it further...

from pydeps.

Similar issue here. It generates different diagrams each run for --show-cycles. Unfortunately, I cannot share the diagrams.

from pydeps.

See my previous comment. Without being able to reproduce the problem it is unlikely that I'll be able to fix it.

from pydeps.

The problem you're seeing might be because the graph is pruned too much before cycle analysis is run..? Could you try adding --max-bacon=5 to the command line?

@thebjorn thanks for the tip on --max-bacon!

See my previous comment. Without being able to reproduce the problem it is unlikely that I'll be able to fix it.

I would like to confirm…

• both the "graph changes every time" issue and the "unexpected output" aspect of the issue
• with both default --max-bacon 2 and --max-bacon 5 and beyond
• for repository https://github.com/hartwork/wnpp.debian.net (commit hartwork/wnpp.debian.net@08195e4) — image below —
• with pydeps 1.12.20
• and command pydeps wnpp_debian_net -T png --show-cycles --no-show --max-bacon 5.

I have yet to find a value for --max-bacon that does not produce any non-circle islands with --show-cycles, even 30 still includes islands.

PS: With regard to the non-determinism, my guess would be that GraphViz input is changing and that adding sorted(..) at a few places may fix the issue. I had the same with git-big-picture/git-big-picture#398 .

from pydeps.

@thebjorn thanks for your positive response! I'm a bit too swamped to have a closer look at the code myself right now, but great to know that there is interest in getting this improved, would be great 👍

from pydeps.

Hello, first of all thanks for the project, I find it quite useful.

If I understand correctly the following looks a bit excessive in find_import_cycles

if node.name in self.cyclenodes:
                return

Let's say we have two cycle A<->B and B<->C:

Starting traverse on A, we detect A<->B,

Then starting traverse on C (or B) will stop on B without detecting the B<->C as B is already marked, although for another cycle.

Maybe it's only part of the problem as it should only affect intersecting cycles, so I don't see how it would create island.

Not sure if I will be able to make a fix. I'll try.

from pydeps.

Hi @emilienDespres , I think I got to the bibliography from this paper "On Algorithms for Enumerating All Circuits of a Graph" (https://epubs.siam.org/doi/10.1137/0205007). As far as I remember the algorithm by Donald Johnson (https://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF) was the most efficient generally, although I don't know if the import graph is a special case where an other (simpler?) algorithm would suffice.

I'm in the middle of a huge project so I won't have any time to implement this for a while, but I'm always happy to merge a PR.

from pydeps.