В этом разделе будет представлен пример проекта для изучения некоторых наиболее важных функций 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 + ".");