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.

Rode tudo com Crossover

Apesar de concordar que na grande maioria das vezes as soluções disponíveis no linux serem tão boas ou até melhores que as soluções disponíveis em Windows, as vezes simplesmente não dá.

Eu, por exemplo, trabalho muito com Enterprise Architect da sparx e com o MS Visio. O EA é uma ferramente UML sem comparações. Até acho que o ArgoUML é bom, mas não é comparável ao EA. O DIA, em termos de funcionalidade é bom para diagramas, mas as figuras são 'feinhas' e é difícil encontrar outras novas.

Pois bem, esses dias encontrei o Crossover da CodeWeavers (http://www.codeweavers.com/products/cxlinux/). Apesar de ser pago, acho, sinceramente, que ele vale os quase US$ 70 que cobra pela versão professional. Não só pelas facilidades e funcionalidades que possui, mas, principalmente, por dar a opção de utilizar o SO de minha preferência para executar os programas que desejo.

Controle remoto do PC

Há algum tempo vinha procurando uma forma de controlar o pc remotamente a partir de algum dispositivo pequeno, como o celular por exemplo. Minha idéia é montar uma estação multimídia com um PC ligado à TV e ao equipamento de som.

Talvez alguns já conheçam, mas eu só o descobri ontem. É o anyremote. Um ótimo aplicativo que permite controlar o PC inteiro através do celular. A conexão pode ser feita por uma série de formas: bluetooth, wi-fi, irda, serial, cabo, etc. No meu caso, estou usando bluetooth, pois o meu celular não tem wi-fi :(. O aplicativo ainda conta com uma interface gráfica para GNome e outra para KDE, gAnyremote e kAnyremote, respectivamente.

O anyremote se baseia em scripts de configuração que definem as ações para cada tecla pressionada. Isso traz uma flexibilidade impressionante. Atendeu perfeitamente as minhas necessidades.

Instalar o aplicativo é muito simples (para quem usa Debian ou Ubuntu, ele está disponível pelo apt-get). É preciso ainda instalar uma pequena aplicação cliente no celular. Depois de iniciar o anyremote, basta entrar na aplicação no celular, menu opções e escolher a forma de conexão (no meu caso, 'Enter BT address') e pronto o celular virou uma extensão do meu Linux.

Para saber mais detalhes sobre instalação e configuração do anyremote, visite http://anyremote.sourceforge.net/ , ou veja o ótimo tutorial sobre isso no Viva o Linux no endereço http://www.vivaolinux.com.br/artigo/Transforme-seu-celular-em-controle-remoto-Bluetooth-no-Linux/ .

Geração de chaves em Java

Nesse post quero demonstrar como gerar um par de chaves publica-privada para criptografia.

O idéia de par de chaves é bem simples:
  • Gera-se um par de chaves, uma pública e uma privada;
  • A chave pública é distribuída para quem for de interesse e a chave privada fica com o dono da chave;
  • Antes de enviar uma mensagem, por exemplo, o remetente usa a chave pública para criptografá-la;
  • Uma vez criptografada, a mensagem só poderar ser descriptografada utilizando a chave privada. Como só o destinatário possui essa chave, só ele poderá ler a mensagem.
Junto com a instalação padrão do JDK, vem uma pequena ferramenta chamada keytool, que serve para genrenciamento de chaves e certificados.
keytool -genkeypair -alias jarbaslima -keyalg DSA -keysize 1024 -keystore chave-jarbaslima.keystore -storepass jl123s
  • O primeiro parâmetro (-genkeypair) é o comando;
  • O segundo informa um apelido para o par de chaves;
  • O terceiro é o algoritmo usado na geração;
  • O quarto é o tamanho da chave. Quanto maior, mais seguro e mais lento;
  • O quinto é o nome do arquivo onde será armazenado o par de chaves;
  • O último é a senha que irá proteger o arquivo;
O keytool solicita uma série de informações sobre quem está gerando a chave: nome, empresa, departamento, cidade, estado e país.
Depois de gerada, nós precisamos agora exportar a chave pública (certificado) para que seja distribuído.
keytool -exportcert -alias jarbaslima -keystore chave-jarbaslima.keystore -file jl-chavepublica.cert
O parâmetro -file informa para qual arquivo a chave deve ser exportada.
Para saber mais sobre o keytool, consulte http://java.sun.com/javase/6/docs/technotes/tools/windows/keytool.html