Теоретико-графовые методы в программировании

Касьянов В.Н.

Введение

Теория графов стала активно применяться на заре программирования в силу удобного выражения задач обработки информации на теоретико-графовом языке. Расширение круга задач, решаемых на ЭВМ, потребовало выхода на модели дискретной математики, что привело к подлинному расцвету теории графов и комбинаторики, которые за прошедшие полвека трансформировались из разделов «досуговой» математики в первостепенный инструмент решения огромного числа задач. Академик Андрей Петрович Ершов, основатель сибирской школы информатики и программирования, называл графы основной конструкцией для программиста и говорил, что «графы обладают огромной, неисчерпаемой изобразительной силой, соразмерной масштабу задачи программирования».

Современное состояние программирования нельзя представить себе без применения теоретико-графовых методов и алгоритмов. Широкая применимость графов связана с тем, что они являются очень естественным средством объяснения сложных ситуаций на интуитивном уровне. Эти преимущества представления сложных структур и процессов графами становятся еще более ощутимыми при наличии хороших средств их визуализации. Поэтому неслучайно в настоящее время одним из наиболее актуальных направлений применения графов в программировании является визуализация информации на основе графов и графовых моделей [5–9].

Доклад начинается с описания вклада академика А. П. Ершова в становление и развитие теоретико-графовых моделей и методов в программировании. Далее рассматриваются вопросы визуализации информации на основе графов и графовых моделей. Доклад завершается рассмотрением работ по созданию электронного словаря по графам в информатике WikiGRAPP и электронной энциклопедии графовых алгоритмов WEGA, которые ведутся в Институте систем информатики им. А. П. Ершова СО РАН при финансовой поддержке Российского фонда фундаментальных исследований (грант РФФИ № 09-07-0012).

1. А. П. Ершов и графы в программировании

Трудно переоценить вклад А. П. Ершова в становление и развитие теоретико-графовых моделей и методов в программировании [4]. Среди первых работ, существенно использующих теоретико-графовые методы в решении задач программирования, можно отметить широко известные работы А. П. Ершова по организации вычисления арифметических выражений (1958 г.), граф-схемной модели для императивных программ в виде операторных алгоритмов (1958–1962 гг.), теории схем Янова с использованием их графового представления и концепции так называемой разметки (1966–1968 гг.) и граф-схемной теории экономии памяти (1961–1966, 1972 г.).

Первой книгой, посвященной применению графов в программировании, была изданная в 1977 г. монография А. П. Ершова [3], в которой он рассмотрел две классические задачи теоретического программирования, решения которых и развитые на этих решениях методы привели к созданию теоретического программирования как самостоятельной математической дисциплины. Это задача экономии памяти в операторных схемах Лаврова и задача построения полной системы преобразований в схемах Янова. В данной книге, написанной в виде беседы с читателем, Андрей Петрович продемонстрировал применение графовых методов к решению задач программирования в действии, начиная с элементарных постановок решаемых задач и кончая полным решением проблем во всей их сложности.

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

Поэтому не случайно, что в отличие от Москвы, где, начиная с работ Юрия Ивановича Янова, в большей степени развивался логический подход к программированию, или Киева, где в работах Виктора Михайловича Глушкова и его учеников явно прослеживается приоритет алгебраических методов, Новосибирск стал центром применения графовых моделей и методов в программировании. Созданная в Новосибирске академиком А. П. Ершовым и его учениками авторитетная школа программирования, пользующаяся мировой известностью, внесла значительный вклад в становление и развитие теоретического и системного программирования с использованием теоретико-графовых методов.

2. Графы и визуализация информации

Теория графов из академической дисциплины все более превращается в средство, владение которым становится решающим для успешного применения компьютеров во многих прикладных областях. Одно из основных современных направлений применения теоретико-графовых методов связано с вопросами визуализации обрабатываемой информации [5–9].

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

Активная разработка методов и средств визуализации графов началась во второй половине 80-х годов прошлого столетия. Это было связано, с одной стороны, с возросшей потребностью оперировать с большими объемами информации и сложными структурами данных, которые достаточно естественным образом представляются графами, а с другой стороны, с существенным прогрессом в развитии аппаратных средств, позволившим сделать графический интерфейс и компьютерную графику удобным и эффективным средством общения человека с компьютером.

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

Граф может рисоваться на плоскости или в трехмерном пространстве. Он может изображаться целиком, частично или иерархически, например, путем стягивания некоторых его подграфов в вершины, которые могут раскрываться по требованию. Изображения графа могут быть не только статическими, но и интерактивными, поддерживающими различные способы навигации, адекватные потребностям пользователя. Интерактивная визуализация может быть вызвана не только динамическим характером работы с визуальным представлением графа в приложении, но и большим размером визуализируемого графа. Если число элементов графа велико, его обработка может занимать неприемлемо большие ресурсы или даже достигать предельных возможностей используемой для визуализации платформы. Даже если возможно разместить и показать все элементы большого графа, часто возникают проблемы наглядности и удобства, поскольку в таком изображении графа становится невозможным различать его элементы и их взаимосвязи. Интерактивная визуализация превращает статическую демонстрацию визуального представления информации в непрерывный процесс взаимодействия пользователя с информацией через её визуальное отображение и доступные ему методы навигации. Пользователь может исследовать, рассматривать, открывать, узнавать данные и манипулировать ими через визуальные метафоры и с помощью навигаций.

Исследования в области визуализации графов и графовых моделей проводятся широким фронтом и имеют обширные и все более разнообразные сферы приложения. В работе [9] перечисляются в качестве основных источников, содержащих результаты этих исследований, такие журналы, как 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. Такая разбросанность исследований по журналам и конференциям, относящимся к весьма разной тематике, усложняет поиск подходящих методов визуализации при создании систем, использующих визуализацию графовых моделей, а также затрудняет объединение полученных результатов в единую теорию и/или структурированное множество методологий.

3. Средства поддержки графов в программировании

Проблема терминологии, без сомнения, является одной из основных проблем в применении теоретико-графовых методов в программировании и информатике.

В 1999 году в издательстве «Наука» вышел в свет наш «Толковый словарь по теории графов и её применении в информатике и программировании» [1], который охватывал основные связанные с графами термины из монографий, вышедших на русском языке. Это был первый словарь по графам в информатике, и он вызвал большой интерес среди читателей. Изданный нами в 2009 году новый словарь [2] представляет собой расширение словаря 1999 года и включает в себя более 1000 новых терминов из статей, рефераты которых публиковались в РЖ «Математика» в разделе «Теория графов», а также из томов ежегодных конференций «Graph- Theoretic Concepts in Computer Science» и книг серии «Graph Theory Notes of New York».

Мы отдаем себе отчет в постоянно развивающемся теоретико-графовом лексиконе в информатике и поэтому одновременно с завершением работ по подготовке второго словаря к изданию приступили к созданию на базе наших словарей расширяемого электронного словаря WikiGRAPP [11].

Другая вики-система, которая, также как и вики-словарь WikiGRAPP, создается нами с использованием MediaWiki [10], – это электронная энциклопедия графовых алгоритмов WEGA. В отличие от Д. Кнута, при создании данной энциклопедии мы, как и в книге [5], на которой базируется наша энциклопедия, ориентируемся на абстрактную модель современных ЭВМ (равнодоступная адресная машина – РАМ) и высокоуровневое описание алгоритмов в терминах специального языка высокого уровня – ВУ-языка. Этот язык является псевдоязыком (лексиконом) программирования и позволяет использовать любые необходимые конструкции математики и языков программирования, если очевидны или заранее зафиксированы оценки их сложности, а также те реализации этих конструкций на РАМ, которые допускают такие оценки. Такой подход позволяет формулировать алгоритмы в естественной форме, допускающей прямой анализ их корректности и сложности, а также простой перенос алгоритмов на реальные языки программирования и ЭВМ с сохранением полученных оценок сложности. Подобный стиль описания алгоритмов является также базой для доказательного стиля программирования: он позволяет понять алгоритм на содержательном уровне, оценить пригодность его для решения конкретной задачи и осуществить модификацию алгоритма, не снижая степень математической достоверности окончательного варианта программы.

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

Благодарности.

Данная работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант РФФИ № 09-07-0012). Автор благодарен всем, кто принимает участие в выполнении проектов, рассмотренных в данном докладе, в первую очередь проф. В. А. Евстигнееву и доц. Е. В. Касьяновой.

Список литературы

1. Евстигнеев В. А., Касьянов В. Н. Толковый словарь по теории графов в информатике и программировании. – Новосибирск: Наука, 1999. – 288 с.
2. Евстигнеев В. А., Касьянов В. Н. Словарь по графам в информатике. – Новосибирск: Сибирское Научное Издательство, 2009. – 300 с.
3. Ершов А. П. Введение в теоретическое программирование (беседы о методе). – М.: Наука, 1977. – 288 с.
4. Касьянов В. Н. Ершов и графы в программировании // Андрей Петрович Ершов – ученый и человек. – Новосибирск: Изд-во СО РАН, 2006. – С.150–157.
5. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ- Петербург, 2003. – 1104 с.
6. Касьянов В. Н., Касьянова Е. В. Визуализация графов и графовых моделей. – Новосибирск: Сибирское Научное Издательство, 2010. – 123 с.
7. Di Battista G., Eades P., Tamassia R., Tollis I.G. Graph Drawing: Algorithms for Vizualization of Graphs. – Prentice Hall, 1999. – 397 p.
8. Drawing Graphs. Methods and Models. – Berlin: Springer, 2001. – 312 p. – (Lect. Notes Comput. Sci.; 2025).
9. Herman I., Melançon G., Marshall M. S. Graph visualization and navigation in information visualization: a survey // IEEE Trans. on Visualization and Computer Graphics. – 2000. – Vol. 6. – P. 24–43.
10. MediaWiki. – http://www.mediawiki.org/wiki/MediaWiki/ru/
11. WikiGRAPP. – http://pco.iis.nsk.su/WikiGrapp/

Об авторе: Институт систем информатики им. А.П. Ершова СО РАН, Новосибирск
kvn@iis.nsk.su
Материалы международной конференции SORUCOM 2011 (12–16 сентября 2011 года)
Статья помещена в музей 22.11.2012 с разрешения авторов