Швейцарский нож, или Визуализация графов

Все-таки швейцарский складной нож — гениальное изобретение. В нем замечательно
все. Кроме одной детали — писать о швейцарском ноже слишком трудно. Потому что
с его помощью можно делать многое. Слишком многое.

Складной нож можно просто носить в кармане и демонстративно открывать им пиво.
Логика такого поведения проста — возможность пренебрежительно использовать дорогую,
изящную и функциональную вещь подчеркивает социальный статус ее владельца. А еще
таким ножом можно чинить, резать, строгать, пилить… Как и, что главное, — зачем
обо всем этом писать? Особенно если нож бесплатный…

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

Почему графы?

Сравнительно давно к этой теме нам уже приходилось обращаться. А именно —
в ходе обсуждения идей метаязыка XML. Но все же повторения вводного материала
о том, что же такое графы и почему они так важны, не избежать. Ведь в случае с
XML графы были понятием утилитарным и слишком глубоко упрятанным за технологическими
особенностями далеко не простой разработки. Теперь нам предстоит поговорить о
графах вообще. Но начать придется с множеств и отношений — понятий сколь обширных
и фундаментальных, столь и необходимых для дальнейшего обсуждения.

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

А для классификационного принципа "вид растений" — множество

Если теперь внимательно взглянуть на эти два множества, то можно сделать "открытие":
"дуб" является представителем "деревьев", "лещина"
— "кустарников", "полынь" — "трав". Тривиальность
его не должна нас обманывать — мы образовали пары представителей двух множеств,
для которых высказывание "является представителем" истинно. Чтобы подчеркнуть
этот (уже не совсем тривиальный) факт, в математике часто используют следующую
(называемую предикативной) форму записи:

Не имеющим академической профессиональной подготовки программистам эта форма,
безусловно, должна напоминать запись… вызова функции с именем "является_представителем".
И действительно, большинство императивных (оперирующих понятиями переменных, значений,
процедур/функций) языков программирования унаследовали этот мощный математический
формализм, имеющий более общее в математике название — отношение.

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

В этом случае ЯВЛЯЕТСЯ_ПРЕДСТАВИТЕЛЕМ — это новое множество, описывающее
отношение, для всех элементов (пар) которого предикат "является_представителем"
— истинный. Оно формализует результат нашего "открытия" и, несмотря
на простоту, уже представляет ценность, скажем, для семилетнего ребенка. Потому
что на самом деле ЯВЛЯЕТСЯ_ПРЕДСТАВИТЕЛЕМ есть формализованное знание.

Но в реальной жизни численность элементов множеств (математический термин — мощность множеств), которыми приходится оперировать, огромна. Слишком велики и их количество, и сложность формализмов, лежащих в основе отношений. Соответственно, формализованные и записанные в приведенных выше формах отношения становятся просто необозримыми. Хорошо, если задача заключается просто в проверке истинности предиката отношения для нескольких элементов — здесь искусство программистов и быстродействие компьютеров помогают достаточно эффективно. Также успешно решается задача нахождения по одному или нескольким элементам остальных членов комбинации, удовлетворяющей предикату отношения (именно на этом, к слову, "специализируются" СУБД — Системы управления базами данных). А вот как быть в том случае, если возникает потребность увидеть все множество, представляющее отношение? Распечатка его на километровом рулоне не слишком привлекает не столько продолжительностью процедуры, сколько абсолютной бесполезностью процесса — ведь никакой наглядности в этой лавине не будет.

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

А вот "спрятавшаяся" в скобки скромная фраза "при некоторых допущениях", как всегда бывает в науке, скрывает за собой еще один очень непростой раздел, но уже вычислительной математики — теорию и практику graphdrawing, "рисования графов". Ведь если расположить точки, отображающие элементы множеств, абсолютно произвольно и соединить их прямыми линиями, можно добиться еще меньшей наглядности, чем в случае с километровым рулоном распечатки.

Если подвести итоги краткого и не претендующего на строгость экскурса в предметную область graphdrawing, можно заметить, что в ходе рассмотрения совершенно безотносительного к реальным задачам элементарного примера мы "вдруг" открыли и формальный способ представления знаний (реальные системы управления базами знаний и экспертные системы на самом деле недалеко от него ушли), и "неожиданную" аналогию между формой записи вызова процедуры/функции в языках программирования и предикативной формой записи отношения, и "страшную тайну" высокоуровневой модели баз данных. Не слишком ли много для такого примитивного примера? Вовсе нет — все, что обладает признаками структуры, иначе говоря, все, что образовано множеством элементов и связями между этими элементами (или некоторыми отношениями), является благодатной почвой и для теории множеств, и для теории графов, и, наконец, для успешного использования инструментов graphdrawing. И если немного задуматься, то универсальность швейцарского складного ножа теперь может показаться жалкой песчинкой по сравнению с целой планетой возможностей инструментов graphdrawing, позволяющих не просто увидеть наглядное изображение этой структуры, но и сделать массу по-настоящему интересных открытий. Впрочем, достоинства швейцарских ножей этот факт ни в коей мере не умаляет.

Хорошая книга — хороший инструмент

Если речь идет об инструментальном программном обеспечении, то совершенно
не лишним кажется и еще одно, пусть не столь необходимое, но все же полезное,
отступление. Действительно, что же такое "хороший инструмент"?

Такая знаменитая и такая непопулярная книга Кришнамурти…

Многообещающие возможности graphdrawing демонстрируются классической в системе X Window утилитой editres, предназначенной для настройки GUI–приложений. К сожалению, эта технология уходит в прошлое

Именно так неказисто выглядит сгенерированный dot граф для нашего примитивного примера

От простого до сверхсложного – один шаг. Граф, демонстрирующий и возможности атрибутов dot, и способ быстрой навигации по большим «рисункам» в dotty с помощью окна birdseye ("птичий глаз", в верхнем левом углу экрана)

Фрагмент очень большого графа, подготовленный к печати на PostScript–принтере, далеко не в полной мере демонстрирующий цветовые возможности атрибутов dgl

Очевидно, что он должен быть удобным в использовании, пропорционально спроектированным
— в том смысле, что затраты на освоение должны соответствовать выгодам, получаемым
за счет его применения. Хороший инструмент не должен зависеть от условий, в которых
мы работаем (ну что это за швейцарский нож, предназначенный "для использования
только в кондиционируемых помещениях"), не должен навязывать способ применения
(ограничение "только для работы правой рукой!" выглядит, по меньшей
мере, глупо). Ну и, наконец, хороший инструмент должен позволять делать то, что
он должен позволять делать, не больше и не меньше. И если в случае с инструментами
"вещественными" ситуацию можно назвать прекрасной — ведь такие инструменты
нужны всегда и практически всем, то отрасль программной инженерии, специализирующаяся
на создании программных инструментов, сегодня "не в фаворе". Пик инструментального
подхода к разработке ПО, вероятнее всего, остался в прошлом. Сегодня бал правят
Большие Приложения. Но graphdrawing — это как раз тот случай, когда самые большие
приложения оказываются "почти всегда не совсем тем, что нужно". Впрочем,
не будем забегать вперед…

В 1995 г. издательством John Wiley & Sons была выпущена книга, ставшая в своем роде бестселлером. Ее редактор — Балачандер Кришнамурти (Balachander Krishnamurthy) — является сотрудником знаменитой исследовательской лаборатории Bell Labs, а в написании материалов и ПО, сопровождающего этот труд, принимали участие одни из самых ярких программных инженеров прошлого (увы, уже прошлого) века, включая Б. Кернигана, Д. Ричи и Д. Корна. К сожалению (в данном случае), слово "бестселлер" — это не синоним к слову "библия", и "Practical reusable Unix Software" ("Прикладные повторно используемые программы Unix" — автор позволил себе несколько вольный, но точно отражающий содержание перевод названия), похоже, не стала настольной книгой современных разработчиков ПО. А жаль: многие ли новомодные разработки хоть в чем-то соответствуют фразе из предисловия к "Practical…", написанной Д. Ричи: "…Коллекция программ, потребность в которых была понятна многим, но возможность создания всегда игнорировалась"?

Но достаточно о грустном. Пора представить главного героя нашего повествования — набор инструментальных утилит под общим названием GraphViz. В книге Кришнамурти утилитам GraphViz посвящена не одна глава, так что можете не сомневаться — мастера разработки инструментального ПО потрудились на славу, и это действительно хороший инструмент (что позже автор попробует подтвердить). И не стоит пугаться слова Unix в названии книги — если уж титула "хороший инструмент" GraphViz удостоился, то и зависимость от "условий эксплуатации" — понятие для него чуждое. Главные утилиты GraphViz доступны как в исходных текстах, так и в виде исполняемых файлов (в том числе и для MS Windows), лицензия на это ПО более чем лояльна, размеры его невелики, а возможности… Вот так обычно и получается — хвалить не хотелось, а приходится.

Точка, точечка

Основа GraphViz — утилита с командным интерфейсом, называемая dot (точка).
Для интерактивной работы в состав GraphViz входит и надстройка над dot — редактор
графов dotty ("точечка", написанный с использованием кросс-платформенного
интерпретирующего языка Tcl и библиотеки примитивов графического интерфейса Tk).

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

Особенность алгоритмов, реализованных в dot, — весьма высокая наглядность получившегося изображения. Достигается она за счет так называемого иерархического подхода (о чем чуть позже). Несмотря на внешнюю простоту и небольшой размер исполняемого файла (почти 500 KB), dot реализует весьма непростой четырехэтапный логический процесс формирования изображения графа.

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

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

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

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

Как видите, dot — вовсе не элементарная программа. Но зато на пользовательском уровне… Для ее освоения нужен всего час времени и документация — ведь, по сути, вам понадобится изучить примитивный, но очень выразительный и соответствующий задачам язык описания графов dgl (dot graph language). А он, в отличие от многих языков описания данных, действительно прост. Основные понятия — граф, вершина графа — элемент множества с названием N, и ребро графа, соединяющее вершину N с вершиной M, описываются на dgl элементарно:

Никаких предварительных объявлений вершин или ребер (”->”) не требуется.
Так, наш пример из области ботаники на dgl можно записать так (REPRESENT заменяет
ЯВЛЯЕТСЯ_ПРЕДСТАВИТЕЛЕМ, hazel — лещина, absinth — полынь):

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

Останавливаться подробнее на атрибутах нет смысла — их описание, представленное в виде таблицы, занимает всего одну страничку в 21-страничном учебнике по dot, который стоит изучить хотя бы из-за подкупающей простоты, компактности описания и, наконец, имени знаменитой Bell Labs, в которой и была создана эта программа.

Что делать… с GraphViz

Это, пожалуй, самая интересная и спорная часть статьи. Инструментальный характер
GraphViz подсказывает, что этот набор программ нужен в первую очередь тем, чья
деятельность напрямую связана с использованием программных инструментов. Открытый
языковой ввод GraphViz является неоценимым подспорьем именно для этой категории
пользователей. Ведь программы на dgl совсем необязательно "писать вручную"
— они могут генерироваться (и, по большому счету, даже должны генерироваться)
сторонними инструментальными средствами. Их сложность может быть разной — от
так называемых "программ выходного дня" до больших программных комплексов.
Главное — генераторы dgl-моделей делаются один раз для решения тех самых проблем,
с которыми слишком многие сталкиваются, а адекватного ПО все же не существует.

Так, в руках программиста GraphViz превращается в мощнейшее средство документирования программ: достаточно изучить dgl и "изобрести" простенький скрипт, выделяющий из комментариев dgl-описания (или более высокоуровневые — почему бы не позаимствовать идею независимости описания структуры от представления и не взглянуть на документацию каскадных листов стилей CSS для HTML?) структуры программы, — и одним движением руки вы будете получать "на-гора" великолепное изображение, существенно облегчающее понимание, сопровождение и, следовательно, высокие потребительские качества программы. К слову, ничего подобного в самых интегрированных средах программирования не наблюдается, а решается задача высокоуровневого документирования обычно с помощью слишком сложных программных пакетов, время освоения которых несоизмеримо выше времени разработки собственного документирующего скрипта.

Еще одна очевидная возможность применения GraphViz в программировании — создание предпроектной документации. Конечно, "самодельные" решения в этом случае не сравнятся по функциям со специализированными системами, например UML-моделирования, но… Обилие возможностей далеко не всегда означает, что ими легко воспользоваться — продукты такого класса слишком сложны и дороги. И, как ни странно, но практика убедительно доказывает, что во многих случаях легковесное решение используется значительно эффективнее.

Более тонкий способ утилизации потенциальных возможностей graphdrawing — так называемое визуальное профилирование, очень эффективный способ отладки программ со сложной логикой. Заключается он или в наглядном графическом отображении результатов выполнения специальных отладочных средств — профиляторов (profilers), или во встраивании в отлаживаемую программу вызовов функций, генерирующих… да, тот же самый dgl-текст! Визуально анализируя полученный в результате выполнения отлаживаемой программы граф, можно выявить очень тонкие и неприятные логические ошибки.

Для системного администратора GraphViz дает возможность частично или полностью автоматизировать весьма трудоемкие, но необходимые процессы составления и поддержания в актуальном состоянии карты сети и визуализации настроек сложных системных сервисов.

Инженеры используют GraphViz для качественного отображения и печати так называемых BOM (Bills Of Materials) — перечней используемых материалов, подготовки сборочной документации. Конструкторы-электронщики часто "пропускают" через GraphViz трансформированные в dgl… описания топологии электронных схем перед выполнением процесса трассировки печатных плат — по мнению многих специалистов, алгоритмика dot весьма совершенна, и такой прием иногда позволяет "вручную" очень удачно скорректировать расположение элементов на плате.

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

Перечислять потенциальные области применения инструментов graphdrawing можно до бесконечности. Но… большинство из них остается все же потенциальными. Как ни странно, но даже в программировании, где "пользователи" graphdrawing достаточно профессиональны для быстрой реализации действительно нужных и полезных приложений, почти никакой активности не наблюдается.

Вариации и ресурсы

GraphViz — не единственная и не уникальная разработка в области graphdra-wing.
Выбрана автором она была по ряду простых причин, а именно из-за доступности, надежности
реализации и прекрасных возможностей. В области graphdrawing существуют и коммерческие
разработки (надо сказать, достаточно дорогие), и ряд проектов из области freeware,
но с весьма жесткими ограничениями по использованию.

Саму систему GrapViz можно загрузить с сайта www.graphviz.org,
расширенную документацию по ней — с сайта исследовательских лабораторий Bell
Labs, www.research.att.com/sw/tools/graphviz/,
подробно ознакомиться с техникой визуализации графов и состоянием этой области
можно на сайте graphdrawing.org, неплохой перечень доступных ресурсов graphdrawing
находится по адресу dmoz.org/Science/Math/Combinatorics/Software/Graph_Drawing/.