Самый быстрый алгоритм для планаризации графа
Я использую Processing для разработки навигационной системы для сложных данных и процессов. В рамках этого я довольно глубоко погрузился в макет графика. Это все забавно, и мои мнения об алгоритмах компоновки таковы: сила направлена на бабу (просто посмотрите на ее масштаб... ха-ха), проекция на собственный вектор классная, слои Sugiyama выглядят хорошо, но быстро на графических графиках терпят неудачу, и хотя я полагался до сих пор на собственных векторах мне нужно минимизировать пересечения ребер, чтобы действительно добраться до точки данных. Я знаю, я знаю NP-полный и т. Д.
Я должен добавить, что у меня есть некоторый хороший успех от применения xy- бокса и использования Sugiyama-подобной перестановки для уменьшения пересечения ребер в строках и столбцах. То есть график (|V|=90, средняя степень log|V|) может идти от 11000 пересечений -> 1500 (по штучным собственным векторам) -> 300 путем чередования перестановок строк и столбцов для уменьшения пересечений.
Но локальные минимумы... что бы это ни было, все это находится вокруг этой отметки, и результат не так ясен, как мог бы быть. Мое исследование освещенного вопроса подсказывает мне, что я действительно хочу использовать алгоритм планаризации, подобный тому, который они используют для СБИС:
- Используйте BFS или что-то еще, чтобы сделать максимальный плоский подграф 1.a. Компоновка плоского подграфа
- Умно добавьте выдающиеся ребра, чтобы восстановить исходный график
Пожалуйста, ответьте с вашими мыслями о самом быстром алгоритме планаризации, вы можете углубиться в некоторые конкретные оптимизации, с которыми вы уже знакомы.
Спасибо!
2 ответа
Учитывая, что все графики не являются плоскими (что вы знаете), может быть, лучше использовать подход "следующий лучший", чем подход "всегда дает лучший ответ".
Я говорю это потому, что у моего соседа по комнате в аспирантуре была та же проблема, что и у вас. Он пытался преобразовать график в плоскую форму, и все алгоритмы, гарантирующие минимальное пересечение ребер, были слишком медленными. Что он в итоге делал, что просто реализовывал рандомизированный алгоритм. По сути, выкладывайте график, затем двигайте узлы, у которых есть ребра с множеством пересечений, и в итоге вы справитесь с наихудшими скоплениями ребер.
Преимущества заключались в следующем: вы можете отключить его через определенное время, поэтому, если вы ограничены во времени, это всегда занимает меньше определенного времени, если вы получаете дрянной график, вы можете просто запустить его снова (в течение уже выложенный график), чтобы получить что-то лучше, и это относительно легко кодировать.
Недостаток в том, что вы не всегда получаете глобальные минимумы в пересечениях, и если график застревает в областях с пересечением, его алгоритм иногда отбрасывает узел далеко на расстояние, чтобы попытаться разрешить его, что иногда вызывает действительно странные графы,
Вы уже знаете много разметки графика, но я думаю, что ваш вопрос все еще, к сожалению, недостаточно конкретизирован.
Вы можете очень быстро выровнять любой график, выполнив следующие действия: (1) случайное расположение графика на плоскости (2) вычисление места пересечения ребер (3) создание псевдоверш на пересечениях (это то, что вы в любом случае делаете, когда используете планарность) основанный макет для неплоских графов) (4) график, расширенный новыми вершинами и разделенными ребрами, автоматически является плоским.
Первая трудность возникает из-за наличия алгоритма, который вычисляет комбинаторное вложение, которое минимизирует количество пересечений ребер. Вторая сложность заключается в использовании этого комбинаторного встраивания для создания макета в евклидовой плоскости, визуально привлекательного, например, для макета ортогонального графа вы можете минимизировать количество изгибов, максимизировать размер граней, минимизировать площадь графа в целом, и т.д., и эти цели могут противоречить друг другу.