Заказать Список зависимостями

Question

Учитывая следующий список:

var modules = new List<Module>() { 
    new Module() { Name = "Audits", Dependencies = new[] { "Logs" } }, 
    new Module() { Name = "Blog", Dependencies = new[] { "Content", "Tags" } }, 
    new Module() { Name = "Content", Dependencies = new[] { "Audits" } }, 
    new Module() { Name = "Logs" }, 
    new Module() { Name = "Tags" } 
}; 

Мне нужно создать способ заказать этот список программно, так что модули, которые являются наиболее надежными являются на самом верху. Поэтому требуемый порядок с помощью приведенного выше примера будет:

1. Журналы
2. Ревизии
3. Содержание
4. Метки
5. Блог

С "Материалы" имеет зависимость от «аудиты «тогда сначала появляется« Аудит ». Но поскольку «Аудит» имеет зависимость от «Журналов», тогда «Журналы» выходят за пределы «Аудит» и так далее. «Блог» появляется последним, поскольку он имеет зависимости от «Контента» и «Метки», и поэтому они выше.

Надеюсь, я достаточно подробно описал свою проблему. Я уверен, что есть какой-то умный алгоритм, позволяющий справиться с этим и сделать его настолько эффективным, насколько это возможно, но это намек на меня до сих пор. Я был бы признателен, если бы кто-нибудь мог указать мне в правильном направлении.

Благодаря

Answer 1

Проблема, которую вы описываете, называется topological sort: при частичном заказе попробуйте найти линейное описание, которое соблюдает это упорядочение.

Типичный алгоритм для решения этой проблемы требуется O(|V| + |E|) время, когда |V| является числом вершин (модули в вашем примере) и |E| это число ребер (зависимости в вашем примере).

Связанная статья в Википедии также содержит pseudo code. Для преобразования алгоритма в ваш пример потребуется некоторое ведение бухгалтерского учета, но это относительно просто.

Answer 2

Самый простой способ создать функцию сравнения между значениями, сортирует, основанный на зависимости

static int CompareModules(Module left, Module right) { 
    if (left.Dependencies.Contains(right.Name)) { 
    return 1; 
    } 

    if (right.Dependencies.Contains(left.Name)) { 
    return -1; 
    } 

    return left.Dependencies.Length - right.Dependencies.Length; 
} 

Затем использовать это в качестве аргумента List<T>.Sort

modules.Sort(CompareModules); 

Обратите внимание, что это пример имеет предположения, что Dependencies - пустой массив, когда они не являются зависимостями и что нет pendencies