Поиск ширины направленного ациклического графа ... только с возможностью поиска родителей

Question

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

График/список предназначен для параллельного диспетчера рабочего процесса GNU Make-like, который использует файлы в качестве критериев для порядка выполнения. Каждый узел имеет список исходных файлов и целевых файлов. У нас есть хеш-таблица на месте, так что, учитывая имя файла, можно определить узел, который его производит. Таким образом, мы можем выяснить родителей узла, исследуя узлы, которые генерируют каждый из его исходных файлов, используя эту таблицу.

Это единственная способность, которую я имею на данный момент, без серьезного изменения кода. Код был в общественном использовании некоторое время, и последнее, что мы хотим сделать, это значительно изменить структуру и иметь плохую версию. И нет, у нас нет времени на тщательное тестирование (я в академической среде). В идеале мы надеемся, что сможем сделать это, не делая ничего более опасного, чем добавлять поля к узлу.

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

Спасибо!

EDIT: Для тех, кто интересуется, это будет в C. Да, я знаю, что мой псевдокод находится в некотором ужасно неудачном Python. Я как бы надеюсь, что язык не имеет значения.

Answer 1

Я думаю, что «ширина», которую вы рассматриваете здесь, на самом деле не то, что вы хотите - ширина зависит от того, как вы назначаете уровни каждому узлу, где у вас есть выбор. Вы заметили это, когда решали, следует ли назначать всем источникам уровень 0 или все приемники на максимальный уровень.

Вместо этого вы просто хотите подсчитать количество узлов и делить на «критический путь длины», который является самым длинным путем в даге. Это дает средний параллелизм для графика. Это зависит только от самого графика, и он по-прежнему дает вам представление о том, насколько широка диаграмма.

Чтобы вычислить длину критического пути, просто выполните то, что вы делаете - критическая длина пути - это максимальный уровень, который вы назначаете.

Answer 2

Вот что я (Platinum Azure, автор оригинала) до сих пор.

Препараты/Augmentations:

• Добавить "дети" поле для связанного списка ("DAG") узел
• поле Add "уровень" в "ДАГ" узел
• Добавить поле "children_left" в Узел «DAG». Это используется, чтобы убедиться, что все дети проверяются до того, как будет исследован родитель (на более поздней стадии алгоритма).

Алгоритм:

1. Найти число непосредственных детей для всех узлов; также, определять листья, добавляя узлы с детьми == 0 в список.

   for l in L: 
       l.children = 0 
   
   
   for l in L: 
       l.level = 0 
       for p in l.parents: 
       ++p.children 
   
   Leaves = [] 
   for l in L: 
       l.children_left = l.children 
       if l.children == 0: 
       Leaves.append(l) 
   

2. Назначьте каждому узлу уровень «обратной глубины». Обычно по глубине я имею в виду топологически сортировку и присваивание depth = 0 узлам без родителей. Тем не менее, я думаю, мне нужно отменить это, с глубиной = 0, соответствующей листьям. Кроме того, мы хотим убедиться, что ни один узел не добавлен в очередь, пока все его дети не «смотрят на него» сначала (чтобы определить его надлежащий «уровень глубины»).

   max_level = 0 
   while !Leaves.empty(): 
       l = Leaves.pop() 
       for p in l.parents: 
       --p.children_left 
       if p.children_left == 0: 
        /* we only want to append parents with for sure correct level */ 
        Leaves.append(p) 
       p.level = Max(p.level, l.level + 1) 
       if p.level > max_level: 
        max_level = p.level 
   

3. Теперь, когда каждый узел имеет уровень, просто создать массив, а затем пройти через список еще раз, чтобы подсчитать число узлов на каждом уровне.

   level_count = new int[max_level+1] 
   for l in L: 
       ++level_count[l.level] 
   
   width = Max(level_count) 
   

---

Так вот что я имею в виду до сих пор. Есть ли способ улучшить его? Это линейное время полностью, но у него есть пять или шесть линейных сканирований, и, вероятно, будет много промахов в кеше и тому подобное. Я должен задаться вопросом, нет ли способа использовать какую-либо локацию с лучшей структурой данных - без фактического изменения базового кода за пределами расширения узла.

Любые мысли?

Answer 3

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

1. Создать матрицу смежности для графа с использованием родительских данных (должно быть легко)
2. Выполнить топологическую сортировку, используя эту матрицу. (или даже использовать tsort, если нажать для времени)
3. Теперь, когда у вас есть топологическая сортировка, создайте уровень массива, один элемент для каждого узла.
4. Для каждого узла:
   • Если узел имеет нет родителей установить свой уровень до 0
   • В противном случае установите его к минимуму уровня его родителям + 1.
5. Найти максимальную ширину уровня ,

Вопрос в том, как Кит Рэндалл спросил, это правильное измерение, которое вам нужно?