grimp icon indicating copy to clipboard operation
grimp copied to clipboard

Add `find_shortest_cycle`

Open Peter554 opened this issue 10 months ago • 1 comments

This PR adds the find_shortest_cycle method to grimp, which I've been proposing in e.g. https://github.com/seddonym/grimp/issues/189.

This is a low-level, granular method for finding cycles in the import graph. We could potentially add some higher order methods for working with import cycles across the entire graph as @K4liber has been suggesting - I think we can potentially have both, e.g. similar to the import chain APIs find_shortest_chain, find_shortest_chains and find_illegal_dependencies_for_layers (I think grimp should offer both lower and higher level APIs - we can add higher level APIs, but we also shouldn't forget/miss the more basic APIs - for one thing not everyone is using grimp with import linter).

Still TODO:

  • [ ] Align with @seddonym and @K4liber on whether we want this method added to grimp
  • [ ] Check implementation for correctness. More (python) tests?
  • [ ] Add benchmark
  • [ ] Usage docs
  • [ ] Update changelog

Peter554 avatar Mar 02 '25 06:03 Peter554

CodSpeed Performance Report

Merging #194 will not alter performance

Comparing Peter554:find-shortest-cycle (43b7c31) with master (8c1bb5d)

Summary

✅ 17 untouched benchmarks

codspeed-hq[bot] avatar Mar 02 '25 06:03 codspeed-hq[bot]

I'm going to close this one as it's a bit stale and I'm not working on it.

Peter554 avatar Jun 16 '25 19:06 Peter554

@Peter554 I am actually using your work while implementing AcyclicContract (still a draft, but soon it will be ready for a review: https://github.com/seddonym/import-linter/pull/250). It seems that it works as intended. Maybe one thing could be improved which is a deterministic output. Right now it seems to not be deterministic. I get different "shortest cycle" between runs for the exact same dependency graph.

K4liber avatar Jun 16 '25 19:06 K4liber