The cycles display mode shows useless information and does not work properly for larger projects.

[ArturLew]

Hi there!

The project looks promising and I wanted to use it to find a cyclic loop when importing modules in my project.
Unfortunately it only works for trivial cases :(

For more complex cases (like mine) the result generated from the application is purely random - not only was the application unable to correctly locate the source of the problem for me, but it generates a different dependency graph each time.

I tested on: Python 3.11.2 and Python 3.11.5
Platform: Windows 11

Used command line:

pydeps --show-cycles --no-config app

For three calls - tree different outputs:

[thebjorn]

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...

[yusiyoh]

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

[thebjorn]

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

[hartwork]

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 .

[thebjorn]

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.

[hartwork]

@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 👍

[emilienDespres]

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.

[thebjorn]

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.