jan-krecke/marui

Find circular imports ina Python project

marui's Issues

Generalize search for circular dependencies

Description

At the moment, marui can only find circular imports that consists of two models directly importing each other. However, in general, a circular import can also occur through an import chain of arbitrary length, e.g.:

modA -> modB -> modC -> modA

where -> stands for 'imports'.

Proposed solution

marui could build a directed graph from the import dependencies in a given Python project, and treat modules that form a circular import chain with each other as strongly connected components. Several algorithms exist to find strongly connected components in a directed graph:

• Kosaraju's algorithm: conceptually simple, but requires two depth-first passes
• Tarjan's strongly connected components algorithm, which uses only one DFS pass
• Path-based strong component algorithm also uses only one DFS pass

Potential issues

An apparent drawback of the algorithms listed above (as far as I can tell right now) is that a graph node can belong to only one strongly connected component (SCC). However, circular import graphs in a Python project might overlap. Thus, I'll have to figure out how to deal with those cases.