TutorialNesta secção, iremos querer criar um projecto de exemplo para explorar algumas das funções mais importantes do Rocs. O objectivo é criar um grafo e um programa que ilustre um algoritmo de 2 aproximações para o problema da cobertura mínima de vértices. Este problema consiste em encontrar um sub-conjunto de nós do grafo C com um tamanho mínimo, de modo que cada aresta do grafo esteja ligada 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 factor 2, encontrando uma correspondência no grafo indicado.
O nosso objectivo é visualizar a correspondência 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 dados que usamos para distinguir os nós contidos em C e os não-contidos.
Para criar o grafo, o Rocs oferece um utilitário que poderá gerar grafos. Este está disponível no menu → → . Aí, iremos gerar 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 ambos os tipos novos, poderemos abrir a janela de propriedades, usando os respectivos botões de e configurar os ID's como 2. Para além disso, iremos mudar as cores dos elementos desses dois novos tipos (para os distinguir dos tipos predefinidos). Finalmente, configuramos todos os tipos de arestas como sendo bidireccionais e os ID's dos tipos predefinidos como 1.
Por último, temos de implementar o algoritmo de aproximação. Para tal, 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(); // 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; // configurar a aresta como sendo correspondente
E.shift(); // remover a 'e' (i.e., E[0]) da lista de arestas
C.push(u); // adicionar a 'u' ao C
C.push(v); // adicionar a 'v' ao C
// marcar o u,v como nós no C
u.type = 2;
v.type = 2;
// remover 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]); // descobrir o índice
if (indice != -1) {
E.splice(indice, 1); // remover 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.");