Покрокові настановиУ цьому розділі ми створимо приклад проєкту для вивчення декількох найважливіших можливостей Rocs. Метою є створення графу та скрипту для ілюстрування простого 2-апроксимаційного алгоритму розв’язування задачі мінімального вершинного покриття. Задача мінімального вершинного покриття полягає у визначенні підмножини вузлів графу C мінімального розміру, такої, що кожне з ребер графу з’єднано з принаймні одним вузлом з C. Відомо, що ця задача має NP-складність. Ми хочемо проілюструвати спосіб визначення парної апроксимації обчисленням відповідника вказаного графу.
Нашою метою буде візуалізації зв’язку між відповідностями і мінімальним вершинним покриттям. Для цього ми визначимо два типи ребер: один для показу відповідних ребер і ще один для показу звичайних ребер; а також два типи вузлів, за допомогою яких відрізнятимемо вузли, що належать до C, і вузли, що не належать до C.
Для створення графу скористаймося типовим засобом створення графів Rocs. Викликати цей засіб можна за допомогою пункту основного меню → → . Виберемо Випадковий граф з 30 вузлами, 90 ребрами і зреном 1 (зерном є початкове значення для генератора випадкових значень; використання одного зерна призведе до створення тих самих графів).
Ми скористаємося панеллю Типи елементів і створимо другий тип вершин, а також другий тип ребер. Для обох нових типів ми відкриємо діалогове вікно властивостей за допомогою відповідних кнопок 
і встановимо ідентифікатори у значення 2. Далі, ми змінимо кольори елементів цих двох нових типів (для того, щоб їх було просто відрізнити від типових типів). Нарешті, ми встановимо двоспрямований тип ребер і визначимо для ідентифікаторів типових типів значення 1.
Нарешті, нам слід реалізувати алгоритм апроксимації. Для цього ми скористаємося таким кодом:
for (var i=0; i < Document.nodes.length; i++) {
Document.nodes[i].type = 1;
}
for (var i=0; i < Document.edges.length; i++) {
Document.edges[i].type = 1;
}
var E = Document.edges(); // набір необроблених ребер
var C = new Array(); // відповідні ребра
while (E.length
> 0) {
var e = E[0]; // беремо перше ребро e={u,v}
var u = e.from();
var v = e.to();
e.type = 2; // робимо ребро відповідним
E.shift(); // вилучити e (тобто E[0]) зі списку ребер
C.push(u); // додати u до C
C.push(v); // додати v до C
// позначити u,v як вузли у C
u.type = 2;
v.type = 2;
// вилучити з E усі ребра, суміжні з u або v
var adjacent = u.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.edges();
for (var i=0; i < adjacent.length; i++) {
var index = E.indexOf(adjacent[i]); // знайти індекс
if (index != -1) {
E.splice(index, 1); // вилучити його, якщо знайдено
}
}
}
Console.log("Покриття вершин містить " + C.length + " вузлів.");
