(N x M) Задача построения диаграмм

Question

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

У меня есть два набора узлов, N и M. Каждый узел n0 в N имеет от 0 до M соединений с уникальным (для n0) узлом в M. Эти наборы узлов должны быть расположены на двух параллельных горизонтальных линиях, с N узлов в линии над М узлами. Соединения будут нарисованы прямыми линиями от N до M.

Что мне нужно сделать, это переставить узлы N и M в пределах их горизонтальных линий, чтобы минимизировать пересечения. Есть ли какой-нибудь способ сделать это более эффективным, чем просто наивно перечислять все возможные меры, а именно O (N! * M!)? (на самом деле, это значительно хуже, так как каждое соединение также должно быть проверено на пересечение).

Ссылки на соответствующую литературу также приветствуются, хотя объяснение того, почему она актуальна, желательно.

---

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

1. ограничения диаграммы состоят в том, что соединения должны быть нарисованы как прямые линии от N до M. В теории графов это практически означает, что соединения не могут идти за узлы в N или M, только между ними. Таким образом, случай 2x2 с четырьмя соединителями может быть планаризован в общем случае двудольного графа, но не может в случае моей диаграммы.

2. Дополнительная информация состоит в том, что, если это не может быть планаризовано, мне все еще нужно решение с минимальным пересечением (или близко к нему). Как правило, алгоритмы минимального пересечения значительно отличаются от тех, которые только выравнивают.

Answer 1

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

Главное, что вам нужно изменить, это сделать принудительное выравнивание 1D вместо 2D, выравнивая только узлы по осям X вместо выравнивания узлов по X и Y.

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

http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)

Answer 2

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

Answer 3

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

Answer 4

Насколько велики N и M? Существует решение, основанное на динамическом программировании, которое выполняется за время O (мин (N, M)! * 2 ** макс (N, M) * poly (N, M)), но я не уверен, что это значительное улучшение по вашему мнению, грубая сила.