Пример работы с RocsВ этом разделе будет представлен пример проекта для изучения некоторых наиболее важных функций Rocs. Цель состоит в том, чтобы создать граф и сценарий, иллюстрирующий простой алгоритм для задачи минимального вершинного покрытия. Задача минимального вершинного покрытия — это задача поиска подмножества вершин графа С минимального размера, такого, чтобы каждое ребро графа было соединено по крайней мере с одной вершиной в С. Эта задача является NP-сложной, и пример ниже иллюстрирует, как найти приближение фактора 2, вычисляя соответствие на заданном графе.
Цель — визуализировать взаимосвязь соответствия и минимального покрытия вершин. Для этого следует указать два типа рёбер, один для отображения совпадающих рёбер, а другой — для отображения «обычных». Также следует указать два типа вершин, которые будут использоваться для обозначения вершин, содержащихся и не содержащихся в 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 + ".");
