Макет графика для печати на бумаге

Question

Наше приложение отображает потенциально большие графики с множеством узлов и ребер. Мы используем такие вещи, как точка, конечно, для разметки графика, и они хорошо выглядят на экране. Тем не менее, пользователи хотели бы распечатать их на бумаге. Теперь технически мы можем сделать это, мы разбиваем график на маленькие изображения, и пользователи могут распечатать это. Но нет никакой гарантии, что, вырезая по размеру страницы, мы не собираемся прорезать узлы, иметь множество ребер между различными страницами и т. Д. Я ищу алгоритм, который бы изменил расположение графика так, будет более пригодным для печати: - убедитесь, что ни один узел не попадет на границы страницы - постарайтесь минимизировать края между страницами Кажется, что это похоже на поиск «кластеров» плотно связанных узлов для размещения на одной странице с небольшим количеством ребер, пересекающих другие страницы с другими кластерами. Кто-нибудь может указать мне соответствующую литературу / инструменты, чтобы делать такие вещи?

Спасибо

Answer 1

Кластерный анализ - хорошее начало.

Я бы предложил следующий способ обработки:

Сначала определите функцию стоимости:

С учетом перераспределения страниц: Стоимость (Перераспределение) = f (узлы вблизи границ, ребра с множеством страниц)

Целью будет минимизация этой функции.

выбрал алгоритм кластерного анализа:

определить алгоритм кластера (вы можете взглянуть на мой пост по DBSCAN: Код DBSCAN на C # или vb.net, для кластерного анализа и добавьте «страничное» ограничение к кластеризации. (размер страницы)

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

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

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