O objetivo do projeto é analisar métodos de identificação de pontes em um grafo. Foram implementados um método baseado em Tarjan e um "descuidado" ou "naive". A identificação de pontes é parte importante para o algoritmo de Fleury, utilizado para a identificação de caminhos eulerianos.
Além das implmentações, são executadas tentativas de identiticação de caminhos eulerianos utilizando os dois métodos de identificação de pontes.
cd src/ && javac App && java -Xss1g AppPode ser necessário aumentar manualmente o tamanho da heap da stack java para a realização dos exemplos.
Executando exemplo para 100 vertices...
Criando grafo...
Gerando arestas aleatorias...
Encontrando um caminho euleriano seguindo o algoritmo de Fleury utilizando um metodo baseado em Tarjan...
Tempo para geração: 10 milisegundos
Encontrando um caminho euleriano seguindo o algoritmo de Fleury utilizando um metodo 'naive'...
Tempo para geração: 37 milisegundos
Executando exemplo para 1000 vertices...
Criando grafo...
Gerando arestas aleatorias...
Encontrando um caminho euleriano seguindo o algoritmo de Fleury utilizando um metodo baseado em Tarjan...
Tempo para geração: 23 milisegundos
Encontrando um caminho euleriano seguindo o algoritmo de Fleury utilizando um metodo 'naive'...
Tempo para geração: 453 milisegundos
Executando exemplo para 10000 vertices...
Criando grafo...
Gerando arestas aleatorias...
Encontrando um caminho euleriano seguindo o algoritmo de Fleury utilizando um metodo baseado em Tarjan...
Tempo para geração: 717 milisegundos
Encontrando um caminho euleriano seguindo o algoritmo de Fleury utilizando um metodo 'naive'...
Tempo para geração: 38816 milisegundos
Executando exemplo para 100000 vertices...
Criando grafo...
Gerando arestas aleatorias...
Encontrando um caminho euleriano seguindo o algoritmo de Fleury utilizando um metodo baseado em Tarjan...
Tempo para geração: 132172 milisegundos
Encontrando um caminho euleriano seguindo o algoritmo de Fleury utilizando um metodo 'naive'...
Tempo para geração: 6176659 milisegundos