Как уменьшить количество пересекающихся ребер на диаграмме?

10

Я работаю над редактором диаграмм. Диаграммы отображают 2D фигуры ( узлы ), связанные с соединителями ( ребрами ).

Я хотел бы добавить операцию, которая, учитывая выбор узлов, «распутывает» их: она перемещает их, чтобы уменьшить количество пересекающихся ребер, если это возможно (и это нормально, если ребра должны быть нарисованы с точками изгиба) ,

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

Читая о графиках вершин и просматривая Cabello и Mohar (2013) , я полагаю, что эта проблема является NP-сложной. Поэтому я буду доволен параметризованным алгоритмом (например, по количеству пересекающихся ребер), который имеет известную полиномиальную временную сложность для любого заданного значения параметра. Это кажется возможным, но мне нелегко придумать такой алгоритм самостоятельно.

Вопросов:

  • Где мне искать такой алгоритм?
  • Это существует?
  • В существующем программном обеспечении?
  • Есть ли значительный практический опыт такой операции? (То, что хорошо выглядит в теории, может быть не очень хорошо на практике, или наоборот.)

(Я не уверен, где лучше задать этот вопрос: здесь, в StackOverflow или MathOverflow?)

reinierpost
источник
1
Я бы предположил, что этот вопрос лучше подходит для StackOverflow, но я заметил, что на подобные вопросы есть неудовлетворительные ответы. Я приведу ответ, который должен помочь вам в теоретическом плане, но, возможно, будет лучше перенести ваш вопрос туда.
mdxn
Здесь проделана очень глубокая работа: complang.tuwien.ac.at/cd/ebner/ebner05da.pdf
Дшони,
Спасибо! Не только это, но это явно очень читаемое представление проблемы и обзор некоторых известных подходов.
Reinierpost

Ответы:

9

NP-трудной

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

Ресурсы:
Вас могут заинтересовать следующие ресурсы, особенно первые:

Есть также много других ресурсов. Это должно помочь вам начать.

Дополнительные мысли и наблюдения:

Вот идея, чтобы обойти вопросы, касающиеся формы и размера узлов. Учитывая график (бесконечно малые узлы), расширяйте каждый узел, одновременно «выталкивая» или сгибая края (например, используя сплайны, применяя ограничение на близость). Вы должны сделать это с другими ребрами и узлами, которые мешают этому, что может запустить цепную реакцию. Посмотрите, как эффективно вычислять равновесия (например, молекулярные структуры). Если вы не можете получить форму узла до нужного размера, масштабируйте всю диаграмму.

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

mdxn
источник
Я добавил топологию в свой вопрос специально, чтобы избежать обсуждения эстетики. Это важно, но я не думаю, что они сильно влияют на основную проблему - я думаю, что их можно рассмотреть на отдельном шаге, после настройки топологии узлов (то есть какие узлы окружены какими другими узлами).
reinierpost
Я впервые использовал Graphviz более 15 лет назад; Я использую это примерно один раз в неделю для всех видов графиков. Я не слишком впечатлен его результатами, и я понимаю, что трудно сделать намного лучше.
reinierpost
Я часто посещаю graphviz.org, и я прочитал некоторые статьи, на которые они ссылаются. Но я еще не встретил ответ на этот конкретный вопрос, и в моей должностной инструкции нет знакомства с литературой. Вот почему я спрашиваю это здесь.
reinierpost
Спасибо за ссылки, хотя - я заметил, что это все еще текущее исследование .
reinierpost
Первое, что я попробую, это тривиальный (и поэтому не обязательно полезный) алгоритм, примерно основанный на идее мисс Шаббер. Еще раз спасибо.
reinierpost