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

Question

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

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

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

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

Спасибо!

РЕДАКТИРОВАТЬ: Для всех, кто заботится, это будет в C. Да, яЯ знаю, что мой псевдокод в каком-то ужасно похожем на Python стиле.Я надеюсь, что язык на самом деле не имеет значения.

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

Вот что у меня (Platinum Azure, первоначальный автор) до сих пор.

Подготовка / дополнения:

• Добавление поля "children" в связанный список ("DAG")узел
• Добавить поле "level" в узел "DAG"
• Добавить поле 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. Назначьте каждому узлу уровень "обратной глубины".Обычно под глубиной я подразумеваю топологическую сортировку и присваиваю глубину = 0 узлам без родителей.Тем не менее, я думаю, что мне нужно изменить это, с глубиной = 0, соответствующей листьям.Кроме того, мы хотим убедиться, что ни один узел не будет добавлен в очередь без того, чтобы все его дочерние элементы сначала «смотрели на него» (чтобы определить его надлежащий «уровень глубины»).* Теперь, когда у каждого узла есть уровень, просто создайте массив и просмотрите список еще раз, чтобы подсчитать количество узлов на каждом уровне.

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

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

Есть мысли?