# Руководство &rocs;

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com
Алексей
Субач

    alexey.subach@gmail.com

Перевод на русский
2009
Tomaz Canabrava
2011
Andreas Cord-Landwehr
04.12.2011
1.1 &kde; 4.8
&FDLNotice;

&rocs; — это инструмент KDE для работы с теорией графов.

KDE
kdeedu
математика
граф
графы
вершина
ребро

## Введение

&rocs; — это среда для работы с графами для любого, кто заинтересован в разработке и анализе алгоритмов, основанных на графах. Она подойдет для

- лекторов, которые хотят продемонстрировать алгоритмы своим студентам,

- студентов, которые хотят понять и увидеть как работает какой-либо алгоритм,

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

Для всех этих пользователей &rocs; предоставляет легкий в использовании инструмент для создания и редактирования графов, мощный скриптовой движок Qt Script для выполнения алгоритмов, и несколько вспомогательных инструментов для создания графов и структур данных для любых экспериментов. Так что обычная последовательность действий включает в себя написание алгоритма, создание графа, и наблюдение в реальном времени как алгоритм работает на конкретном примере.

Снимок окна &rocs;.
Снимок окна &rocs;.

## Интерфейс &rocs;

### Общие части интерфейса

Пользовательский интерфейс разделен на несколько логических частей как показано на снимке окна ниже.

Элементы интерфейса &rocs;
Элементы интерфейса &rocs;

Панель инструментов визуального редактора графов

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

Визуальный редактор графов

  Это рабочая панель, где вы можете рисовать графы. Нажмите правой кнопкой на белой поверхности, элементах графа или выбранных элементах графа, и откроется нужное контекстное меню.

Свойства графа

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

Редактор скриптов

  В этом текстовом редакторе вы можете писать алгоритмы на скриптовом языке Qt Script (его синтаксис точно такой же, как JavaScript). Вы можете работать над несколькими алгоритмами одновременно, открывая или создавая вкладки с новыми скриптами в главном меню. Если текущие изменения в скрипте не сохранены, на вкладке появится небольшой значок диска.

Отладочная информация и выходные данные скрипта

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

Выполнение скриптов

  Эта зона контролирует выполнение скриптов. Вы можете выполнить скрипт, который в данный момент открыт в редакторе скриптов на графе, который в текущий момент открыт в визуальном редакторе графов нажатием кнопки Запустить. Во время выполнения скрипта можно его остановить нажатием кнопки Стоп.

### Панели инструментов

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

- Главная панель инструментов

- Панель выравниванияr

#### Главная панель инструментов

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

- Переместить: Чтобы выбрать элементы, кликните на неиспользуемом пространстве, удерживайте левую кнопку мыши нажатой и нарисуйте прямоугольник, который будет содержать нужные узлы и ребра, или просто кликните на невыбранный элемент, чтобы выбрать его. Если вы кликните по уже выбранному элементу или набору выбранных элементов, продолжая удерживать левую кнопку мыши нажатой и двигая курсор вы переместите элементы. Также перемещение выбранных элементов возможно при помощи стрелок на клавиатуре.

- Добавить вершину: Кликните на произвольное место в визуальном редакторе, чтобы создать новый узел, который будет принадлежать текущему графу.

- Добавить ребро: Кликните на один узел, удерживайте левую кнопку мыши нажатой и проведите линию к другому узлу, к которому данное ребро будет вести. Действие произойдет только если добавление данного ребра в текущий граф возможно (например, в неориентированном графе нельзя добавлять несколько ребер между узлами).

- Удалить: Кликните на элемент, чтобы удалить его. Если вы удаляете узел, все смежные ребра будут также удалены.

- Масштаб: Кликните на рабочее пространство, и, удерживая левую кнопку мыши нажатой, нарисуйте прямоугольник. Выбранная область рабочего пространства будет увеличена. Для масштабирования также можно использовать колесико мышки. Двойной щелчок левой кнопкой мыши восстановит масштаб по умолчанию.

Главная панель инструментов.
Главная панель инструментов.

#### Панель выравнивания

Вы можете добавить Панель выравнивания. Нажатие на любую кнопку этой панели незамедлительно воздействует на выбранные узлы:

- Вверх: Выравнивание узлов на вертикальную позицию самого верхнего из выбранных.

- По центру: Центрирование вертикальной позиции выбранных узлов. Вертикальная позиция выбранных узлов усреднится.

- Вниз: Выравнивание узлов на вертикальную позицию самого нижнего из выбранных.

- Влево: Выравнивание узлов на горизонтальную позицию самого левого из выбранных.

- Центр: Центрирование горизонтальной позиции выбранных узлов. Горизонтальная позиция выбранных узлов усреднится.

- Вправо: Выравнивание узлов на горизонтальную позицию самого правого из выбранных.

- По кругу: Выравнивание узлов по кругу, диаметр которого равен максимальному расстоянию среди выбранных узлов. Узлы будут расположены также, как они расположены относительно их центра масс.

- Минимизировать количество пересекающихся рёбер: Применяется алгоритм Fruchterman-Reingold для минимизации числа пересекающихся ребер.

Панель выравнивания.
Панель выравнивания.

### Свойства графа

Слева вы можете настроить каждый открытый граф. Все настройки являются глобальными для каждого графа, а чтобы настроить конкретный узел или конкретное ребро, используйте диалоги Свойства Ребра и Свойства Узла.

- Имя: Имя, по которому ваш алгоритм будет иметь доступ к графу.

- Цвет данных для вновь созданных узлов. Вы можете поменять цвет всех узлов, нажав кнопку Все

- Цвет указателей

Последний ряд настроек состоит из переключаемых кнопок:

- Показывать имена на: Данных или Указателях.

- Показывать значения на: Вершинах или Ребрах.

## Использование &rocs;

Обычно первый шаг — это создать граф с помощью визуального редактора. Вы можете это сделать либо вручную, добавляю новые узлы и соединяя их ребрами, либо используя один из вспомогательных алгоритмов, которые могут быть найдены в Инструменты Генерирование графа. Возможно, вы также захотите использовать Инструменты Сопоставить значения для сопоставления начальных значений узлам и ребрам графа. В конце, вы должны дать графу имя. Имя будет идентификатором, который вы в дальнейшем будете использовать для доступа к графе через скриптовой движок.

### Написание скриптов

&rocs; в качестве скриптового языка использует язык, похожий на JavaScript. Создание переменных и функций и их использование реализованы точно так же, как в JavaScript. Сверх того, &rocs; предоставляет функции, позволяющие вам иметь доступ к открытым графам и их элементам.

#### Доступ к графу

При написании скрипта вы можете обращаться к графу просто введя его имя, и используя его как объект со следующими функциями. Чтобы обратиться к узлу или ребру, вы должны получить их идентификатор от объекта графа

Объекты графа

      // функции
           array list_nodes();
           array list_edges();
           node add_node(name);
           edge add_edge(from, to);
           node node_byname(QString& name);
           node begin_node();
           array end_nodes();

      // переменные
           bool directed
           bool automate
           string name
           string nodeDefaultColor // в шестнадцатеричной системе счисления
           string edgeDefaultColor  // в шестнадцатеричной системе счисления

Объекты узлов

      // функции
           array adj_nodes();
           array adj_edges();
           array input_edges();
           array output_edges();
           array loop_edges();
           array connected_edges(Node *n);
           void self_remove();

      // переменные
          double x
          double y
          double width
          string value
          string name
          string color  // в шестнадцатеричном формате
          bool begin
          bool end

Объекты ребер

      string color ( em hexa )
          string value
          string name
          double width
          string style ( dot, dash, dash dot, solid )

          node start();
          node  end();

          void self_remove();

#### Алгоритмы на графах

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

Вычисление кратчайшего пути

  Находит кратчайший путь между вершинами start и end. Обе вершины должны принадлежать одному графу. Алгоритм работает на ориентированных и неориентированных графах.

      	array dijkstra_shortest_path Node* start Node* end

### Пример

Здесь приведен простой пример скрипта, который задает цвета первых четырех узлов первого графа:

    /* пример скрипта, который задает цвета первых
    четырех узлов первого графа: */

    var colors = new Array("red", "green", "blue", "yellow");

    /* graphs — это массив графов, вы можете обращаться к графу по его индексу
    в массиве или просто по его имени, так что если имя первого графа — Untitled0, следующие
    строки верны  */
    var list1= graphs[0].list_nodes(); //  1-й вариант.
    var list2=Untitled0.list_nodes();              // 2-й вариант

     for ( var i = 0; i < colors.length; i++){
            if (i
    > list2.length) break;
            list2[i].color = colors[i]
     }

### Импорт и экспорт

&rocs; на данный момент поддерживает импорт и экспорт в следующих файловых форматах:

- DOT файлы

- GML файлы

- Текстовые файлы

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

## Авторские права и лицензия

&rocs;

Авторские права:

- © Ugo Sangiori, 2008 (ugorox@gmail.com)

- © Tomaz Canabrava, 2008-2011 (tcanabrava@ kde.org)

- © Wagner Reck, 2008-2011 (wagner.reck@gmail.com)

- © Andreas Cord-Landwehr, 2011 (cordlandwehr@gmail.com)

Авторские права на документацию:

- © Anne-Marie.Mahfouf, 2009 (annma@kde.org)

- © Tomaz Canabrava, 2009 (tcanabrava@ kde.org)

- © Andreas Cord-Landwehr, 2011 (cordlandwehr@gmail.com)

Перевод на русский: Алексей Субачalexey.subach@gmail.com

&underFDL; &underGPL;

## Установка

### Как получить &rocs;

&install.intro.documentation;

### Компиляция и установка

&install.compile.documentation;

&documentation.index;