Perfomance: Use Dynamic Programming for dependency analysis.
Perfomance: Use Dynamic Programming for dependency analysis.

Rationale: when using larging amounts of migrations (> 100) and some explicit
dependencies (using depends_on) the dependency resolver's performance became
pathological.

It was observed that the Depth First Search algorithm used to establish the
dependencies had large overlapping subproblems, and that therefor Dynamic
Programming was a viable strategy:

http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming

Note that the 'path' parameter is not used in the cache. However, it is not
needed there: if if given subtree has been proven to not have circular
dependencies it cannot have circular dependencies at a later moment by the
very definition of circular.

The method _dfs() is rewritten to return lists rather than individual elements
to facilitate the storing of results in a global cache.

The performance gain is not proven with tests. However, on my local project
it is visible with the naked eye: dependency analysis dropped from > 2 minutes
to < 1 second.

smartfile/django-south,smartfile/django-south