Редактор графов на основе пакета Сytoscape

Многие практические задачи естественным образом сводятся к понятию “граф”. Поэтому актуальной является реализация удобных средств построения изображения графов. В статье описывается один из возможных способов решения этой проблемы в виде реализации веб-сервиса, основанного на одном из пакетов с открытым программным кодом.

Введение

Теория графов является одной из самых востребованных для практического применения областей дискретной математики [1].

Важно различать понятия «граф» и «изображение графа».

Граф - это математический объект, состоящий из двух множеств: множество вершин и множество дуг или ребер, соединяющих вершины. Различают графы ориентированные и неориентированные, нагруженные и ненагруженные. Можно упомянуть и многие другие термины. Подчеркнем, что именно изображение графа позволяет многое воспринимать наглядно, и поэтому важно в процессе обучения.

Таким образом, задача создания (или нахождения) удобного инструмента для построения изображения графов различных типов является актуальной.

Безусловно существует немало инструментов, которые предназначены для решения подобных задач. Проблема, обычно состоит либо в сложности их «освоения», либо в их немалой стоимости.

В этой статье описывается программа, позволяющая создавать изображения графов, использующая пакет Сytoscape [2].

Описание программы

В редакторе предусмотрены 3 режима:

1.    добавления (удаления) вершин графа;

2.     рисования ребер (дуг);

3.     выделения элементов графа с цель их последующего перемещения и/или переименования.

В первом режиме (см. рис.1) нажатие левой кнопки мыши приводит к рисованию на месте клика вершины (элемента множества V).

Рис. 1. Режим добавления вершин в граф.

Второй режим позволяет соединить вершины дугами или ребрами (см. рис.2). Для этого необходимо на исходной вершине нажать правую кнопку мыши и довести указатель мыши до конечной вершины. При реализации этой возможности был использован “трюк”, заключающийся в том, что исходная вершина при первом клике программно дублировалась, за счет чего обеспечивался эффект “Drag-and-drop” (перетаскивания вершины). При отжатииклавиши мыши вершины, являющиеся началом и концом дуги опять меняются местами, т.е. приходят в исходное положение

Рис. 2. Режим рисования ребер (дуг) графа.

Редактор позволяет изменить метки (названия) вершин и (или) ребер (дуг) на рис.3 представлен пример, где дуге, связывающей вершины v1 и v2 вместо метки, выставляемой по умолчанию (“v1->v2”) поставлена метка 100.

Рис. 3. Режим выделения элементов графа, позволяющий их переименование.

Кроме перечисленных трех режимов в редакторе предусмотрены элементы управления, реализованные в виде кнопок, расположенных выше поля для рисования и справа от него (рис. 4).

Рис. 4. Элементы графического интерфейса.

Кнопки, расположенные по горизонтали осуществляют следующие действия:

1.    Увеличение и уменьшение площади рисунка по горизонтальному направлению;

2.     Запоминание текущего изображения графа (максимум 15 изображений);

3.     Переключение между состояниями;

4.     Выбор вида графа (ориентированный или неориентированный граф);

5.     Указание на то, является ли граф размеченным или нет;

6.     Создание картинки и возможность сохранения ее в формате PNG.

Кнопки расположенные по вертикали осуществляют следующие действия:

7. Увеличение и уменьшение площади рисунка по вертикальному направлению;

8. Увеличение и уменьшение масштаба изображения;

9. Вывод на экран матрицы смежности, которая также является элементом управления. Функциональность этой кнопки проиллюстрирована на рис. 5. При нажатии на неё справа от поля рисования появляется матрица смежности. Нажав на соответствующую позицию матрицы смежности, возможно добавление или удаление соответствующего ребра или дуги. Таким образом рисование дуг графа можно осуществлять двумя способами: перетягиванием указателя мыши от вершины к вершине, либо, модификацией матрицы смежности путем нажатия на определенный ее элемент.

Рис. 5. Построение графа по матрице смежности.

Кнопка “картинка”, обозначенная на рис. 4 номером 6, предназначена для обеспечения основной функции программы, при ее нажатии справа появляется картинка, которую можно сохранить (см. рис. 6).

Рис. 6. Режим построения картинки.

Заключение

В дальнейшем планируется включить описанный сервис в качестве дополнения гу- гл-таблицы и реализовать сохранение сформированных изображений не только в виде файла на диске компьютера, но и в виде текстовой строки в формате, предусмотренным пакетом cytoscape. Это позволит хранить значительный объем информации (изображений графов) в легко воспроизводимом виде и включить его в пакет, описанный в [3].

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