Olá tenho esse codigo que utiliza o Backtracking para resolver o problema de k clique como eu faço para utilizar o de força bruta para resolver o mesmo??
ENTRADA:
- G(V, E), um grafo não-direcionado e sem
peso nas arestas, e - k , um número natural, k em |V|
SAÍDA:
- Existe em G um subgrafo completo com
k vértices?
se alguem puder me ajudar
agradeceria muito
package CliqueGrafo;
import java.io.*;
import java.util.*;
import java.lang.Math;
//CliqueBT" classe encontra o k-clique em um gráfico usando o método de backtracking
public class CliqueBT {
private int [][] grafo; // uma matriz de adjacência de aresta para um grafo
private static int numAresta; // número total de arestas em um grafo
private static int sizeClique; // k = piso((1/2)*(log n)/log 2), n = |V|
private static int numClique; // número de k-cliques em um grafo
private Vector primeiroClique; // um k-clique encontrado pela primeira vez
// Construtor: criar uma estrutura de dados de um gráfico.
// Param numV número total de vértices em um grafo.
public CliqueBT(String numV) {
int n = new Integer(numV).intValue();
grafo = new int[n][n];
primeiroClique = new Vector();
sizeClique = (int)Math.floor(0.5*Math.log((double)n)/Math.log(2.0));
//sizeClique = 4;
}
/* / **
* Adicionar uma aresta da matriz adjacente ao ler pares de entrada.
* Para um grafo não direcionado, somente o triângulo superior direito da matriz será
* Preenchido com '1 ', se existe uma aresta.
* v um vértice incidente até a aresta
* x incidente o outro vértice da aresta
* /*/
public void addAresta(String v, String x) {
int idxV1 = new Integer(v).intValue();
int idxV2 = new Integer(x).intValue();
grafo[idxV1][idxV2] = 1;
numAresta++;
}
/* / **
* Verifique se existe uma aresta entre o vértice i e j. vértice
* /*/
public boolean isConnected(int i, int j) {
return grafo[i][j] == 1;
}
/* / **
* Utilizando DFS recursiva, encontrar k-cliques em um grrafo. Armazenar apenas o primeiro encontrado
* K-clique Considerando que conta o número de todos os k-cliques em um grafo.
* A um vetor a ser testada é se A j-clique
* j tamanho do clique para cada etapa intermediária no DFS
* /*/
public void doCliqueBT(Vector A, int j) {
// Se j é igual ao tamanho do clique, k, então A é k-clique no grafo
if (j == sizeClique) {
if (primeiroClique.isEmpty()) { primeiroClique = A; }
numClique++;
///////////////////////////////////////////////////////////////////
// O seguinte é para mostrar todos os k-cliques em um gráfico
// - Comentar esta parte, se o gráfico de entrada é esperado
// Para ter um monte de cliques tal.
System.out.print(" Vértices em um clique: ");
for (int i=0; i<A.size(); i++) {
Integer v = (Integer)A.get(i);
System.out.print(v.intValue()+", ");
}
System.out.println();
//
///////////////////////////////////////////////////////////////////
return;
}
else {
j = j + 1;
// Sj é o conjunto de todos os vetores candidato a j-clique
ArrayList Sj = new ArrayList();
if (j <= sizeClique) {
Sj = getCandidates(A);
}
if (!Sj.isEmpty()) {
// Para cada vetor candidato em Sj,
// Recursivamente fazer backtracking para k-clique
for (int i=0; i<Sj.size(); i++) {
Vector a = (Vector)Sj.get(i);
doCliqueBT(a, j);
}
}
}
}
/* / **
* Retorna um conjunto de candidatos, Sq, para q clique. Cada candidato é um vetor
* Em que um vértice recém adicionado deve ser maior do que o último vértice na
* Dado vetor, A, e deve ser ligado a todos os vértices na nota que o A.
* Vetores candidato são estendidos a partir do vetor dado A, adicionando
* Apenas um adicional de tempo cada vértice desse método é chamado.
* A (aq a1, a2, ...,) um vetor,
* um conjunto de candiates para q-clique
* /
*/
public ArrayList getCandidates(Vector A) {
// O conjunto de todos os vetores candidato para q-clique
ArrayList candidatos = new ArrayList();
// Se A é vazio, vamos sj ser um vetor com cada nó únicos em um gráfico.
if (A.isEmpty()) {
for (int i=0; i<grafo.length; i++) {
Vector sj = new Vector(1);
sj.add(new Integer(i));
candidatos.add(sj);
}
}
else {
Integer ultimo = (Integer)A.lastElement();
int q = ultimo.intValue()+1; // maior que o último de A
// Permutar todos os vetores candidato, satisfazendo a propriedade de sj
for (int j=q; j<grafo.length; j++) {
boolean allConnected = true;
Iterator iter = A.iterator();
//Verifique se 'j' vértice é adjacente a todos os vértices em A
while (iter.hasNext()) {
Integer v = (Integer)iter.next();
int i = v.intValue();
if (!isConnected(i,j)) {
//Corte ocorreu em poda - deixar de cumprir a propriedade de A
allConnected = false;
break;
}
}
if (allConnected) {
Vector sj = new Vector(A);
sj.add(new Integer(j));
candidatos.add(sj);
}
}
}
return candidatos;
}
/* / **
* Mostrar todos os resultados de backtracking.
* /*/
public void showResult() {
System.out.println(" Número total de vértices : "+grafo.length);
System.out.println(" Número total de arestas : "+numAresta);
System.out.println(" Valor de k (tamanho do clique) : "+sizeClique);
if (numClique == 0) {
System.out.println("Número de k-cliques encontrados: Não clique tais encontrado ");
}
else {
System.out.println(" Número de k-cliques encontrados : "+numClique);
System.out.print (" Vértices do clique encontrado pela primeira vez : ");
for (int i=0; i<primeiroClique.size(); i++) {
Integer v = (Integer)primeiroClique.get(i);
System.out.print(v.intValue()+" ");
}
}
System.out.println();
}
/* / **
* A função de nível superior que cria uma instância de 'CliqueBT' classe e
* Invoca seus métodos para encontrar k-cliques em grafos.
* @ Param args cordas de representação gráfica - número total de vértices
* Seguido por pares de vértices que indicam arestas.
* @ Throws IOException
* /*/
public static void main(String[] args) throws IOException {
System.out.println(" Digite um inteiro positivo 'n' seguido por " +
"um certo número de pares de inteiros \n na faixa de 0 a n-1" +
" N representa o número de vértices no gráfico, \n, e cada " +
"uv par representa uma aresta entre os vértices u e v."+
"\n \n Nota de Entrada: A primeira linha deve conter apenas o número de vértices."+
" Então, \n par ta de vértices separadas por espaço pode acompanhar a partir de "+
"a linha \n \t segundo. E, apenas uma das arestas duplicadas tais"+
" como \n \t (u, v) e (v, u) devem ser inseridos.");
System.out.println("Exemplo de entrada: Um gráfico de 5 vértices e E (0,1), "+
"e (0,3), e (1,2 ),..., e (3,4) \n \t \t deve ter uma entrada como mostrado abaixo.");
System.out.println("\t\t 5"); System.out.println("\t\t 0 1");
System.out.println("\t\t 0 3"); System.out.println("\t\t 1 2");
System.out.println("\t\t 1 4"); System.out.println("\t\t 2 3");
System.out.println("\t\t 2 4"); System.out.println("\t\t 3 4");
System.out.print("\nEnter a string representaion of a graph.\n" + "=> ");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String firstLine = br.readLine(); // Linha 1 contém apenas # dos vértices
StringTokenizer token = new StringTokenizer(firstLine);
String numNodes = token.nextToken();
// Criar uma instância com determinado número de nós em um gráfico
CliqueBT cliqueBT = new CliqueBT(numNodes);
// Leia todas as extremidades em forma de pares de vértices
String pair = br.readLine();
token = new StringTokenizer(pair);
while (token.hasMoreTokens()) {
if (token.countTokens() == 0) {
break; // par de entradas não mais
}
else {
String v = token.nextToken();
String x = token.nextToken();
cliqueBT.addAresta(v, x); // adicionar aresta para um gráfico
if (!token.hasMoreTokens()) { // não mais par nesta linha
pair = br.readLine(); // ler uma linha próxima
token = new StringTokenizer(pair);
}
}
}
// Carimbo do tempo de partida do algoritmo.
long tempo1 = System.currentTimeMillis();//metodo que verifica o tempo porem desconsidera o tempo de cpu
// Realizar backtracking para clique com a solução inicialmente vazia
cliqueBT.doCliqueBT(new Vector(), 0);
// Carimbo do tempo final do algoritmo.
long tempo2 = System.currentTimeMillis();
// Determinar o tempo de execução de DFS
long tempoExecucao = tempo2 - tempo1;
System.out.println("\n Running Time of the algorithm : "+(long)tempoExecucao+" ms.");
cliqueBT.showResult(); // mostrar resultados do backtracking para clique
}
}
/* //16
0 1 0 5 0 6 0 14 1 5
1 6 2 1 14 2 4 10 3 4
3 15 4 6 4 7 4 10 5 14 //exemplo de entrada
6 14 7 9 8 9 8 12 8 13
10 15 11 12 11 13 12 13*/
