Sort a list of instances by their model dependancy graph.

    This is very similar to Django's sort_dependencies method except
    for two big differences:

    1. We graph dependencies unrelated to natural_key.
    2. We take a list of objects, and return a sorted list of objects.

def sort_dependencies(objects):
    """
    Sort a list of instances by their model dependancy graph.

    This is very similar to Django's sort_dependencies method except
    for two big differences:

    1. We graph dependencies unrelated to natural_key.
    2. We take a list of objects, and return a sorted list of objects.
    """
    from django.db.models import get_model
    # Process the list of models, and get the list of dependencies
    model_dependencies = []
    models = set()
    model_list = set()
    objs_by_model = defaultdict(list)
    for o in objects:
        model = o.__class__
        objs_by_model[model].append(o)
        model_list.add(model)

    for model in model_list:
        models.add(model)
        # Add any explicitly defined dependencies
        if hasattr(model, 'natural_key'):
            deps = getattr(model.natural_key, 'dependencies', [])
            if deps:
                deps = [get_model(*d.split('.')) for d in deps]
        else:
            deps = []

        # Now add a dependency for any FK or M2M relation with
        # a model that defines a natural key
        for field in itertools.chain(model._meta.fields, model._meta.many_to_many):
            if hasattr(field.rel, 'to') and field.rel.to != model:
                deps.append(field.rel.to)
        model_dependencies.append((model, deps))

    model_dependencies.reverse()
    # Now sort the models to ensure that dependencies are met. This
    # is done by repeatedly iterating over the input list of models.
    # If all the dependencies of a given model are in the final list,
    # that model is promoted to the end of the final list. This process
    # continues until the input list is empty, or we do a full iteration
    # over the input models without promoting a model to the final list.
    # If we do a full iteration without a promotion, that means there are
    # circular dependencies in the list.
    model_list = []
    while model_dependencies:
        skipped = []
        changed = False
        while model_dependencies:
            model, deps = model_dependencies.pop()

            # If all of the models in the dependency list are either already
            # on the final model list, or not on the original serialization list,
            # then we've found another model with all it's dependencies satisfied.
            found = True
            for candidate in ((d not in models or d in model_list) for d in deps):
                if not candidate:
                    found = False
            if found:
                model_list.append(model)
                changed = True
            else:
                skipped.append((model, deps))
        if not changed:
            raise CommandError("Can't resolve dependencies for %s in serialized app list." %
                ', '.join('%s.%s' % (model._meta.app_label, model._meta.object_name)
                for model, deps in sorted(skipped, key=lambda obj: obj[0].__name__))
            )
        model_dependencies = skipped

    sorted_results = []
    for model in model_list:
        sorted_results.extend(objs_by_model[model])

    return sorted_results