В 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— открыть список смежности
