След.: Оглавление Выше: Визуализация информации на основе Пред.: Предисловие Содержание
Современное состояние программирования нельзя представить себе без применения теоретико-графовых методов и алгоритмов. Среди первых работ, существенно использующих теоретико-графовые методы в решении задач программирования, можно отметить широко известные работы А. П. Ершова по организации вычисления арифметических выражений (1958 г.), граф-схемной модели для императивных программ в виде операторных алгоритмов (1958-1962 гг.), теории схем Янова с использованием их графового представления и концепции так называемой разметки (1966–1968 гг.) и граф-схемной теории экономии памяти (1961–1966, 1972 гг.).
Широкая применимость графов в программировании и информатике связана с тем, что они являются естественным средством объяснения сложных ситуаций на интуитивном уровне. Эти преимущества представления сложных структур и процессов графами становятся более ощутимыми при наличии хороших средств их визуализации. Поэтому неслучайно в последнее время в мире растет интерес к методам и системам рисования и визуальной обработки графов и графовых моделей. Многие программные системы, особенно те, которые используют информационные модели, включают элементы визуальной обработки графовых объектов. Среди них — системы и окружения программирования, инструменты CASE-технологии, системы автоматизации проектирования и многие другие.
Теория графов из академической дисциплины все более превращается в средство, владение которым становится решающим для успешного применения компьютеров во многих прикладных областях. Визуализация информации на основе графовых моделей является ключевой компонентой во многих приложениях в науке и технике, а методы визуализации графов представляют собой теоретическую основу методов визуализации абстрактной информации. Методы и средства визуализации графов и графовых моделей широко используется в таких областях, как информационные системы и программное обеспечение, биологические науки, искусственный интеллект, анализ финансовой информации, компьютерное обучение и многие другие.
В зависимости от применения элементы 2(вершины и ребра) графа должны изображаться различными способами. Например, вершины могут быть нарисованы в виде точек, кругов, прямоугольников или других геометрических фигур либо представлены неявно — через имена, которыми вершины помечены. Аналогично имеется большое разнообразие рисования ребер: например, в виде отрезков прямых, ломаных линий или кривых.
Графовые изображения, как правило, предназначены для визуализации информационных моделей, обладающих семантикой. Информация, сопоставленная элементам графовой модели, может визуализироваться с использованием текстовых меток, расположенных внутри или рядом с их изображением, различными цветами или другими визуальными элементами, такими как, например, толщина линий, вид стрелок на дугах, формы или размеры фигур, изображающих вершины. Поэтому важным аспектом рисования графовых моделей является расположение меток вершин и ребер изображаемого графа. Помеченные (или, как иногда говорят, атрибутированные) графы широко применяются на практике: в транспортных схемах, диаграммах состояний, планах зданий и др. Граф может рисоваться на плоскости или в трехмерном пространстве. Он может изображаться целиком, частично или иерархически, например, путем стягивания некоторых его подграфов в вершины, которые могут раскрываться по требованию. Изображения графа могут быть не только статическими, но и интерактивными, поддерживающими различные способы навигации, адекватные потребностям пользователя. Интерактивная визуализация может быть вызвана не только динамическим характером работы с визуальным представлением графа в приложении, но и большим размером визуализируемого графа. Если число элементов графа велико, его обработка может занимать неприемлемо большие ресурсы или даже достигать предельных возможностей используемой для визуализации платформы. Даже если возможно разместить и показать все элементы большого графа, часто возникают проблемы наглядности и удобства, поскольку в таком изображении графа становится невозможным различать его элементы и их взаимосвязи. Интерактивная визуализация превращает статическую демонстрацию визуального представления информации в непрерывный процесс взаимодействия пользователя с информацией через её визуальное отображение и доступные ему методы навигации. Пользователь может исследовать, рассматривать, открывать, узнавать данные и манипулировать ими через визуальные метафоры с помощью навигаций.
Активная разработка методов и средств визуализации графов началась во второй половине 80-х гг. прошлого столетия. Это было связано, с одной стороны, с возросшей потребностью оперировать с большими объемами информации и сложными структурами данных, которые достаточно естественным образом представляются графами, а с другой стороны, с существенным прогрессом в развитии аппаратных средств, позволившим сделать графический интерфейс и компьютерную графику удобным и эффективным средством общения человека с компьютером.
В настоящее время вопросам визуальной обработки графов и графовых моделей посвящена обширная литература, а на рынке широко представлены наукоемкие программные продукты, использующие методы визуализации информации на основе графовых моделей (см., например, обзоры [1, 56, 99] и книги [9, 10, 57, 60]). Среди них есть как специализированные системы, ориентированные на визуализацию определенных подклассов графов и/или специальные применения, так и библиотеки и программные комплексы, предназначенные для визуализации графов общего вида и на-значения.
В последнее время с развитием науки о визуализации графов и её повсеместным распространением начали в большом количестве появляться системы, развивающие отдельные аспекты данного направления, считающиеся перспективными в настоящее время. В качестве примеров можно привести системы, использующие гиперболическую геометрию для построения изображений графов. Другим примером являются системы, работающие с трехмерными изображениями графов. Хотя до сих пор не создано полноценного редактора для такого представления, трехмерная визуализация графов уже давно используется на практике. Активно развиваемым в последние годы направлением является интерактивная визуализация очень крупных графов, т. е. графов с настолько большим числом вершин, что применение обычных статических методов визуализации для них практически невозможно. Данная проблематика не в последнюю очередь связана с популяризацией Интернета, развитием био- и бизнес-информатики и необходимостью вести исследования различного характера в области больших компьютерных сетей и с большим объемом структурированной информации.
Считается, что хорошая визуализация информации позволяет пользователям быстро находить нужный элемент в графе и понимать его отношение к контексту и обеспечивает возможность прямого доступа к информации, связанной с этим элементом. Общий процесс визуального исследования большого графа обычно начинается с выбора его раскладки для демонстрации всей информации целиком, которая позволяет пользователям полу-чить представление о ее глобальной структуре. Например, рассматривая всю структуру, пользователи могут понять некоторые интересные тенденции, кластеры или черты. Получив необходимое глобальное представление, пользователи переходят к следующему этапу исследования, в процессе которого они применяют подходящие методы навигации по изображению графа с целью изучения деталей, представляющих для них интерес. Описывая этот процесс, Бен Шнайдерман сформулировал “мантру” интерактивной визуализации следующим образом [179]: “Сначала общий план, потом масштабирование и фильтрация, затем детали по требованию”.
Исследования в области визуализации графов и графовых моделей проводятся широким фронтом и имеют обширные и все более разнообразные сферы приложения. В работе [99] перечисляются в качестве основных источников, содержащих результаты этих исследований, такие журналы, как Journal of Graph Algorithms and Applications (JGAA), IEEE Transactions on Visualization and Computer Graphics, Computational Geometry: Theory and Applications и Algorithmica, а также труды таких регулярных конференций, как Graph Drawing Symposia (GD), ACM Conference on Human Factors in Computing Systems (CHI), ACM Symposium on User Interface Software and Technology (UIST), IEEE Information Visualization Conference (InfoVis), Eurographics Workshop on Scientific Computing. Такая разбросанность исследований по журналам и конференциям, относящимся к весьма разной тематике, усложняет поиск подходящих методов визуализации при создании систем, использующих визуализацию графовых моделей, а также затрудняет объединение полученных результатов в единую теорию и/или структурированное множество методологий.