Недавно столкнулась с проблемой визуализации графа и оказалось, что есть большое количество алгоритмов для этого. Начнем по порядку.
Визуализация или отображение графов, как ответвление теории графов, относящееся к топологии и геометрии — двумерное представление графа. В основном, это графическое представление укладки графа на плоскость (как правило, допускаются пересечение рёбер), направленное, обычно, на удобное отображение некоторых свойств графа, или моделируемого объекта.
В связи с большим разнообразием видов графов, существует множество различных способов отображения графов.
Можно выделить следующие способы отображения:
— произвольное;
— прямолинейное — рёбра представляются отрезками;
— сеточное — предполагает, что все вершины, а также все точки пересече¬ния и сгибы ребер имеют целочисленные координаты, т. е. находятся в узлах коорди¬натной сетки, образованной прямыми, параллельными координатным осям и пересе¬кающими их в точках с целочисленными координатами;
— полигональное или полилинейное — для отображения рёбер используются ломаные;
— ортогональное — рёбра представляются ломаными, отрезки которых — вертикальные или горизонтальные линии;
— планарное или плоское – изображение предполагает отсутствие точек пересечения у линий, изображающих ребра;
— восходящее или низходящее — восходящее (соответственно нисходящее) изображение имеет смысл по отношению к ациклическому орграфу и предполагает, что каждое ребро орграфа изобра¬жается кривой, которая монотонно не убывает (соответственно не возрастает) в вер¬тикальном направлении. В частности, изображение является строго восходящим (со-ответственно строго нисходящим), если каждая кривая, изображающая дугу, строго возрастает (соответственно убывает) в вертикальном направлении.
Эстетические критерии определяют параметры отображения. Наиболее распространённые среди них:
— пересечения: минимизация общего числа пересечений рёбер. В идеале, если это возможно, должно быть получено планарное отображение;
— области: минимизация размеров областей;
— общая длина рёбер: минимизация суммарной длины всех рёбер;
— максимальная длина рёбер;
— универсальная длина рёбер: минимизация различий в длинах рёбер;
— общее число изгибов: уменьшение общего числа изгибов;
— максимальное число изгибов;
— угловое разрешение;
— характеристическое отношение;
— cимметрия.
Большинство методологий рисования графа основывается на следующих простых наблюдениях:
— эстетические критерии часто противоречат друг другу и, таким образом, поиски компромиссов неизбежны;
— даже если эстетические критерии не конфликтуют, часто алгоритмически трудно удовлетворить всем им одновременно.
Имеется ряд методов, которые позволяют получить удовлетворительные решения задач визуализации графов.
Основными среди них являются следующие:
1) планаризация. Плоские расположения обычно более привлекательны, чем неплоские. Плоские расположения являются весьма важными в технологиях печатных плат с точки зрения минимизации размещения. К сожалению, на практике многие графы не являются планарными. Можно пытаться сделать граф планарным либо удаляя из него как можно меньше ребер (эта проблема является NP-полной), либо удалением тех ребер, чья вставка впоследствии может создать наименьшее число пересечений. Эта проблема минимизации пересечений является в общей постановке NP-трудной, но есть некоторые эвристики, которые позволяют получать вполне удовлетворительные результаты;
2) использование физических аналогий. Эти методы интерпретируют граф при построении его изображения как физическую систему с силами между вер¬шинами и пытаются минимизировать энергию системы для получения хорошего ри¬сунка. Такого типа алгоритмы используются для рисования произвольных (разреженных) сетей, таких как блок-схемы, графы программного планирования, графы телефонных вызовов и т. п. Они также применяются для кластерных изображений;
3) Cигаяма-подобные методы. Наиболее широко используемыми алгоритмами для поуровневого рисования графов являются алгоритмы, относящиеся к классу, предло¬женных Сигаямой. Они производят поуровневые (или иерархические) изображения, пытаясь также минимизировать количество пересечений или размер области разме¬щения;
4) потоковые методы. Проблема минимизации числа сгибов может эффективно ре¬шаться путем сведения ее к задаче потока в сети, по крайней мере в тех случаях, когда зафиксирована топология размещения. Те же самые методы мо¬гут применяться для максимизации углов между ребрами.
Подробнее эти методы будут рассмотрены далее.
Визуализация или отображение графов, как ответвление теории графов, относящееся к топологии и геометрии — двумерное представление графа. В основном, это графическое представление укладки графа на плоскость (как правило, допускаются пересечение рёбер), направленное, обычно, на удобное отображение некоторых свойств графа, или моделируемого объекта.
В связи с большим разнообразием видов графов, существует множество различных способов отображения графов.
Можно выделить следующие способы отображения:
— произвольное;
— прямолинейное — рёбра представляются отрезками;
— сеточное — предполагает, что все вершины, а также все точки пересече¬ния и сгибы ребер имеют целочисленные координаты, т. е. находятся в узлах коорди¬натной сетки, образованной прямыми, параллельными координатным осям и пересе¬кающими их в точках с целочисленными координатами;
— полигональное или полилинейное — для отображения рёбер используются ломаные;
— ортогональное — рёбра представляются ломаными, отрезки которых — вертикальные или горизонтальные линии;
— планарное или плоское – изображение предполагает отсутствие точек пересечения у линий, изображающих ребра;
— восходящее или низходящее — восходящее (соответственно нисходящее) изображение имеет смысл по отношению к ациклическому орграфу и предполагает, что каждое ребро орграфа изобра¬жается кривой, которая монотонно не убывает (соответственно не возрастает) в вер¬тикальном направлении. В частности, изображение является строго восходящим (со-ответственно строго нисходящим), если каждая кривая, изображающая дугу, строго возрастает (соответственно убывает) в вертикальном направлении.
Эстетические критерии определяют параметры отображения. Наиболее распространённые среди них:
— пересечения: минимизация общего числа пересечений рёбер. В идеале, если это возможно, должно быть получено планарное отображение;
— области: минимизация размеров областей;
— общая длина рёбер: минимизация суммарной длины всех рёбер;
— максимальная длина рёбер;
— универсальная длина рёбер: минимизация различий в длинах рёбер;
— общее число изгибов: уменьшение общего числа изгибов;
— максимальное число изгибов;
— угловое разрешение;
— характеристическое отношение;
— cимметрия.
Большинство методологий рисования графа основывается на следующих простых наблюдениях:
— эстетические критерии часто противоречат друг другу и, таким образом, поиски компромиссов неизбежны;
— даже если эстетические критерии не конфликтуют, часто алгоритмически трудно удовлетворить всем им одновременно.
Имеется ряд методов, которые позволяют получить удовлетворительные решения задач визуализации графов.
Основными среди них являются следующие:
1) планаризация. Плоские расположения обычно более привлекательны, чем неплоские. Плоские расположения являются весьма важными в технологиях печатных плат с точки зрения минимизации размещения. К сожалению, на практике многие графы не являются планарными. Можно пытаться сделать граф планарным либо удаляя из него как можно меньше ребер (эта проблема является NP-полной), либо удалением тех ребер, чья вставка впоследствии может создать наименьшее число пересечений. Эта проблема минимизации пересечений является в общей постановке NP-трудной, но есть некоторые эвристики, которые позволяют получать вполне удовлетворительные результаты;
2) использование физических аналогий. Эти методы интерпретируют граф при построении его изображения как физическую систему с силами между вер¬шинами и пытаются минимизировать энергию системы для получения хорошего ри¬сунка. Такого типа алгоритмы используются для рисования произвольных (разреженных) сетей, таких как блок-схемы, графы программного планирования, графы телефонных вызовов и т. п. Они также применяются для кластерных изображений;
3) Cигаяма-подобные методы. Наиболее широко используемыми алгоритмами для поуровневого рисования графов являются алгоритмы, относящиеся к классу, предло¬женных Сигаямой. Они производят поуровневые (или иерархические) изображения, пытаясь также минимизировать количество пересечений или размер области разме¬щения;
4) потоковые методы. Проблема минимизации числа сгибов может эффективно ре¬шаться путем сведения ее к задаче потока в сети, по крайней мере в тех случаях, когда зафиксирована топология размещения. Те же самые методы мо¬гут применяться для максимизации углов между ребрами.
Подробнее эти методы будут рассмотрены далее.