TutorialEn esta sección queremos crear un proyecto de ejemplo para explorar algunas de las funciones más importantes de Rocs. El objetivo es crear un grafo y un guion que ilustre un sencillo algoritmo de aproximación a 2 para el problema de la cobertura de vértices mínima. En este problema se debe encontrar un subconjunto de nodos del grafo C del mínimo tamaño, de modo que cada arista de grafo esté conectada al menos a un nodo de C. Este problema es NP-complejo y deseamos ilustrar cómo encontrar una aproximación de factor 2 buscando una coincidencia en el grafo propuesto.
Nuestro objetivo es mostrar la correspondencia de las coincidencias y la cobertura de vértices mínima. Para ello, vamos a especificar dos tipos de aristas (uno para mostrar las aristas coincidentes y otro para mostrar las aristas «ordinarias»), así como dos tipos de nodos que vamos a usar para distinguir los nodos contenidos en C y los que no están contenidos en C.
Para crear el grafo, usaremos el generador por omisión que proporciona Rocs. Está disponible en menú principal: → → . Allí seleccionamos un Grafo aleatorio con 30 nodos, 90 aristas y semilla 1 (la semilla es la inicial para el generador de grafos aleatorios; si usa la misma semilla varias veces, se volverán a reproducir los mismos grafos).
Usaremos Tipos de elementos para crear un segundo tipo de nodo y un segundo tipo de arista. Para estos dos nuevos tipos, abriremos el diálogo de propiedades usando sus respectivos botones 
y fijaremos sus ID a 2. Además, cambiaremos los colores de los elementos de estos dos nuevos tipos (para distinguirlos de los tipos por omisión). Finalmente, indicaremos que todos los tipos de aristas sean bidireccionales y fijaremos el ID de los tipos por omisión a 1.
Por último, tenemos que implementar el algoritmo de aproximación. Para ello usaremos la siguiente implementación:
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(); // conjunto de aristas sin procesar
var C = new Array(); // aristas coincidentes
while (E.length
> 0) {
var e = E[0]; // tomamos la primera arista e={u,v}
var u = e.from();
var v = e.to();
e.type = 2; // indicamos que la arista es coincidente
E.shift(); // eliminar e (es decir, E[0]) de la lista de aristas
C.push(u); // añadir u a C
C.push(v); // añadir v a C
// marcar u,v como nodos en C
u.type = 2;
v.type = 2;
// eliminar de E todas las aristas en común con u o v
var adjacent = u.edges();
for (var i=0; i < adjacent.length; i++) {
var index = E.indexOf(adjacent[i]); // encontrar el índice
if (index != -1) {
E.splice(index, 1); // eliminarla si se encuentra
}
}
var adjacent = v.edges();
for (var i=0; i < adjacent.length; i++) {
var index = E.indexOf(adjacent[i]); // encontrar el índice
if (index != -1) {
E.splice(index, 1); // eliminarla si se encuentra
}
}
}
Console.log("La cobertura de vértices contiene " + C.length + " nodos.");
