# Підручник з &rocs;

## Вступ

&rocs; — комплексне середовище розробки для теорії графів, призначене для всіх, хто цікавиться розробкою та аналізом алгоритмів, пов’язаних з графами. Це зокрема

- викладачі, які хочуть продемонструвати роботу алгоритмів, пов’язаних з графами, студентам,

- студенти, які бажають краще зрозуміти теорію і розібратися у роботі алгоритмів,

- всі, чия робота пов’язана з розробкою алгоритмів теорії графів, та всі, кому потрібен інструмент для тестування прототипів.

Для всіх цих користувачів у &rocs; передбачено простий у користуванні редактор графів для створення і внесення змін до графів, потужний рушій обробки скриптів Qt Script для виконання алгоритмів та декілька допоміжних інструментів для налаштування ваших графів та структур даних для експериментів. Отже звичайна процедура роботи з програмою передбачає написання алгоритму, створення графу та перегляд у режимі реального часу обробки алгоритмом графу.

Знімок вікна &rocs;. Знімок вікна &rocs;.

## Інтерфейс користувача &rocs;

### Загальні елементи інтерфейсу користувача

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

Елементи графічного інтерфейсу &rocs;. Елементи графічного інтерфейсу &rocs;.

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

- щоб мати змогу малювати або вносити зміни до графів на панелі візуального редактора графів, вам слід спочатку вибрати інструмент на цій панелі.

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

- Це ділянка вікна програми, у якій ви можете малювати ваші графи. Клацання правою кнопкою миші на панелі малювання, частинах графу або позначених елементах графу відкриє контекстне меню, вміст якого залежатиме від об’єкта.

Властивості графу

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

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

- У полі цього текстового редактора ви можете створювати скрипти алгоритмів мовою Qt Script (у нашому випадку це просто діалект JavaScript). Ви можете працювати одночасно над декількома алгоритмами: для цього достатньо відкрити або створити декілька вкладок скриптів за допомогою головного меню програми. Якщо зміни, внесені на якійсь із вкладок це не збережено, програма показуватиме невеличкий символ диска на заголовку цієї вкладки.

Панель діагностичних повідомлень та виведення даних

- До цього поля програма виводитиме діагностичні повідомлення або дані, виведені скриптом, залежно від вибору параметра виведення даних. Якщо під час виконання скрипту станеться помилка, програма негайно перемкнеться у режим діагностичних повідомлень. Крім того, серед діагностичних повідомлень будуть і всі повідомлення, виведені скриптом під час виконання.

Виконання скриптів

- За допомогою цього меню можна керувати виконанням алгоритмів. Ви можете виконати скрипт, створений у редакторів скриптів, для графу, відкритого на панелі візуального редактора графів, натисканням кнопки Пуск. Якщо виконання скрипту ще не завершено, його можна зупинити натисканням кнопки Стоп.

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

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

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

- Панель інструментів вирівнювання

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

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

- Пересунути: щоб позначити елементи, натисніть ліву кнопку миші на порожньому місці на графі, утримуйте кнопку натисненою і рухом вказівника миші створіть прямокутник, у якому міститимуться всі вузли і/або ребра. Якщо треба позначити окремий елемент, просто клацніть лівою кнопкою миші на цьому елементі. Якщо ви наведете вказівник миші на позначений елемент або набір елементів, натиснете і утримуватимете натисненою ліву кнопку миші, а потім почнете рухати вказівник, разом з ним почнуть рухатися позначені елементи. Пересунути позначені елементи можна також за допомогою клавіш зі стрілочками.

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

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

- Вилучити: клацніть на елементі графу, щоб його вилучити. Якщо ви вилучите вузол, всі ребра, які з ним з’єднано, також буде вилучено.

- Масштаб: наведіть вказівник на панель візуального редактора, натисніть і утримуйте натисненою ліву кнопку миші, перетягніть вказівник так, щоб у отриманому прямокутнику містилися всі потрібні вам елементи, відпустіть кнопку миші. Панель візуального редактора буде масштабовано відповідно до вказаного вами прямокутника. Збільшити або зменшити масштаб можна за допомогою прокручування коліщатка миші. Подвійне клацання лівою кнопкою миші відновлює початковий масштаб.

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

#### Панель інструментів вирівнювання

Крім того, ви можете додати відкрити додаткову панель вирівнювання. Натискання кнопки дії на цій панелі призведе до негайного виконання дії над поточними позначеними вузлами.

- Вгору: вирівняти вузли за вертикальною позицією найвищого з них. Змінено буде лише вертикальні координати.

- Центр: вирівняти вузли на вертикальною позицією середнього значення вертикальних координат всіх позначених вузлів. Змінено буде лише вертикальні координати.

- Основа: вирівняти вузли за вертикальною позицією найнижчого з них. Змінено буде лише вертикальні координати.

- Ліворуч: вирівняти вузли на горизонтальною позицією найлівішого вузла. Змінено буде лише горизонтальні координати.

- Центр: вирівняти вузли на горизонтальною позицією найвищого вузла. Змінено буде лише горизонтальні координати.

- Праворуч: вирівняти вузли на горизонтальною позицією найправішого вузла. Змінено буде лише горизонтальні координати.

- Коло: розташувати вузли на колі з діаметром, рівним максимальній відстані між вузлами. Вузли на колі буде розташовано у такому самому порядку, у якому їх видно з центра мас вузлів.

- Мінімізувати кількість перетинів ребер: застосувати алгоритм Фругтермана-Рейнґольда для мінімізації (наближено) кількості ребер, що перетинаються.

Панель інструментів вирівнювання. Панель інструментів вирівнювання.

### Властивості графу

На лівій бічній панелі буде наведено параметри кожного з відкритих графів. Всі ці параметри є загальними для окремого графу, їх можна змінити для окремих вузлів та ребер за допомогою діалогових вікон «Властивості вузла» та «Властивості ребра».

- Назва: назва, яку має використовувати ваш алгоритм для доступу до графу.

- Колір даних для нових вузлів. Змінити колір вузлів для всіх поточних вузлів можна натисканням кнопки Всі.

- Колір вказівника

У останньому рядку параметрів буде наведено кнопки перемикання:

- Показувати назви у: Даних або Вказівниках.

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

## Користування &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 // у HEXA
           string edgeDefaultColor  // у HEXA

Об’єкти вузлів

-     // функції
           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  // у HEXA
          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();

#### Алгоритми графів

Іноді для виконання типових завдань, наприклад обчислення найкоротшого маршруту між двома вузлами, варто скористатися функцією. У поточній версії програми передбачено можливість виклику з рушія обробки скриптів вказаних нижче алгоритмів для вузлів одного графу.

Обчислення найкоротшого маршруту

- Обчислює найкоротший шлях між вузлами початок і кінець. Обидва вузли мають належати одному графу. Під час обчислення враховується те, чи є граф зорієнтованим.

      	array dijkstra_shortest_path Node* початок Node* кінець

### Приклад

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

    /* Простий приклад, який встановлює кольори перших чотирьох вузлів першого
    графу: */

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

    /* graphs — це масив графів, доступ до окремого графу можна отримувати за його індексом
    у масиві або за його назвою, отже, якщо назвою першого графу є Untitled0, можна скористатися
    такими командами  */
    var list1= graphs[0].list_nodes(); //  перша форма.
    var list2=Untitled0.list_nodes();              // друга форма

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

### Імпортування та експортування

У поточній версії &rocs; передбачено підтримку імпортування та експортування даних файлів у таких форматах:

- файли DOT, також відомі як файли Graphviz;

- файли GML;

- звичайні текстові файли.

У поточній версії з більшості цих файлів імпортується лише декілька значень. Серед імпортованих значень дані вузлів та відповідних з’єднань, назви всіх елементів, значення та, якщо їх вказано, координати.

## Подяки і ліцензія

&rocs;

Авторські права на програму:

- Авторські права на програму належать Ugo Sangiori (ugorox AT gmail.com), 2008

- Авторські права на програму належать Tomaz Canabrava (tcanabrava AT kde.org), 2008–2011

- Авторські права на програму належать Wagner Reck (wagner.reck AT gmail.com), 2008–2011

- Авторські права на програму належать Andreas Cord-Landwehr (cordlandwehr AT googlemail.com), 2011

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

- Авторські права на документацію належать &Anne-Marie.Mahfouf; &Anne-Marie.Mahfouf.mail;, 2009

- Авторські права на документацію належать Tomaz Canabrava tcanabrava at kde dot org, 2009

- Авторські права на документацію належать Andreas Cord-Landwehr (cordlandwehr AT googlemail.com), 2011

Переклад українською: Юрій Чорноіван yurchor@ukr.net

&underFDL; &underGPL;

## Встановлення

### Як отримати &rocs;

&install.intro.documentation;

### Збирання і встановлення

&install.compile.documentation;
&documentation.index;