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

Tomaz
Canabrava
tomaz.canabrava@gmail.com
Andreas
Cord-Landwehr
cordlandwehr@googlemail.com
Юрій
Чорноіван

    yurchor@ukr.net

Переклад українською
2009
Tomaz Canabrava
2011-2012
Andreas Cord-Landwehr
2 грудня 2012 року
1.8.0 &kde; 4.10
&FDLNotice;

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

KDE
kdeedu
математика
математика
графи
вузол
ребро

## Вступ

У цьому розділі наведено короткий огляд основних можливостей та прийомів роботи у &rocs;. Користувачам, які хочуть негайно перейти до навчання принципам роботи у &rocs;, ми пропонуємо перейти до читання розділу , користуючись настановами розділу щодо написання алгоритмів.

### Мета, цільова аудиторія програми та процес роботи з нею

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

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

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

- та всі, хто цікавиться структурами даних та алгоритмами.

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

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

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

### Ядро &rocs;

У цьому розділі наведено стислий огляд основних елементів &rocs;. Надано пояснення щодо важливих понять структур даних, модулів структур та типів елементів. Ці знання є корисними для покращення розуміння принципів створення структур даних та внесення до них змін у &rocs;.

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

#### Модулі документів графів та структур даних

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

Документи графів є основою визначення типів вказівників та даних.

#### Структури даних

Структури даних є основою всіх дій, які може виконувати &rocs;. Ви можете додати одну або декілька структур до документа графу, додати елементи даних (вузли, значення) та вказівники до структури. Також можна вносити зміни до структур даних за допомогою скриптів. Доступ до структур даних зі скриптів здійснюється за допомогою унікальної назви структури даних. Вибір поточного модуля обробки структури даних дещо обмежує можливість внесення змін до структур даних (наприклад, у дереві не може міститися циклів). Модуль обробки структури даних визначається на рівні документа, який містить відповідну структуру даних.

#### Типи вказівників

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

#### Типи даних

У декількох задачах обробки структур даних набір елементів даних має бути поділено на групи різних типів (наприклад, у задачах з кластеризації та покриття). Типи можуть бути корисними для виконання алгоритмів, у яких для визначення певного типу використовується тип елемента структури даних (наприклад, у алгоритмі пошуку у ширину). Якщо вам потрібно саме це, скористайтеся визначенням типів даних. Кожному типу даних відповідає власна піктограма. Доступ до певних типів даних можна зовсім просто здійснювати зі скриптів.

#### Динамічні властивості

Кожен елемент даних і кожен вказівник можуть мати довільну кількість властивостей. Деякі з цих властивостей є типовим і визначаються модулем структур даних. Докладніше про ці властивості можна дізнатися з документації до модуля структур даних. Додаткові властивості до елементів даних і вказівників можна додати за допомогою динамічних властивостей. Кожна динамічна властивість визначається назвою і може містити пов’язане з нею значення. Назва має починатися з літери латинки (a-z або A-Z) і може складатися лише з літер, цифр і символів «_». Якщо ви спробуєте використати у назві властивості некоректний символ, властивість не буде додано.

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

Крім того, ви можете використовувати скрипти. Вам достатньо скористатися кодом `add_property` з назвою і значенням потрібної вам властивості. Після цього ви зможете скористатися node/pointer.назваВластивості для встановлення або отримання її значень.

Нижче наведено приклад використання динамічних властивостей за допомогою модуля структури даних «Граф».

    nodes = myGraph.list_nodes()
    for (var i = 0; i < nodes.length; ++i ){
        nodes[i].add_property("MyProperty", 0)
    }
    nodes[0].MyProperty = 2
    nodes[1].MyProperty = nodes[0].MyProperty + 2

### Покрокові настанови

У цьому розділі наведено опис прикладу проекту з метою ознайомлення з деякими найважливішими функціональними можливостями &rocs;. Метою є створення графу і скрипту, за допомогою яких може бути проілюстровано простий алгоритм «наближеного» розв’язання для задачі мінімального вершинного покриття. Задача мінімального вершинного покриття полягає у відшуканні підмножини вузлів графу, C, мінімального розміру, такої, що кожне ребро графу з’єднано принаймні з одним вузлом у C. Відомо, що ця задача є NP-повною. Ми намагатимемося проілюструвати спосіб відшукання наближення, кількість вузлів у якому не буде перевищувати подвоєну кількість вузлів у мінімальному покритті, за допомогою пошуку відповідностей у вказаному графі (надалі використовуватимемо загальні терміни алгоритмів для графів: граф називатимемо структурою даних, вузли — елементами даних, ребра — вказівниками).

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

#### Створення графу

У модулі структури даних &rocs; передбачено допоміжний інструмент для створення графів. Викликати його можна за допомогою пункту меню Документ графу Інструменти Створення графу. Створимо «Випадковий граф» з 30 вузлами, 90 ребрами та породжувачем 1 (породжувач впливає на послідовність псевдовипадкових чисел, на основі якої створюється граф; використання одного породжувача декілька разів призведе до повторного створення тих самих графів). Крім того, внесемо зміни до назви графу за допомогою панелі структури даних: назвемо граф `testgraph`.

#### Створення типів

Скористаємося кнопкою Властивості документа на панелі структури даних для відкриття діалогового вікна властивостей для типів даних і вказівників поточного документа графу. Додамо новий тип даних з назвою «C». Цей тип даних автоматично отримає ідентифікатор `1`. Виберемо для цього типу даних піктограму із зображенням сервера. Далі, перемкнемося на сторінку типів вказівників і додамо новий тип вказівника з назвою «matching» (відповідність). Цей тип автоматично отримає ідентифікатор `1`. Визначимо для нього синій колір.

#### Алгоритм

Нарешті, нам слід реалізувати алгоритм апроксимації. Для цього ми скористаємося таким кодом:

    var E = testgraph.list_edges(); // набір необроблених ребер
    var C = new Array();            // відповідні ребра
    while (E.length
    > 0) {
        var e = E[0];        // беремо перше ребро e={u,v}
        var u = e.start();
        var v = e.end();
        e.set_type(1);        // зробити ребро відповідним ребром
        E.shift();            // вилучити e (тобто E[0]) зі списку ребер
        C.push(u);            // додати u до C
        C.push(v);            // додати v до C

        // позначити u,v як вузли у C
        u.set_type(1);
        v.set_type(1);

        // вилучити з E всі ребра з кінцями в u або v
        var adjacent = u.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // визначити індекс
            if (index!=-1) {
                E.splice(index, 1); // вилучити його, якщо знайдено
            }
        }
        var adjacent = v.adj_edges();
        for (var i=0; i < adjacent.length; i++) {
            var index = E.indexOf(adjacent[i]); // визначити індекс
            if (index!=-1) {
                E.splice(index, 1); // вилучити його, якщо знайдено
            }
        }
    }
    output("Vertex Cover contains " + C.length + " nodes.");

#### Виконання алгоритму

Нарешті, алгоритм слід виконати. Для цього ми розпочнемо його виконання натисканням кнопки Виконати на панелі керування скриптами.

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

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

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

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

Вибір документа

  За допомогою розташованої у верхній частині вікна панелі меню ви можете вибрати поточний документ і структуру даних. Також за її допомогою можна створювати і вилучати структури даних та отримувати доступ до властивостей структур даних.

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

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

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

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

Бічна панель

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

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

  - Журнал: у кожного з проектів є власний журнал, яким можна скористатися, наприклад, для занотовування завдань, результатів та спостережень.

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

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

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

Виведене скриптом

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

Керування

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

### Робота з документами графів

Проект &rocs; складається з одного або декількох документів графів, які можна редагувати за допомогою візуального редактора графів. Далі, кожен документ може складатися з довільної кількості структур даних. Для всіх структур даних певного документа використовується один модуль обробки структур даних. За допомогою цього розділу документації ви зможете довідатися, як перемикатися між документами та як створювати нові документи.

#### Панель вибору документа

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

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

- Вилучити: за допомогою цієї дії можна вилучити структуру даних, яку позначено панелі структур даних поточного документа.

- Властивості структури даних: відкрити діалогове вікно доступу до властивостей структури даних.

- Властивості документа: відкрити діалогове вікно доступу до властивостей документа та переліку типів даних та вказівників документа.

Головна панель інструментів.
Панель вибору документа.

#### Створення та імпортування документів графів

Щоб створити новий документ графу або додати вже створений документ до проекту, скористайтеся пунктами меню Проект Створити документ графу та Проект Імпортувати граф &rocs;. Крім того, ви можете імпортувати документи графів зі сторонніх програм (докладніше про це можна дізнатися з розділу ).

## Написання та виконання алгоритмів у &rocs;

У &rocs; використовується рушій обробки скриптів QtScript, який працює з одним з діалектів JavaScript. Це означає, що всі алгоритми, які ви створюватимете, має бути написано мовою JavaScript. У цьому підручнику немає опису принципів роботи та способів написання скриптів JavaScript, хоча тут ви знайдете опис способів доступу до структур даних, елементів даних та вказівників ваших структур даних за допомогою рушія обробки скриптів. Оскільки ви не використовуватимете об’єкт основної структури даних напряму, працюючи з об’єктом, що надається поточним використаним модулем структури даних, функціональні можливості структури даних розширюються відповідним модулем, отже вам слід ознайомитися з відповідними функціональними можливостями. Зокрема, у модулях структур даних використовуються загальні терміни теорії (вузли (nodes) та ребра (edges) у графах, листя (leafs) і корені (roots) у деревах тощо).

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

### Елементи основної структури даних

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

#### Властивості основної структури даних

Структури даних ідентифікуються за назвами. Припустимо, вами створено структуру даних з назвою `testgraph`, тоді ви зможете отримати доступ до структури даних за її ідентифікатором. Наприклад, щоб отримати масив з усіма елементами даних у вказаній структурі даних, ви можете вписати до вашого скрипту інструкцію `testgraph.list_nodes();`.

##### Властивості і функції основної структури даних

Кожна структура даних `testgraph` має такі властивості, які можна читати або записувати за допомогою `testgraph.властивість`:

    string name  // ідентифікація структури даних

#### Властивості та функції основного елемента даних

Кожен з елементів даних має такі властивості, які можна прочитати або записати

    double x      // координата поточної позиції за x
    double y      // координата поточної позиції за y
    double width  // розмір
    string value  // значення
    int id        // унікальний ідентифікатор для елемента даних
    string name   // назва
    string color  // колір у HEXA

Крім того, доступ до всіх динамічних властивостей елемента даних можна отримати за їхніми назвами.

Для кожного об’єкта елемента даних передбачено такі методи:

    int type();                         // тип даних елемента даних
    int set_type(int);                  // встановлення типу даних елемента даних
    void add_property(string name, string value);      // додати динамічну властивість із вказаною назвою і значенням до елемента даних
    array adj_data();                   // список сусідніх даних
    array adj_pointers();               // список сусідніх вказівників
    array input_pointers();             // список вхідних вказівників
    array output_pointers();            // список вихідних вказівників
    array loop_pointers();              // список вказівників, що є замкненими циклами
    array connected_pointers(target);   // список вказівників, що вказують на «target»
    void remove();                      // вилучення цього елемента даних

#### Властивості та функції основного вказівника

Кожен з вказівників має такі властивості, які можна прочитати або записати

    string color  // колір у HEXA
    string value  // значення
    string name   // назва
    double width  // ширина
    string style  // значення з набору: dot, dash, dash dot, solid

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

Для кожного об’єкта вказівника передбачено такі методи:

    int type();                         // тип вказівника
    int set_type(int);                  // встановлення типу вказівника
    void add_property(string name,      // додати динамічну властивість із вказаною назвою та значенням до елемента даних
    node start();                       // початковий вузол вказівника
    node end();                         // вузол призначення вказівника
    void remove();                      // вилучення цього вказівника

### Модуль графів

#### Властивості і функції графу

##### Властивості графу, специфічні для модуля

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

- Граф: граф, у якому передбачено будь-які два вузли може бути з’єднано лише одним ребром.

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

##### Структура графу

Якщо вказано об’єкт структури даних типу «граф», ви зможете викликати такі функції роботи з елементами:

    array list_nodes();                   // список всіх вузлів графу
    array list_nodes(int тип);            // список всіх вузлів вказаного типу
    array list_edges();                   // список всіх ребер графу
    array list_edges(int тип);            // список всіх ребер вказаного типу
    node add_node(name);                  // додати новий вузол і повернути його
    edge add_edge(node з, node до);       // додати нове ребро з вузла «з» до вузла «до» і повернути його
    array overlay_edges(int іднакладки);  // список всіх вузлів у вказаній накладці
    edge add_overlay_edge(node з,
                          node до,
                          int іднакладки); // додати ребро вказаного спрямування до вказаної накладки

##### Ребра графу

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

    array adj_nodes();                    // список всіх сусідніх вузлів
    array adj_edges();                    // список з’єднаних ребер
    array input_edges();                  // список вхідних ребер
    array output_edges();                 // список всіх вихідних ребер
    array loop_edges();                   // список всіх циклічних ребер вузла
    array connected_edges(node target);   // всі ребра, що з’єднують цей вузол з вузлом «target»

##### Ребра графу

Якщо вказано ребра структури даних типу «граф», доступними будуть лише властивості основної структури даних.

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

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

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

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

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

Найкоротші відстані

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

          array distances node початок

### Модуль лінійних списків

#### Властивості і функції лінійних списків

##### Структура лінійного списку

Якщо вказано об’єкт структури даних типу «лінійний список», ви зможете викликати такі функції роботи з елементами:

    node begin();                           // повертає головний вузол лінійного списку
    setBegin(node begin):                   // робить вузол begin початковим вузлом списку і перевпорядковує список
    createNode();                           // створює новий вузол списку

##### Вузли пов’язаних списків

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

    node front();                           // повертає попередник вузла

##### Ребра лінійних списків

Якщо вказано ребра структури даних типу «лінійний список», доступними будуть лише властивості основної структури даних.

### Модуль «кореневого дерева»

#### Властивості і функції «кореневого дерева»

##### Модуль «кореневого дерева»

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

##### Структура «кореневе дерево»

Якщо вказано об’єкт структури даних типу «кореневе дерево», ви зможете виконувати читання або запис таких властивостей:

    ShowAllPointers     // встановіть значення true, якщо слід показувати всі ребра, або false, якщо кратні ребра слід спрощувати

Якщо вказано об’єкт структури даних типу «кореневе дерево», ви зможете викликати такі функції роботи з елементами:

    node add_data(string name);         // додати вузол з вказаною назвою до дерева
    void set_root_node(node root);      // зробити root кореневим вузлом дерева
    node root_node();                   // повертає кореневий вузол дерева

##### Вузли «кореневого дерева»

Якщо вказано об’єкт вузла типу «кореневе дерево», ви зможете виконувати читання або запис таких властивостей:

    int numberOfChilds                  // встановити кількість (дозволену) дочірніх вузлів цього вузла
    node left_child                     // лише читання: вузол, який є лівим дочірнім
    node right_child                    // лише читання: вузол, який є правим дочірнім
    node node_parent                    // лише читання: вузол, який є батьківським

Якщо вказано ребра структури даних типу «кореневе дерево», ви зможете викликати такі функції роботи з елементами:

    node add_left_child(node child);    // додати лівий дочірній
    node add_right_child(node child);   // додати правий дочірній
    node add_child(node child, int i);  // додати дочірній вузол як i-ий дочірній вузол вузла
    node add_node_parent(node child);   // додати батьківський вузол (буде успішним, лише якщо батьківського вузла ще не було)
    node left_child();                  // повертає правий дочірній
    node right_child();                 // повертає лівий дочірній
    node child_at(int i);               // повертає i-ий дочірній вузол вузла
    node node_parent();                 // повертає батьківський вузол вузла

##### Ребра «кореневого дерева»

Якщо вказано ребра структури даних типу «кореневе дерево», доступними будуть лише властивості основної структури даних.

### Керування виконанням скриптів

#### Включення файлів

Ваші документи скриптів можуть включати інші скрипти. Така можливість може бути корисною для зменшення розмірів документів скриптів та полегшення читання скриптів. За допомогою пункту меню Документ скрипту Можливі включення ви можете отримати список файлів скриптів, вже включених до пакунка &rocs;, якими ви можете скористатися. Включити файл скрипту можна такою командою:

    include_script(string path);            // відносний або абсолютний шлях до файла скрипту

#### Дані, виведені скриптами

Під час виконання алгоритму діагностичні повідомлення та повідомлення, виведені програмою, буде показано на панелі Вивід повідомлень. Якщо рушієм обробки скриптів буде виявлено синтаксичну помилку у вашому скрипті, відповідне повідомлення також буде показано серед діагностичних повідомлень. Зауважте, що всі повідомлення, виведені програмою, також буде показано і у списку діагностичних повідомлень (напівжирним шрифтом).

Керувати текстом, який буде виведено скриптом, можна за допомогою таких функцій:

    output(string message);            // виводить повідомлення до рядків виведення скрипту
    debug(string message);             // виводить повідомлення до рядків діагностичних повідомлень

#### Керування виконанням скриптів

Передбачено різні режими виконання ваших скриптів.

Керувати текстом, який буде виведено скриптом, можна за допомогою таких функцій:

- Пуск: виконати скрипт, аж до завершення його роботи.

- Стоп: припинити виконання скрипту (доступне, лише якщо виконується скрипт).

- Один крок: виконати скрипт до завершення одного кроку. Крок завершується, коли скриптом викликається функція `interrupt()`:

      interrupt();    // завершує крок

- Діагностика: виконати скрипт у режимі діагностики. Програма відкриє діалогове вікно діагностики QtScript.

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

### Обмін проектами &rocs;

Проекти &rocs; можна імпортувати та експортувати у форматі файлів архівів `.tar.gz`. Такими архівами можна скористатися для обміну проектами, імпортування та експортування можна здійснювати за допомогою пунктів меню Файл Імпортувати проект та Файл Експортувати проект, відповідно.

### Імпортування та експортування документів графів

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

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

- файли GML;

- Файли у форматі TGF

#### Формат файлів звичайних графів (TGF)

Звичайний формат графів (Trivial Graph Format або TGF) є простим текстовим форматом файлів, призначеним для опису графів. Файл TGF містить список визначень вузлів з прив’язкою ідентифікаторів вузлів до міток, за яким вказано список ребер. У такому форматі можливий запис лише однієї мітки на вузол і одного значення на ребро. &rocs; обробляє імпортовані графи у цьому форматі як неорієнтовані. Експортовані графи у цьому форматі міститимуть по два ребра на з’єднання, якщо з’єднання у них є двонапрямленими.

##### Специфікація формату

- Файл починається зі списку вузлів (один вузол на рядок), далі має бути рядок з єдиним символом «#», за яким має йти список ребер (по одному ребру на рядок).

- Запис вузла складається з цілого числа (ідентифікатора), пробілу і довільного рядка.

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

##### Приклад

    1 starting node
    2 transmitter
    3 sink
    #
    1 2 blue
    2 1 red
    2 3 green

#### Мова DOT та формат файлів графів Graphviz

Мова DOT є мовою текстового опису графів, у якій поєднується придатне до читання людиною представлення графів та можливості ефективної обробки графу програмами компонування. DOT є типовим форматом файлів для комплексу програм для візуалізації графів Graphviz, але цей формат також широко використовується іншими програмами для обробки графів. Типовими суфіксами назв файлів у форматі DOT є .gv та .dot.

##### Непідтримувані можливості

Програма &rocs; здатна обробляти всі файли графів, які містять дані, що відповідають специфікації мови DOT http://www.graphviz.org/content/dot-language. Передбачено повну підтримку можливостей мови, окрім таких виключень:

- підграфи: через відсутність концепції підграфів у &rocs;, підграфи (subgraph) імпортуються лише як набори елементів даних зі з’єднаннями. Зокрема, не імпортуються дані щодо вхідних і вихідних з’єднань між підграфами.

- Атрибути &HTML; і &XML;: атрибути (зокрема мітки) що містять синтаксичні конструкції &HTML; або &XML; читаються без обробки. Зокрема, не виконується обробка інструкцій щодо зміни шрифтів та стилю запису з атрибутів.

##### Приклад

    digraph myGraph {
        a -> b -> c;
        b -> d;
    }

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

&rocs;

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

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

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

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

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

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

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

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

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

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

&underFDL; &underGPL;

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

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

&install.intro.documentation;

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

&install.compile.documentation;

&documentation.index;