Document Actions
Implementação do código
Realizando permutações
O código abaixo realiza a permutação entre índices nas linhas através do método ChangeMatrixRows() e nas coluns através do método ChangeMatrixCols().
Perceba que o parametro aIndexes[], existente nos dois métodos, é o vertor que possui a permutação que deve ser realiza. Nesse vetor o valor presente no índice i é o número que indica a troca da linha/coluna i pela linha/coluna aIndexes[i].
O método cloneMatrix() retorna a cópia de uma nova instância da matriz que foi passada como parametro.
//
// ChangeMatrixRows - Troca linhas de uma matrix
private void ChangeMatrixRows( int aMatrix[][], int aIndexes[] ) {
int aSourceMatrix[][] = this.cloneMatrix( aMatrix);
for ( int x = 0; x < aMatrix.length; x++ )
for ( int y = 0; y < aMatrix.length; y++ )
aMatrix[x][y] = aSourceMatrix[aIndexes[x]][y];
}
//
// ChangeMatrixCols - Troca colunas de uma matrix
private void ChangeMatrixCols( int aMatrix[][], int aIndexes[] ) {
int aSourceMatrix[][] = this.cloneMatrix( aMatrix);
for ( int y = 0; y < aMatrix.length; y++ )
for ( int x = 0; x < aMatrix.length; x++ )
aMatrix[x][y] = aSourceMatrix[x][aIndexes[y]];
}
Executando o algoritmo de força bruta
O algoritmo de força bruta consiste em:
- Obter permutação da ordem dos vértices
- Obter uma cópia de G2
- Realizar permutação das linhas em G2
- Realizar permutação das colunas em G2
- Comparar G1 com G2
- Se G1 fo igual G2 para execução, se forem diferentes repete os passos anteriores
Nessa implementação a calsse que gera permutações (GenratorPermutation) foi obtida em http://www.merriampark.com/perm.htm.
As variáveis aAdjGraph1 e aAdjGraph2 são as matrizes de adjacência dos grafos G1 e G2.
A variável aVertexRelationshipMap é um vertor que indica a relação de correspondência entre os vértices dos grafos G1 e G2.
//
// PermutationAnalysis - Realiza permutações para tentar obter grafo isomorfo.
private boolean PermutationAnalysis() {
// Obtém Gerador de permutações
PermutationGenerator aPermut = new PermutationGenerator( this.aAdjGraph2.length );
// Enquanto houver permutações...
while ( aPermut.hasMore()) {
// Obtém próxima permutação
int aIndexes[] = aPermut.getNext();
// Obtém uma cópia temporaria da matrix que será modificada
int aTempAnalisysMatrix[][] = this.cloneMatrix( this.aAdjGraph2 );
// Troca as linhas reais pelas linhas da permutação atual.
this.ChangeMatrixRows( aTempAnalisysMatrix, aIndexes );
// Troca as Colunas reais pelas colunas da permutação atual.
this.ChangeMatrixCols( aTempAnalisysMatrix, aIndexes );
// Compara as matrizes
if ( this.CompareMatrix( this.aAdjGraph1, aTempAnalisysMatrix )) {
this.aVertexRelationshipMap = aIndexes;
return true;
}
}
return false;
}
Carregando os grafos com o roxGt
A API do roxGt fornece um método para carregar um arquivo .graph e também um metódo para obter a matriz de adjacência de um grafo carregado.
// Carrega arquivo que contém o grafo IGraph oGraph1 = GraphUtils.getInstance().getGraph( "myGraph.graph" ); IGraph oGraph2 = GraphUtils.getInstance().getGraph( "myGraph1.graph" ); // Obtém matrizes de ajacência int oAdjGraph1[][] = GraphUtils.getInstance().getAdjacencyMatrix( oGraph1 ); int oAdjGraph2[][] = GraphUtils.getInstance().getAdjacencyMatrix( oGraph2 ); // Realiza análise IsomorphAnalysis oIsomorphAnalysis = new IsomorphAnalysis( oAdjGraph1, oAdjGraph2 ); boolean bIsIsomorph = oIsomorphAnalysis.getResult();
Forgot your password?
New user?