Como gerar grafos no formato .dot usando JGraphT

grafoA linguagem DOT é uma linguagem para descrição de grafos interpretada pelo GraphViz e também pelo Gephi para visualização de grafos. A biblioteca JGraphT dispõe de classes para exportação de grafos para este formato.

O código abaixo em Java, cria um grafo aleatório e exporta para um arquivo .dot. A figura ao lado mostra o grafo com dez vértices gerado a partir do código de exemplo, como o programa gera grafos aleatórios, outras execuções podem resultar em grafos diferentes.

Continuar lendo

Como instalar o JGraphT no Eclipse

JGraphT é uma biblioteca Java gratuita para trabalhar com algoritmos da teoria dos grafos. A instalação no eclipse segue em cinco passos.

  1. Baixe o JGraphT e descompacte;
  2. Crie um projeto java no Eclipse normalmente;
  3. Windows > Preferences > Java > Build Path > User Libraries -> New ->”Dê um nome, Jgraph, por exemplo” -> Add External JARs (jgraph-5.13.0.0.jar e os demais na pasta lib)
  4. Project > Properties > Java Build Path -> Na aba ‘Library‘ -> Add Library -> User Library -> Next  -> Escolha ‘Jgraph’ -> Finish
  5. Agora é possível importar o Jgrapht no código.
    import org.jgrapht.*;

A arte de provar a complexidade de algoritmos

A teoria da complexidade, grosseiramente falando, preocupa-se em classificar os problemas computacionais de acordo com a sua dificuldade, assim, existem problemas resolvidos em tempo polinomial e aqueles resolvidos em tempo exponencial. Daí, temos as classes dos problemas P, NP, NP-completos, NP-difíceis e vários outros.

Provar que um problema é mais difícil que outro uma vez que não se encontrou um algoritmo que o resolve em tempo polinomial, consiste em transformar um problema que já se sabe da sua dificuldade para que ele seja resolvido pelo problema que se deseja provar a NP-completude ou NP-dificuldade.

Continuar lendo

Algoritmos em Português com Latex

Existem vários ambientes no \LaTeX que alg2permitem escrever pseudo código sem muitas dificuldades, um que eu particularmente achei muito interessante e prático é o ambiente algorithm2e.

Além de deixar algoritmos muito bonitos ele tem vários idiomas como opção, inclusive o português.  Para instruções de uso veja aqui a documentação.

Infelizmente, quando fui usar pela primeira vez encontrei algumas inconsistências que dependendo da urgência do trabalho pode ser um tanto inconveniente. E eu vou mostrar aqui como resolver.

Continuar lendo