порядок выполнения сборки файлов

Question

У меня есть структура данных, как указано ниже:

 class File
    {
        public string Value { get; set; }
        public File[] Dependencies { get; set; }
        public bool Change { get; private set; }</p>

<pre><code>    public File(string value,File[] dependencies)
    {
        Value = value;
        Dependencies = dependencies;
        Change = false;
    }
}

По сути, эта структура данных соответствует типичному выполнению сборки файлов.

Каждый файл имеет значение и список зависимостей, который снова имеет тип File. Каждый файл доступен со свойством Change, которое указывает, был ли файл изменен или нет.

Я провел мозговой штурм, чтобы сформировать алгоритм, который просматривает все эти файлы и собирает их в порядке (т.е. типичном процессе сборки), но не получил лучшего алгоритма.

Может кто-нибудь пролить свет на это?

Большое спасибо.

Махеш

Answer 1

Алгоритм, который вы ищете, называется топологическая сортировка .

Answer 2

Выполните следующие основные шаги.

1. Поиск файлов без каких-либо зависимостей
2. Сначала добавьте их в сборку
3. Поиск файлов, зависящих от тех, что находятся в сборке, и ничего больше
4. Добавьте их, чтобы построить следующий
5. Повторяйте 3 и 4, пока все файлы в сборке

Вам понадобятся некоторые проверки для обнаружения циклических зависимостей, которые могут вызвать бесконечный цикл на шаге 5. Кроме этого, это должно работать.