Nesta 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.");