Март 9

Graphviz – рисуем графы

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

Сама программа бесплатна и может быть скачена по ссылке.  После установки в Windows в меню “Пуск” появится приложение gvedit, которое является графическим интерфесом к установленному пакету программ. В Mac OS X такого не произойдет и обходное решение описано ниже (если, конечно, вы не готовы работать в терминале).

Рассмотрим направленный граф, описывающий все возможные коммуникации между четырьмя участниками проекта. Листинг, описывающий граф привожу ниже:

digraph test{
   1->2;
   1->3;
   1->4;
   2->1;
   2->3;
   2->4;
   3->1;
   3->2;
   3->4;
   4->1;
   4->2;
   4->3;
}

В приложении это будет выглядеть следующим образом:

bezymyannyy_1

 

В данном случае, был использован параметр по умолчанию и для построения графа использована утилита dot.

Для примера, тот же граф, построенный с помощью:

test_1 test_2 test_3
circo fdp twopi

Подробнее это описано в документации на сайте. Если кратко, то dot, а далее в статье используется только он, рисует граф в заданном в порядке ветвления; twopi – использует радиальное построение, когда вершины располагаются на концентрических окружностях, circo – связанные вершины располагаются по кругу.

В данном случае, у нас был изображен орграф. Если граф не ориентирован, иными словами “стрелочки” на рисунке нам не важны, то граф описывается следующим образом (обратите внимание на первой слово “graph” вместо “digraph”, как задаются связи (“–” вместо “->”), а также на команду node [shape = box] – задающую прямоугольники в качестве вершин). Несомненно, формат стрелок можно определить и в самом графе на языке dot, но алгоритмы построения для ориентированных и неориентированных графов имеют небольшое отличие.

graph test{
   node [shape = box];
   "Проект А"--"Фаза 1";
   "Проект А"--"Фаза 2";
   "Проект А"--"Фаза 3";
   "Фаза 1"--"Задача 1";
   "Фаза 1"--"Задача 2";
   "Фаза 2"--"Задача 3";
   "Фаза 2"--"Задача 4";
}

Результат выглядит так:

test_4

Пример из заметки по динамическому программированию: меняем ориентацию графа (строится справа налево), добавляем подписи и стили линий и задаем размер листа.

digraph ex01 {
    rankdir=LR;
    size="8,5"
    node [shape = box];
    "1" -> "2" [ label = "3",style=bold,color=red ];
    "1" -> "3" [ label = "7",style=dotted];
    "1" -> "4" [ label = "2",style=dotted ];
    "2" -> "5" [ label = "9",style=dotted ];
    "2" -> "6" [ label = "11",style=bold,color=red ];
    "3" -> "5" [ label = "5",style=dotted ];
    "3" -> "6" [ label = "10",style=dotted ];
    "3" -> "7" [ label = "7",style=dotted ];
    "4" -> "6" [ label = "15",style=dotted ];
    "4" -> "7" [ label = "13",style=dotted ];
    "5" -> "8" [ label = "7",style=dotted ];
    "5" -> "9" [ label = "5",style=dotted ];
    "6" -> "8" [ label = "3",style=bold,color=red ];
    "6" -> "9" [ label = "4",style=dotted ];
    "7" -> "8" [ label = "7",style=dotted ];
    "7" -> "9" [ label = "1",style=dotted ];
    "8" -> "10" [ label = "1",style=bold,color=red ];
    "9" -> "10" [ label = "4",style=dotted ];
}

step4-1

 

Более сложные пример приведен в заметке по методу анализа иерархии.

При выборе формата записи результирующего графа, определенный интерес представляет формат svg в поле Output File Type. Формат svg — векторный формат, файлы в этом  формате можно редактировать, например, с помощью Inkscape.  Также обратите внимание на векторный формат emf, позволяющий внедрять и масштабировать рисунки в Word без потери качества. Для этого сайта был использован растровый формат png.

bezymyannyy_2

И последний пример, использование структуры в качестве вершины графа.

digraph structs { 
    node [shape=record, style="rounded,filled"];
    struct1 [label="<f0> Инициация|<f1> Планирование|<f2> Исполнение|<f3> Завершение",
             fillcolor=yellow];
    struct2 [label="<f0> Мониторинг|<f1> Контроль"]; 
    struct1:f0-> struct2:f0;
    struct1:f1-> struct2:f0;
    struct1:f2-> struct2:f0;
    struct1:f3-> struct2:f0;
    struct2:f1 -> struct1:f0 [color="red"];
    struct2:f1 ->struct1:f1 [color="red"];
    struct2:f1 ->struct1:f2 [color="red"];
    struct2:f1 ->struct1:f3 [color="red"];
}

 test_5

Иcпользование команд консоли

snimok-ekrana-2016-03-09-v-21-55-07

Самый простой вариант создать диаграмму – это запустить в консоли соответсвующую команду (на рисунке показано окно Терминала под Mac OS X), например, dot. Если файл называется test.gv, а на выходе мы хотим получить png, то команда будет такая, как это показано ниже (а также выше на рисунке). Решение универсально и работает в любой операционной системе.

dot -Tpng -O test.gv

Использование RStudio для рисования графов

Следует отметить, что в Mac OS X при установке graphviz такой удобной графической оболочки как в Windows, вы не получите. Если вариант собрать его из исходников из портов (если вы хоть что-то поняли из написанных слов, значит инструкции не нужны), можно использовать консоль, как это показано выше, но также имеется возможноть использовать средства языка R и RStudio. Возможно, что кому-то это будет проще.

Для корректной работы вам понадобится пакет DiagrammeR. Установите его из меню или командой

install.packages("DiagrammeR")

После установки создайте файл, скопируйте туда код, сохраните его с расширением .gv, поставьте галочку “Preview on Save”. Обратите внимание, если вы работаете в Windows, то файл необходимо сохранять в кодировке cp1251, иначе вместо русского языка вы получите кракозябры.

bezymyannyy_3

Дальше, используя кнопку Export, можно сохранить получившуюся диаграмму в формате png или jpeg.

Альтернативные варианты рисования диаграмм

Следует отметить, что DiagrammeR позволяет работать и с диаграммами в формате mermaid. В таком случае, файлы надо сохранять с расширением .mmd. Помимо простых графов, этот формат позволяет описать диаграмму последовательности, как это показано на рисунке ниже.

bezymyannyy_4

Код:

sequenceDiagram
  Покупатель->>Кассир: запрос билетов
  Кассир->>База данных: наличие мест
  alt билеты имеются
    База данных->>Кассир: Имеются
    Кассир->>Покупатель: Подтверждение
    Покупатель->>Кассир: Согласие
    Кассир->>База данных: Бронирование мест
    Кассир->>Принтер: Печать билета
  else билеты проданы
    База данных->>Кассир: Свободных мест нет
    Кассир->>Покупатель: Извините
  end

Диаграмма (обратите внимание, что пропали стрелки и непонятно, как идут сообщения.  Это давно известная ошибка, которую так и не исправили):

rplot_1

К счастью, в формате mermaid можно редактировать online с сохранением результата в формате SVG, где результат будет выглядеть больше похожим на то, что ожидалось.

snimok-ekrana-2016-03-09-v-21-06-13

Дополнительные материалы

  1. Примеры на сайте graphviz. При кликании мышкой по графу показывается его код.
  2. Документация: различные типы узлов
  3. Документация: различные типы стрелок
  4. Документация: цветовая палитра



Опубликовано 09.03.2016 Тушавин В.А. в категории "Используем свободное ПО", "Пишем ВКР