EsercitazioneIn questa sezione vogliamo elaborare un progetto di esempio per esplorare alcune tra le più importanti funzioni di Rocs. L'obiettivo è quello di creare un grafo e uno script che illustrino un semplice algoritmo di approssimazione di fattore 2, per trattare un problema di copertura minima dei vertici. Questo problema può essere descritto come la ricerca del più piccolo sottoinsieme C di vertici in un grafo tale che ogni arco ha almeno un'estremità in C. Si tratta di un problema NP-completo e il nostro obiettivo è quello di trovare un'approssimazione di fattore 2 attraverso la computazione di una corrispondenza all'interno di un grafo dato.
Il nostro obiettivo è di visualizzare la corrispondenza tra l'accoppiamento e la copertura minima dei vertici. Per ottenere questo obiettivo dobbiamo specificare due tipi di archi, uno per mostrare gli archi accoppiati e l'altro per mostrare gli archi «ordinari»; dobbiamo specificare inoltre due tipi di nodi, che useremo per distinguere i nodi contenuti in C da quelli non contenuti in C.
Per creare il grafo usiamo il generatore di grafi fornito da Rocs, che si trova in → → . In questo modo selezioniamo un «grafo casuale» composto di 30 nodi, 90 archi, e con seme di generazione 1 (il seme determina la casualità del grafo; partendo dallo stesso seme si riproduce lo stesso grafo).
Usiamo Tipi di elementi per creare sia un secondo tipo di nodo sia di arco. Dobbiamo aprire la finestra delle proprietà di entrambi questi due nuovi tipi facendo clic sul rispettivo pulsante delle 
per impostare gli ID a 2; dobbiamo anche cambiare il colore degli elementi di questi due nuovi tipi (per distinguerli da quelli predefiniti). Infine dobbiamo impostare tutti i tipi di archi come bidirezionali, e gli ID del tipo predefinito a 1.
Al minimo è necessario implementare l'algoritmo di approssimazione. Per farlo si utilizza la seguente implementazione:
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(); // insieme degli archi non esaminati
var C = new Array(); // archi accoppiati
while (E.length
> 0) {
var e = E[0]; // prende il primo arco e={u,v}
var u = e.from();
var v = e.to();
e.type = 2; // imposta l'arco come arco accoppiato
E.shift(); // elimina l'arco e (i.e., E[0]) dalla lista degli archi
C.push(u); // aggiunge u a C
C.push(v); // aggiunge v a C
// segna u,v come nodi di C
u.type = 2;
v.type = 2;
// rimuove da E tutti gli archi incidenti a u o v
var adjacent = u.edges();
for (var i=0; i < adjacent.length; i++) {
var index = E.indexOf(adjacent[i]); // trova l'indice
if (index != -1) {
E.splice(index, 1); // elimina l'indice dopo averlo trovato
}
}
var adjacent = v.edges();
for (var i=0; i < adjacent.length; i++) {
var index = E.indexOf(adjacent[i]); // trova l'indice
if (index != -1) {
E.splice(index, 1); // elimina l'indice dopo averlo trovato
}
}
}
Console.log("Vertex Cover contains " + C.length + " nodes.");
