Find One Import Cycle

models imports services, and services imports models. That loop is an import cycle, and the article before this exercise showed how it can break at import time. Before you can fix a cycle you have to find it, and in a project with forty modules the loop can run through five of them.

Write a depth-first search that finds one cycle in a project's imports:

find_cycle({"app": ["models"], "models": ["services"], "services": ["models"]})
# ["models", "services", "models"]

What to write

Fill in find_cycle(imports). imports maps each module to the modules it imports, in the order its import lines appear.

• Search depth-first. Follow a module's first import, then that module's first import, and so on, before you try any module's next import.
• Start a search from each module, in sorted name order. Follow each module's imports in the order listed.
• Keep the path of modules you are on. If the next module is already on the path, you have found a cycle. Return the path from that module to the end, followed by that module again, as in ["models", "services", "models"].
• A module that imports itself gives ["a", "a"].
• Skip any imported name that is not a key in imports, such as json. It is outside the project.
• Return None if there is no cycle.

What the driver reports

Keep solve as it is. It returns:

• cycle: the list your function returned, or None.
• chain: the cycle written as an import chain, such as models -> services -> models, or no cycle.

The hard problem after this one lists every cycle in a graph, each one once. This one stops at the first.