ATENÇÃO: O blog está de casa e cara nova.
O novo endereço agora é http://www.jjocenio.com.

Se você não for redirecionado automaticamente, por favor, clique link acima.

Algoritmo Menor Caminho

Semana passada me pediram ajuda com a implementação de um algoritmo de menor caminho. O pessoal precisava calcular a menor rota entre dois vértices de um grafo, levando em consideração o custo do caminho. Para quem ainda não percebeu, esse é o algoritmo desenvolvido por Djikstra.

Suponha que você tem um conjunto de pontos interligados, como lugares ligados por ruas e estradas, e precisa calcular o menor caminho entre dois pontos. O grafo abaixo mostra um exemplo de um situação como essa.


Os pontos podem ser cidades e os números nas setas podem ser vistos como a distância ou o custo entre duas cidades.

O algoritmo de Djikstra consistem em calcular o menor caminho, a partir da origem, a cada ponto caminhado no grafo até o destino. O código abaixo mostra como sua implementação é simples.

Note que o algoritmo verifica se o destino já foi alcançado e se o próximo vértice do grafo já foi percorrido. Isso impede que os caminhos sejam analisados indefinidamente.

public class Djikstra {

 /**
  * Calcula a menor rota entre a origem e o destino.
  * 
  * @param caminhoPercorrido
  *            O caminho percorrido até aqui
  * @return O custo total do caminho percorrido.
  */
 public static Double calcularMenorCaminho(Vertice origem,
   Vertice destino, List<Vertice> caminhoPercorrido) {

  Double menor = Double.POSITIVE_INFINITY;
  Double custo = 0.0;

  // Adiciona a origem ao caminho percorrido
  caminhoPercorrido.add(origem);

  // Se a origem for igual ao destino, encerra a busca
  if (origem.equals(destino)) {
   return custo;
  }

  // Armazena o caminho percorrido até aqui
  List<Vertice> caminhoAnterior = new ArrayList<Vertice>(
    caminhoPercorrido);
  List<Vertice> caminho = null;

  // Verifica cada caminho possível
  for (Entry<Vertice, Double> proximoVertice : origem
    .getProximosVertices().entrySet()) {

   // Inicia o novo caminho
   caminho = new ArrayList<Vertice>(caminhoAnterior);

   // Define o custo do caminho como infinito, pois ainda não se sabe
   // se ele leva ao destino desejado
   custo = Double.POSITIVE_INFINITY;

   // Percorre o caminho a partir do próximo nodo, desde que este não
   // tenha sido percorrido
   if (!caminho.contains(proximoVertice.getKey())) {
    custo = proximoVertice.getValue()
      + calcularMenorCaminho(proximoVertice.getKey(),
        destino, caminho);
   }

   // Verifica se o caminho percorrido é melhor que o anterior
   if (custo < menor) {
    menor = custo;

    // Atualiza o melhor caminho
    caminhoPercorrido.clear();
    caminhoPercorrido.addAll(caminho);
   }
  }

  return menor;
 }
}

A classe abaixo é utilizada para realizar a representação de um grafo. Organizando os pontos e os destinos acessíveis a partir de um ponto.
/**
 * Define os atributos de cada ponto no grafo e os possíveis
 * caminhos de saída de cada ponto
 */
class Vertice {

 private String nome;
 private Map<Vertice, Double> proximosVertices
    = new HashMap<Vertice, Double>();

 public Vertice(String nome) {
  super();
  this.nome = nome;
 }

 @Override
 public boolean equals(Object obj) {
  if (obj != null && obj instanceof Vertice) {
   Vertice objVertice = (Vertice) obj;

   return (this.nome == null && objVertice.nome == null)
     || this.nome.equals(objVertice.nome);
  }

  return false;
 }

 public String getNome() {
  return nome;
 }

 public Map<Vertice, Double> getProximosVertices() {
  return proximosVertices;
 }

 @Override
 public int hashCode() {
  return nome != null ? nome.hashCode() : 0;
 }

 @Override
 public String toString() {
  return nome;
 }
}

O trecho abaixo mostra construção do grafo e como o método é utilizado para o nosso exemplo.
public static void main(String[] args) {
 Vertice a = new Vertice("A");
 Vertice b = new Vertice("B");
 Vertice c = new Vertice("C");
 Vertice d = new Vertice("D");
 Vertice e = new Vertice("E");
 Vertice f = new Vertice("F");
 Vertice g = new Vertice("G");

 a.getProximosVertices().put(b, 1.0);
 a.getProximosVertices().put(c, 2.0);
 a.getProximosVertices().put(d, 1.0);

 b.getProximosVertices().put(e, 4.0);

 c.getProximosVertices().put(e, 3.0);

 d.getProximosVertices().put(f, 2.0);

 e.getProximosVertices().put(g, 7.0);
 e.getProximosVertices().put(f, 2.0);

 f.getProximosVertices().put(g, 3.0);

 b.getProximosVertices().put(c, 4.0);
 c.getProximosVertices().put(d, 1.0);
 c.getProximosVertices().put(b, 1.0);
 d.getProximosVertices().put(a, 1.0);
 d.getProximosVertices().put(e, 1.0);
 f.getProximosVertices().put(d, 2.0);

 List<Vertice> menorCaminho = new ArrayList<Vertice>();
 Double menorCusto = calcularMenorCaminho(a, g, menorCaminho);

 System.out.println(menorCusto);
 for (Vertice vertice : menorCaminho) {
  System.out.print("=> " + vertice.getNome() + " ");
 }
}

Dica Android: Separador de Categoria

Aqui vai uma dica rápida para quem desenvolve em Android e quer utilizar adicionar aos seus formulários um separador igual ao das telas de preferências. Basta configurar o TextView como mostrado abaixo.

<TextView android:layout_width="fill_parent"
android:layout_height="wrap_content"
android:text="Texto do Separador"
style="?android:attr/listSeparatorTextViewStyle"/>

Simples assim.

Conexão SSL em aplicações JAVA

O uso de SSL para criptografar a comunicação entre o cliente e as aplicações é muito comum, principalmente em webservices. Em JAVA, isso acaba causando problemas que, apesar de serem simples de solucionar, são pouco documentados ou a documentação é de difícil acesso. Por isso, resolvi escrever este post para ajudar na solução desses problemas.

Na comunicação via SSL, ao enviar a primeira requisição o cliente recebe o certificado do servidor, que contem uma chave pública. O cliente então utiliza essa chave pública para criptografar os dados antes de cada requisição para o servidor, que por sua vez utiliza a sua chave privada para decriptografar os dados antes de processá-lo.

Em Java, existe o conceito de certificados confiáveis, que são aqueles armazenados em um repositório de chaves, chamado keystore. Ao tentar estabelecer a requisição, a JVM utiliza o gerenciador de certificados para aceitar ou não a conexão. Caso o certificado não esteja importado ou o keystore não esteja presente a conexão será rejeitada.

Para resolver esse problema pode-se usar duas abordagens. A primeira é importar manualmente o certificado e informar a JVM qual keystore utilizar. Para importar o certificado, é necessário primeiro fazer o download (.cer), o que pode ser feito pelo browser, e então utilizar o utilitário keytool para importá-lo.
keytool -importcert -alias certificado_do_servidor -keystore arquivo_keystore -file arquivo.cer
O keytool solicitará a senha do keystore para armazenar o certificado.

Feito isso, agora falta informar a JVM sobre o keystore que deve ser utilizado. Isso é feito por meio de variáveis de ambiente que podem ser passadas para a JVM pela linha de comando, utilizando a notação -Dnome=valor, ou dentro do seu código, utilizando o método System.setProperty. As variáveis que devem ser definidas são:
javax.net.ssl.trustStore=/caminho/arquivo_keystore
javax.net.ssl.trustStorePassword=senha_keystore
O problema dessa solução é que você precisa primeiro importar o certificado manualmente antes de distribuir sua aplicação e, no caso de uma mudança do certificado, sua aplicação pode parar de funcionar, apresentando o erro SSLHandshakeException, e aí você precisaria importar o novo certificado. A segunda abordagem é um pouco mais complicada, mas evita que a aplicação quebre quando houver mudanças de certificados.

Ao estabelecer uma conexão SSL a JVM utilizará um contexto SSL. O que faremos é criar um novo contexto SSL, substituindo o gerenciador de certificados por uma implementação customizada, que  importará os novos certificados automaticamente.

A seguir, está a classe customizada para gerenciamento dos certificados.
/**
 * Classe responsável pelo gerenciamento dos certificados
 */
public class CustomTrustManager implements X509TrustManager {

 // Nome da variável de ambiente que contem a senha 
 // do arquivo de keystore
 private static final String SENHA_KEYSTORE_VAR = 
    "javax.net.ssl.trustStorePassword";
 // Nome da variável de ambiente que contem o caminho 
 // para o arquivo de keystore
 private static final String TRUST_STORE_VAR = 
    "javax.net.ssl.trustStore";


 // O caminho para o arquivo de keystore
 private String keyStorePath;

 // A senha do arquivo de keystore
 private String senhaKeystore;

 // O objeto keystore que será carregado do arquivo
 private KeyStore keyStore;

 // O gerenciador padrão, que será utilizado pela nossa classe
 // evitando que precisemos reimplementar toda a 
 // lógica de gerenciamento
 private X509TrustManager trustManager;

 public CustomTrustManager() throws Exception {
  super();
  
  // Carrega os certificados armazenados
  setKeyStorePath();
  
  // Inicia o gerenciador padrão
  getTrustManager();
 }

 // Método obrigatório para implementar a interface do gerenciador
 public void checkClientTrusted(X509Certificate[] chain, 
   String authType) throws CertificateException {

  // Utiliza o gerenciador padrão para executar a verificação
  trustManager.checkClientTrusted(chain, authType);
 }

 // Método obrigatório para implementar a interface do gerenciador
 public void checkServerTrusted(X509Certificate[] chain, 
   String authType) throws CertificateException {

  try {
   // Utiliza o gerenciador padrão para executar a verificação
   trustManager.checkClientTrusted(chain, authType);
  } catch (CertificateException e) {
   // No caso de erro, o certificado é importado e 
   // a verificação é refeita
   adicionarCertificado(chain);
   trustManager.checkClientTrusted(chain, authType);
  }
 }

 // Método obrigatório para implementar a interface do gerenciador
 public X509Certificate[] getAcceptedIssuers() {
  // Utiliza o gerenciador padrão recuperar os certificados
  return trustManager.getAcceptedIssuers();
 }

 // Método responsável por importar o certificado
 private void adicionarCertificado(X509Certificate[] chain) 
  throws CertificateException {
 
  // É comum que o certificado contenha toda a rede de certificação.
  // Nesse caso, toda ela será carregada
  for (X509Certificate cert : chain) {
   try {
    // Armazena o certificado com o alias Certificado_X_Y, 
    // onde X é o serial e Y é o Current Time Millis.
    // Isso evita a duplicidade de alias.
    keyStore.setCertificateEntry("Certificado_" 
      + cert.getSerialNumber() + "_"
      + System.currentTimeMillis(), cert);
   } catch (KeyStoreException e) {
   throw new CertificateException("Erro ao aceitar o certificado.", e);
   }
  }

  try {
   // Armazena os certificados no arquivo informado pela
   // variável de ambiente com a senha específica
   OutputStream streamKeyStore = new FileOutputStream(
      new File(keyStorePath));
   keyStore.store(streamKeyStore, senhaKeystore.toCharArray());
   getTrustManager();
  } catch (Exception e) {
  throw new CertificateException("Erro ao aceitar o certificado.", e);
  }
 }

 // Método responsável por iniciar o gerenciador de certificados
 protected void getTrustManager() throws Exception {
  // Recupera o algoritmo default de certificados
  String algoritmo = TrustManagerFactory.getDefaultAlgorithm();
  // Recupera a fabrica de gerenciadores para o algoritmo padrão
  TrustManagerFactory fabricaTM = 
      TrustManagerFactory.getInstance(algoritmo);

  // Inicia a fábrica com o keystore
  fabricaTM.init(this.keyStore);

  // Recupera todos os gerenciadores do sistema para encontrar o 
  // responsável pelos certificados
  TrustManager tms[] = fabricaTM.getTrustManagers();
  for (TrustManager tm : tms) {
   if (tm instanceof X509TrustManager) {
    this.trustManager = (X509TrustManager) tm;
    return;
   }
  }

  // Caso não seja encontrado um gerenciador para os certificados, 
  // lança a exceção
  throw new NoSuchAlgorithmException("TrustManager não encontrado!");
 }

 // Método responsável por carregar o keystore do arquivo especificado
 protected void setKeyStorePath() throws Exception {
  // Recupera o caminho do arquivo e a senha do keystore
  this.keyStorePath = System.getProperty(TRUST_STORE_VAR);
  this.senhaKeystore = System.getProperty(SENHA_KEYSTORE_VAR);

  if (this.keyStorePath == null) {
   throw new KeyStoreException("O caminho do keystore não pode " +
     " ser null. Informe em " + TRUST_STORE_VAR);
  }

  // Obtem o keystore para o tipo padrão do sistema
  this.keyStore = KeyStore.getInstance(KeyStore.getDefaultType());
  
  // Inicia o stream para leitura dos certificados já importados
  InputStream streamKeyStore = 
      new FileInputStream(new File(keyStorePath));

  try {
   // Carrega os certificados já importados utilizando 
   // a senha informada
   this.keyStore.load(streamKeyStore, senhaKeystore.toCharArray());
  } finally {
   if (streamKeyStore != null) {
    streamKeyStore.close();
   }
  }
 }
}
Perceba que os métodos obrigatórios da interface são implementados por delegação para um gerenciador que foi obtido do sistema. Dessa forma evitamos a implementação de toda a lógica de um gerenciador padrão e somente fazemos o tratamento necessário no momento de carregar os certificados que ainda não foram importados. Note também que é obrigatório que já exista um arquivo de keystore.

Vejamos agora como utilizar o nosso gerenciador para realizar a conexão com um servidor https do qual não possuímos o certificado.
public class TesteHttpsURLConnection {

  public static void main(String[] args) throws Exception {
  
  // Define a variável de ambiente com o caminho do keystore
  System.setProperty("javax.net.ssl.trustStore", "/tmp/keystore");
  // Define a variável de ambiente com a senha do keystore
  System.setProperty("javax.net.ssl.trustStorePassword", "changeit");

  // Recupera o contexto SSL
  SSLContext context = SSLContext.getInstance("SSL");
  // Define o nosso gerenciador como o gerenciador default do contexto
  context.init(null, 
     new TrustManager[] { new CustomTrustManager() }, null);

  // Cria a conexão com o endereço https
  URL httpsURL = new URL("https://internetbanking.caixa.gov.br/");
  HttpsURLConnection connection = 
     (HttpsURLConnection) httpsURL.openConnection();
  // Define a fábrica de sockets do nosso contexto
  connection.setSSLSocketFactory(context.getSocketFactory());

  // Realiza a conexão
  connection.connect();
  
  // Exibe as chaves dos certificados do servidor
  Certificate[] certs = connection.getServerCertificates();
  for (Certificate cert: certs) {
   System.out.println(cert.getPublicKey());
  }
 }
}
Como demonstração, você pode executar o main sem a linha que define o socket factory para ver que será lançada a exceção SSLHandshakeException.

Se você utilizar o utilitário keytool para verificar os certificados no arquivo de keystore, verá que todos os certificados do servidor foram armazenados lá. Evitando que seja necessário importá-los novamente.

Manipulando imagens com ImageMagick

Para aqueles que não conhecem, o ImageMagick é uma suíte de programas para manipular imagens com suporte a uma grande variedade de formatos e que é tipicamente utilizada pela linha de comando. É possível utilizar o ImageMagick para redimensionar, rotacionar, espelhar, adicionar texto, entre outras funcionalidades e é muito (muito mesmo) útil quando você precisa alterar dezenas ou centenas de arquivos.

O ImageMagick possui ainda bibliotecas em várias linguagens para que você possa adicionar funcionalidades de manipulação de imagens na sua aplicação. Entre as versões disponíveis estão implementações em C, JAVA, .NET e PHP.

Apesar de todos os recursos disponíveis na suíte, a grande maioria dos usuários utilizará as funções de redimensionar e converter imagens. Essas são as que eu, particularmente, mais utilizo. Sendo assim, essas serão as funcionalidades que mostrarei aqui.

Para redimensionar uma imagem o usuário pode fazê-lo utilizando o aplicativo mogrify com no comando abaixo.
mogrify -resize LARGURAxALTURA arquivo
mogrify -resize 800x600 imagem.jpg
Neste caso, o programa irá alterar as dimensões da imagem mantendo a proporção, ou seja, a largura será alterada para, no máximo, 800 pixels e a altura será alterada proporcionalmente até 600 pixels, no máximo.
mogrify -resize 800x600! imagem.jpg
Neste outro exemplo, a imagem será redimensionada ignorando a proporção e terá exatamente as medidas fornecidas.
mogrify -resize 50% imagem.jpg
No exemplo acima, a imagem será redimensionada para 50% do seu tamanho original, mantendo a proporção.

A conversão de imagens é uma operação ainda mais simples. O programa convert fornece diversas formas de conversão e pode ser usado da seguinte forma.
convert arquivo.jpg arquivo.png
Neste exemplo, o arquivo será convertido do formato jpg para png e pode utilizar coringas na seleção de arquivos.
convert *.jpg *.png
O programa permite, por exemplo, juntar vários arquivos em um só.
convert *.jpg arquivounico.pdf
Além desses, a suíte ImageMagick fornece inúmeros outros recursos para tratamento de imagens, que você pode explorar mais profundamente em http://www.imagemagick.org/script/command-line-tools.php.