Достаточно часто встречается задача, когда надо нарисовать нечто, представляющее из себя граф. Это может быть иерархическая сструктура работ проекта, иерархическая структура рисков, организационная структура, топология сети и т.п. Если же количество вершин и ребер достаточно велико, то нарисовать это красиво становится нетривиальной задачей. К счастью, существует программа 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; >
В приложении это будет выглядеть следующим образом:
Как построить матрицу смежности?
В данном случае, был использован параметр по умолчанию и для построения графа использована утилита dot.
Для примера, тот же граф, построенный с помощью:
 |
 |
 |
| circo | fdp | twopi |
Подробнее это описано в документации на сайте. Если кратко, то dot , а далее в статье используется только он, рисует граф в заданном в порядке ветвления; twopi — использует радиальное построение, когда вершины располагаются на концентрических окружностях, circo — связанные вершины располагаются по кругу.
В данном случае, у нас был изображен орграф. Если граф не ориентирован, иными словами «стрелочки» на рисунке нам не важны, то граф описывается следующим образом (обратите внимание на первой слово «graph» вместо «digraph», как задаются связи («—» вместо «->»), а также на команду node [shape = box] — задающую прямоугольники в качестве вершин). Несомненно, формат стрелок можно определить и в самом графе на языке dot, но алгоритмы построения для ориентированных и неориентированных графов имеют небольшое отличие.
graph test
Результат выглядит так:
Gephi создание графа
Пример из заметки по динамическому программированию: меняем ориентацию графа (строится справа налево), добавляем подписи и стили линий и задаем размер листа.
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 ]; >
Более сложные пример приведен в заметке по методу анализа иерархии.
При выборе формата записи результирующего графа, определенный интерес представляет формат svg в поле Output File Type. Формат svg — векторный формат, файлы в этом формате можно редактировать, например, с помощью Inkscape. Также обратите внимание на векторный формат emf, позволяющий внедрять и масштабировать рисунки в Word без потери качества. Для этого сайта был использован растровый формат png.
И последний пример, использование структуры в качестве вершины графа.
digraph structs < node [shape=record, style=»rounded,filled»]; struct1 [label=»Инициация| Планирование| Исполнение| Завершение», fillcolor=yellow]; struct2 [label=» Мониторинг| Контроль»]; 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»]; >
Иcпользование команд консоли
Самый простой вариант создать диаграмму — это запустить в консоли соответсвующую команду (на рисунке показано окно Терминала под 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, иначе вместо русского языка вы получите кракозябры.
Дальше, используя кнопку Export, можно сохранить получившуюся диаграмму в формате png или jpeg.
Альтернативные варианты рисования диаграмм
Следует отметить, что DiagrammeR позволяет работать и с диаграммами в формате mermaid. В таком случае, файлы надо сохранять с расширением .mmd. Помимо простых графов, этот формат позволяет описать диаграмму последовательности, как это показано на рисунке ниже.
sequenceDiagram Покупатель->>Кассир: запрос билетов Кассир->>База данных: наличие мест alt билеты имеются База данных->>Кассир: Имеются Кассир->>Покупатель: Подтверждение Покупатель->>Кассир: Согласие Кассир->>База данных: Бронирование мест Кассир->>Принтер: Печать билета else билеты проданы База данных->>Кассир: Свободных мест нет Кассир->>Покупатель: Извините end
Диаграмма (обратите внимание, что пропали стрелки и непонятно, как идут сообщения. Это давно известная ошибка, которую так и не исправили):
К счастью, в формате mermaid можно редактировать online с сохранением результата в формате SVG, где результат будет выглядеть больше похожим на то, что ожидалось.
Дополнительные материалы
- Примеры на сайте graphviz. При кликании мышкой по графу показывается его код.
- Документация: различные типы узлов
- Документация: различные типы стрелок
- Документация: цветовая палитра
Источник: tushavin.ru
алгоритмы / Методичка построение графа
3. Теперь нужно разместить на форме необходимые для работы с графами компоненты.
Компонент Image(находится на вкладке Additional), компонент StringGrid(тоже на вкладке Additional) и компонент Button(на вкладке Standart). Компонент Image нам нужен для рисования графа, в компоненте StringGrid будет отображаться матрица смежности для нарисованного графа, а кнопку Button приспособим для очистки компонента Image и матрицы смежности.
После добавления этих компонентов на экране должно быть примерно следующее:
4. Теперь приступим непосредственно к программированию
Объявите следующие переменные в качестве глобальных:
TPoint koortoch[50]; //массив точек
int n; //счетчик текущей вершины
int versh=-1; //понадобиться нам для обработки различных ситуаций при нажатии мыши
5. Щелкните один раз мышкой на компоненте Image, а затем слева, на панели Object Inspector перейдите на вкладку Events. Найдите строку OnMouseDown и дважды по ней щелкните.
Сейчас мы будем писать обработчик события “Щелчок мышкой” по компоненту Image.
В появившееся окно вставляем следующий код:
if (Button==0)//если нажата правая кнопка мыши
Image1->Canvas->Pen->Width = 10;//радиус наших шариков
Image1->Canvas->TextOut(X+15,Y,IntToStr(n+1)); //выводится созданный по счету шарик
koortoch[n]=Point(X,Y); //массив точек
n++; //увеличиваем номер вершины
Form1->StringGrid1->ColCount=n+1;//количество столбцов матр. смежности увеличивается
Form1->StringGrid1->RowCount=n+1; //количество строк матр. смежности увеличивается
Image1->Canvas->Pen->Color = clBlue;//устанавливаем цвет вершин
Image1->Canvas->Ellipse(X,Y,X+10,Y+10); //рисуем эллипс
if (Button==1)//если нажата левая кнопка мыши
if (versh==-1)//если пока не запомнили ни одну из вершин
versh=i;//если попали, то запоминаем вершину по которой щелкнули
else //если по одной из вершин уже раннее щелкнули(запомнили), то
toversh=i;//если попал, то соединяем вершины
if ((toversh!=-1)(versh!=toversh))//если щелкнули сначала по одной, а потом по другой вершине
//по номеру вершины узнаем ее конкретные координаты x и y
Image1->Canvas->Pen->Width = 1;//ширина линии , которой соединяем вершины
//рисуем линию между вершинами по которым щелкнули мышкой
//заполняем матрицу смежности:
В результате на экране будет примерно следующее:
6. Один раз щелкните мышкой на форме(либо слева в окне Object TreeView выберите вашу форму). Затем слева, на панели Object Inspector перейдите на вкладку Events. Найдите строку OnActivate и дважды по ней щелкните.
В появившемся окне введите следующий код:
Это необходимо для инициализации компонента Image при активации формы.
7. Теперь напишем обработчик события “Нажатие на кнопку” для кнопки “Очистить”
Дважды щелкните на кнопке, которую ранее мы расположили на форме.
В появившееся окно вставляем следующий код:
StringGrid1->Cells[j][i]=»»; //в цикле очищаем матрицу смежности
n=0;//обнуляем счетчик вершин
В результате на экране будет примерно следующее:
Источник: studfile.net
Реализация Graph на C++ с использованием STL
Учитывая неориентированный или ориентированный граф, реализуйте структуру данных Graph на C++ с использованием STL. Реализуйте как взвешенные, так и невзвешенные графы, используя представление списка смежности Graph.
Условие:
Как мы уже знаем, список смежности связывает каждую вершину Graph с набором соседних вершин или ребер, т. е. каждая вершина хранит список смежных вершин. Существует множество вариантов представления списка смежности в зависимости от реализации.
Например, ниже представлен список смежности приведенного выше Graph:
Приведенное выше представление позволяет хранить дополнительные данные о вершинах, но практически очень эффективно, когда граф содержит только несколько ребер. Мы будем использовать векторный класс STL для реализации представления Graph в виде списка смежности.
Источник: www.techiedelight.com