В 2021 году мы разработали и добавили на сайт редактор графов. Вряд ли найдутся те, кто не знает, что такое граф. Однако на всякий случай напомним, что граф — это графическое представление набора объектов, где некоторые пары объектов соединены связями. Взаимосвязанные объекты представлены точками, называемыми вершинами, а связи, соединяющие вершины, называются рёбрами. Строго формально граф — это пара множеств (V, E)
, где V
— множество вершин, а E
— множество ребер, соединяющих пары вершин.
Графы находят своё применение во многих сферах — электротехнике (для проектирования схем и топологий), информатике (для изучения алгоритмов вроде алгоритма Дейкстры или построения минимального остовного дерева), компьютерных сетях (для нахождения оптимального расположения маршрутизаторов или вычисления максимальной пропускной способности), науке (исследования химических веществ и биологических организмов), играх (составление дерева ветвления сюжета), книгах (взаимосвязи между героями) и многих других областях.
Интерфейс редактора
При открытии редактора, пользователю отображается меню и поле для построения графа. Поле имеет сетку (при желании её можно отключить с помощью сочетания клавиш Ctrl+G
), для более удобного выравнивания вершин. Меню (можно свернуть с помощью сочетания Ctrl+M
) позволяет добавлять элементы графа (вершины, рёбра, текстовые поля) на поле, выполнять загрузку и сохранение графа в различных форматах, отображать различные представления графа, а также запускать различные алгоритмы с пошаговым выполнением. В нижней части меню отображается основная информации о текущем графе — количестве вершин, рёбер и текущем масштабе.
В правом нижнем углу поля находятся кнопки поиска ближайшей вершины, отмены/повтора действий, изменения масштаба и переключения видимости сетки. В правом верхнем углу доступна кнопка для отображения информации об основных горячих клавишах, используемых в редакторе. Также в этой же части отображаются кнопки для изменения или удаления элементов графа при наличии выбранного элемента.
Редактор хранит историю всех выполненных действий, так что в случае ошибки можно отменить последние действия с помощью сочетания клавиш Ctrl+Z
. Чтобы повторить отменённое действие, достаточно нажать сочетание Ctrl+Y
.
Построение и изменение графа
Добавление вершин
Добавить вершину можно несколькими способами:
- выбрать вершину в меню и, зажав кнопку мыши, перетащить её в нужное место (если просто кликнуть по пункту меню, вершина добавится рядом с меню)
- дважды кликнуть по рабочей области, вершина появится в месте клика
- использовать быстрое создание вершины с ребром (подробнее в разделе добавления ребра)
Также вершину можно скопировать и вставить с помощью сочетаний клавиш Ctrl+C
и Ctrl+V
соответственно.
Добавление рёбер
В теории графов различают неориентированные рёбра и ориентированные рёбра, называемые дугами. Также рёбра могут быть взвешенными или не иметь веса (в таком случае обычно неявно предполагается, что вес ребра равен единице). Для добавления ребра в редакторе доступны следующие варианты:
- через меню: выбрать пункт "Добавить ребро" или "Добавить дугу", после чего кликнуть по вершинам, между которыми необходимо разместить ребро.
- через горячие клавиши: выделив начальную вершину и зажимая клавиши
Shift
для ребра илиAlt
для дуги, нажать на конечную вершину. Если при этом также зажать клавишуCtrl
, то добавится взвешенное ребро единичного веса. Если вместо второй вершины кликнуть по пустому месту, в него добавится новая вершина и создастся ребро между начальной вершиной и добавленной.
Редактирования вершин и рёбер
Для перехода в режим редактирования вершины достаточно дважды кликнуть по ней или нажать клавишу F2
при наличии выделенной вершины. Для редактирования вершины доступны следующие параметры:
- название — по умолчанию все вершины создаются в виде числовых вершин, однако название может состоять из любых символов.
- размер — радиус вершины изменяется в довольно широких пределах.
- стиль — для изменения доступны цвет фона, текста и контура вершины. Доступны 28 цветов на выбор, включая прозрачный.
Аналогично вершине, для редактирования ребра на него также можно дважды кликнуть или использовать клавишу F2
, после чего можно будет ввести вес ребра. В качестве веса допускаются только числовые значения (в том числе вещественные и отрицательные) или пустое значение для невзвешенного ребра. Для изменения дуги ребра достаточно нажать на ребро и, удерживая кнопку мыши, перемещать курсор в нужную сторону.
Сохранение графа
Редактор позволяет сохранить граф в одном из следующих форматов:
.graph
— собственный формат редактора, по своей природе являющийся JSON'ом.png
— растровое изображения, качество напрямую зависит от текущего масштаба редактора..svg
— векторное изображение.dot
— распространённый текстовый формат, наиболее известный благодаря редактору graphviz.tgf
— самый простой текстовый формат.graphml
— основанный на XML формат хранения графов
Для сохранения графа в нужном формате нужно выбрать в меню пункт "Скачать граф", а затем в появившемся подменю кликнуть по интересующему формату. В дальнейшем планируется расширение списка доступных для сохранения форматов.
Загрузка графа
Редактор поддерживает три способа загрузки графа — из файла, из имеющегося набора примеров и генерация случайного графа.
Загрузка из файла
В настоящий момент доступны два формата файлов для загрузки: собственный формат .graph
и формат списка рёбер .edges
. Синтаксис формата .edges
довольно прост: это текстовый файл, каждая строка которого описывает ребро в следующем виде: v1 direction v2 weight
v1
иv2
— имена вершин, соединённых ребром. Если вершина содержит пробелы, то название должно браться в кавычки.direction
— указывает наличие направления ребра. Неориентированные рёбра обозначаются как--
, а ориентированные как->
weight
— необязательный параметр, обозначает вес ребра. Аналогично редактору, значение должно быть числовым.
Загрузка из примера
В редакторе доступны 17 примеров различных графов — неориентированный, несвязный, дерево, полный, двудольный и т.д.
Генерация случайного графа
При выборе создания случайного графа редактор создаст новый граф по следующему алгоритму:
- Случайным образом выбирается количество вершин из диапазона [3, 25]
- Случайным образом равновероятно определяется ориентированность и взвешенность графа
- Случайным образом выбирается количество рёбер
- Для каждого ребра выбираются две доступные вершины и соединяются ребром или дугой в зависимости от ориентированности
Представления графа. Матрицы смежности и инцидентности, список рёбер, список смежности
Для хранения графов используются различные структуры - матрицы смежности, инцидентности, списки рёбер или списки инцидентности. Поскольку не существует наиболее удобного способа представления произвольного графа, то и редактор предоставляет возможность использовать все возможные представления.
Редактирование и создание из представления
Все представления графа (за исключением списка смежности пока) позволяют изменять структуру графа — удалять и добавлять вершины, удалять и добавлять рёбра, а также изменять их вес. Аналогичным образом можно создать граф по заданному представлению с нуля.
Алгоритмы на графах
Для наглядности и более лёгкого изучения теории графов редактор предоставляет возможность запускать на созданных графах различные алгоритмы, результат работы которых можно смотреть в том числе пошагово. В настоящий момент редактор поддерживает следующие алгоритмы:
- Алгоритмы обхода графа
- Поиск путей
- алгоритм Дейкстры (кратчайший путь от одной вершины до всех остальных)
- алгоритм Беллмана-Форда (кратчайший путь от одной вершины до всех остальных, допускает рёбра отрицательного веса)
- алгоритм Флойда-Уоршелла (кратчайшие пути между всеми парами вершин)
- поиск всех возможный путей между парой вершин
- Размещение графа (перемещение вершин для придания более эстетического вида)
- силовой алгоритм Фрюхтермана-Рейнгольда
- энергетический алгоритм Камада-Кавай
- Построение минимального остовного дерева
- Связность
- Нахождение максимального потока
- Прочее
- Эйлеров путь
- Эйлеров цикл
- Гамильтонов цикл
- поиск любого цикла
- разбиение на две доли
- проверка двух графов на изоморфизм
- центр, радиус и диаметр
- топологическая сортировка
- раскраска
- расчёт степеней вершин
Анимацию алгоритмов можно сохранить целиком в виде анимированного .gif
изображения либо сохранить выбранный кадр анимации в виде png изображения. Для некоторых алгоритмов можно сохранить результирующий граф в виде .graph
файла. Во время работы анимации работа с графом в области просмотра блокируется, доступными остаются только действия изменения масштаба и перемещения по полю. Чтобы закрыть анимацию достаточно нажать на иконку в правом верхнем углу или на клавишу Esc
.
Прочие действия
Масштабирование и перемещение
Для того, чтобы перемещаться вверх и вниз используется обычная прокрутка мыши. Для горизонтального перемещения также используется прокрутку мыши, но с зажатой клавишей Shift
. Также можно перемещаться, зажав Ctrl
и левую кнопку мыши или с помощью стрелок без выделенных элементов.
Для изменения текущего масштаба используется прокрутка колеса мыши с зажатой клавишей Alt
. Также масштабирование возможно с использованием сочетаний клавиш Ctrl+Plus
и Ctrl+Minus
или иконок лупы в правой нижней части экрана для увеличения и уменьшения масштаба соответственно.
Переключение между вершинами и поиск ближайшей вершины
Чтобы сделать активной очередную вершину и переместить поле так, чтобы она оказалась в центре, достаточно нажать клавишу Tab
. А для того чтобы перейти на предыдущую вершину, достаточно нажать сочетание клавиш Ctrl+Tab
. Для перемещения поля таким образом, чтобы в центре оказалась ближайшая вершина, нужно нажать сочетание клавиш Ctrl+F
.
Выделение и действия с ним
Для создания выделения достаточно в пустом месте зажать левую кнопку мыши и перемещать её до выделения нужной области. Если требуется выделить весь граф целиком, то лучше использовать сочетание клавиш Ctrl+A
Чтобы переместить выделение, аналогично перемещению элементов, необходимо зажать левую кнопку мыши внутри выделения и перемещать мышь. Также для перемещения можно использовать стрелки клавиатуры.
Чтобы скопировать выделение, используется сочетание клавиш Ctrl+C
. Для вставки скопированного выделения нужно нажать Ctrl+V
. Удалить выделение можно с помощью нажатия клавиши Delete
или специальной иконки в правом верхнем углу.
Список всех горячих клавиш
Некоторые сочетания клавиш уже описаны выше в тексте инструкции. Основные горячие клавиши доступны прямо в редакторе, для открытия списка достаточно щёлкнуть по иконке клавиатуры в правом верхнем углу экрана. Ниже приводим список всех доступных сочетаний:
Общие действия
Ctrl + Z
— отменить прошлое действиеCtrl + Y
— повторить отменённое действиеCtrl + G
— скрыть / показать сеткуCtrl + M
— скрыть / показать менюCtrl + A
— выделить все элементы графаCtrl + F
— найти ближайшую вершину и поместить в центрCtrl + P
— разместить граф с помощью силового лагоритмаEsc
— завершить или отменить начатое действиеShift + клик
— добавить невзвешенное неориентированное реброAlt + клик
— добавить невзвешенное ориентированное ребро (дугу)Ctrl + Shift + клик
— добавить взвешенное неориентированное реброCtrl + Alt + клик
— добавить взвешенное ориентированное ребро (дугу)Tab
— сделать следующую вершину активнойShift + Tab
— сделать предыдущую вершину активнойCtrl + E
— открыть примеры графов
Действия с активным объектом
Ctrl + C
— скопировать активный объект (вершину, текст или выделение)Ctrl + X
— вырезать активный объектCtrl + V
— вставить скопированный объектDel
— удалить активный объектF2
илидвойной клик
— редактировать активный объектPlus
— увеличить размер вершины / дуги ребра / размера текстаMinus
— уменьшить размер вершины / дуги ребра / размера текстаD
— сделать ребро дугой и наоборотR
— изменить направление дуги
Сохранение и загрузка графа
Ctrl + O
— загрузить граф из .graph файлаCtrl + S
— сохранить граф в .graph файлCtrl + Shift + S
— сохранить граф в .png файлCtrl + Alt + S
— сохранить граф в .svg файлCtrl + Shift + Alt + S
— сохранить граф в .dot файл
Масштабирование и перемещение области просмотра
Ctrl + Minus
— уменьшить масштабCtrl + Plus
— увеличить масштабAlt + скролл
— измененить масштабирскролл
— переместить область просмотра вертикальноShift + скролл
— переместить область просмотра горизонтальнострелки
— переместить область просмотра
Отображение представления графа
Alt + M
— открыть матрицу смежностиAlt + E
— открыть список рёберAlt + I
— открыть матрицу инцидентностиAlt + L
— открыть список смежности