TutorialNesta seção criaremos um projeto de exemplo para explorar algumas das funções mais importantes do Rocs. O objetivo é criar um grafo e um script que ilustre um algoritmo de 2 aproximações para o problema da cobertura mínima de vértices. Esse problema consiste em encontrar um subconjunto de nós do grafo C com um tamanho mínimo, de modo que cada aresta do grafo esteja conectada a pelo menos um nó do C. Este problema é conhecido por ser NP-difícil e queremos ilustrar como encontrar uma aproximação com um fator 2 computando uma correspondência no grafo dado.
Nosso objetivo é visualizar o relacionamento da ocorrência e da cobertura mínima de vértices. Para tal, queremos mostrar dois tipos de arestas, um para mostrar as arestas correspondentes e outro para mostrar as "normais", assim como dois tipos de nós que usamos para distinguir os nós contidos em C e os não-contidos.
Para criação do grafo, usamos o gerador de grafos padrão oferecido pelo Rocs. Ele pode ser encontrado no menu principal em → → . Aí, selecionamos um Grafo aleatório com 30 nós, 90 arestas e com uma raiz 1 (a raiz é o valor de referência inicial para o gerador de grafos aleatórios; a utilização da mesma raiz várias vezes origina grafos iguais).
Usamos os Tipos de elementos e criamos um segundo tipo de nó, assim como um segundo tipo de aresta. Para os novos tipos, abrimos a janela de propriedades, usando os respectivos botões de e definimos os IDs como 2. Além disso, mudamos as cores dos elementos desses dois novos tipos (para distingui-los dos tipos padrão). Finalmente, definimos todos os tipos de arestas como sendo bidirecionais e os IDs dos tipos padrão como 1.
Por último, temos de implementar o algoritmo de aproximação. Para isso, iremos usar a seguinte implementação:
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(); // define o conjunto de arestas não processadas
var C = new Array(); // arestas correspondentes
while (E.length
> 0) {
var e = E[0]; // escolhemos primeiro a aresta e={u,v}
var u = e.from();
var v = e.to();
e.type = 2; // define a aresta como sendo correspondente
E.shift(); // remove a 'e' (i.e., E[0]) da lista de arestas
C.push(u); // adiciona a 'u' ao C
C.push(v); // adiciona a 'v' ao C
// marcar o u,v como nós no C
u.type = 2;
v.type = 2;
// remove do E todas as arestas que incidem em 'u' ou 'v'
var adjacente = u.edges();
for (var i=0; i < adjacente.length; i++) {
var indice = E.indexOf(adjacente[i]); // localiza o índice
if (indice != -1) {
E.splice(indice, 1); // remove se já tiver encontrado
}
}
var adjacente = v.edges();
for (var i=0; i < adjacente.length; i++) {
var indice = E.indexOf(adjacente[i]); // descobrir o índice
if (indice != -1) {
E.splice(indice, 1); // remover se já tiver encontrado
}
}
}
Console.log("A cobertura de vértices contém " + C.length + " nós.");