grafos
Interface AlgoritmosEmGrafos

public interface AlgoritmosEmGrafos

Method Summary

java.util.Collection<Aresta>	agmUsandoKruskall(Grafo g) Retorna a árvore geradora mínima utilizando o algoritmo Kruskall.
java.util.Collection<Aresta>	agmUsandoPrim(Grafo g) Retorna a árvore geradora mínima utilizando o algoritmo Prim.
java.util.Collection<Aresta>	arestasDeArvore(Grafo g) Arestas de arvore.
java.util.Collection<Aresta>	arestasDeAvanco(Grafo g) Arestas de avanço.
java.util.Collection<Aresta>	arestasDeCruzamento(Grafo g) Arestas de cruzamento.
java.util.Collection<Aresta>	arestasDeRetorno(Grafo g) Arestas de retorno.
java.util.ArrayList<Aresta>	caminhoMaisCurto(Grafo g, Vertice origem, Vertice destino) Retorna (em ordem) as arestas que compoem o caminho mais curto entre um par de vértices.
Grafo	carregarGrafo(java.lang.String path, TipoDeRepresentacao t) Carrega grafo do arquivo texto.
java.util.Collection<java.util.Collection<Vertice>>	componentesFortementeConectados(Grafo g) Retorna todos os conjuntos de vértice fortemente conectados.
double	custoDaArvoreGeradora(Grafo g, java.util.Collection<Aresta> arestas) Calcula o custo de uma árvore geradora.
double	custoDoCaminho(Grafo g, java.util.ArrayList<Aresta> arestas, Vertice origem, Vertice destino) Dado um caminho, esta função calcula o custo do caminho.
boolean	ehArvoreGeradora(Grafo g, java.util.Collection<Aresta> arestas) Testa se a árvore é geradora.
boolean	ehCaminho(java.util.ArrayList<Aresta> arestas, Vertice origem, Vertice destino) Verifica se a sequencia de arestas é caminho entre oriem e destino.
boolean	existeCiclo(Grafo g) Verifica se existe ciclo no grafo.
java.util.ArrayList<java.util.ArrayList<Vertice>>	ordenacaoTopologica(Grafo g) Retorna (em ordem) todos os conjuntos da ordenação topológica.

Method Detail

carregarGrafo

Grafo carregarGrafo(java.lang.String path,
                    TipoDeRepresentacao t)
                    throws java.lang.Exception

Carrega grafo do arquivo texto. O formato será definido do site da disciplina

Parameters:

path -

Returns:

um objeto grafo com as informações representadas no arquivo.

Throws:

java.lang.Exception - Caminho inválido ou árquivo fora do padrão.

existeCiclo

boolean existeCiclo(Grafo g)

Verifica se existe ciclo no grafo.

Parameters:

g - Grafo.

Returns:

True, se existe ciclo, False, em caso contrário.

componentesFortementeConectados

java.util.Collection<java.util.Collection<Vertice>> componentesFortementeConectados(Grafo g)

Retorna todos os conjuntos de vértice fortemente conectados.

Parameters:

g - O grafo.

Returns:

Retorna todos os conjuntos de vértice fortemente conectados.

ordenacaoTopologica

java.util.ArrayList<java.util.ArrayList<Vertice>> ordenacaoTopologica(Grafo g)

Retorna (em ordem) todos os conjuntos da ordenação topológica.

Parameters:

g - O grafo.

Returns:

todos os conjuntos da ordenação topológica.

agmUsandoPrim

java.util.Collection<Aresta> agmUsandoPrim(Grafo g)

Retorna a árvore geradora mínima utilizando o algoritmo Prim.

Parameters:

g - O grafo.

Returns:

Retorna a árvore geradora mínima utilizando o algoritmo Prim.

agmUsandoKruskall

java.util.Collection<Aresta> agmUsandoKruskall(Grafo g)

Retorna a árvore geradora mínima utilizando o algoritmo Kruskall.

Parameters:

g - O grafo.

Returns:

Retorna a árvore geradora mínima utilizando o algoritmo Kruscall.

custoDaArvoreGeradora

double custoDaArvoreGeradora(Grafo g,
                             java.util.Collection<Aresta> arestas)
                             throws java.lang.Exception

Calcula o custo de uma árvore geradora.

Parameters:

arestas - As arestas que compoem a árvore geradora.

g - O grafo.

Returns:

O custo da árvore geradora.

Throws:

java.lang.Exception - Se a árvore apresentada não é geradora do grafo.

ehArvoreGeradora

boolean ehArvoreGeradora(Grafo g,
                         java.util.Collection<Aresta> arestas)

Testa se a árvore é geradora.

Parameters:

g -

arestas -

Returns:

True, se a árvore é árvore geradora, False, caso contrário.

caminhoMaisCurto

java.util.ArrayList<Aresta> caminhoMaisCurto(Grafo g,
                                             Vertice origem,
                                             Vertice destino)

Retorna (em ordem) as arestas que compoem o caminho mais curto entre um par de vértices.

Parameters:

g -

origem -

destino -

Returns:

As arestas (em ordem) do caminho mais curto.

custoDoCaminho

double custoDoCaminho(Grafo g,
                      java.util.ArrayList<Aresta> arestas,
                      Vertice origem,
                      Vertice destino)
                      throws java.lang.Exception

Dado um caminho, esta função calcula o custo do caminho.

Parameters:

arestas -

g -

origem -

destino -

Returns:

o custo da caminho.

Throws:

java.lang.Exception - Se a sequencia apresentada não é um caminho entre origem e destino.

ehCaminho

boolean ehCaminho(java.util.ArrayList<Aresta> arestas,
                  Vertice origem,
                  Vertice destino)

Verifica se a sequencia de arestas é caminho entre oriem e destino.

Parameters:

arestas -

origem -

destino -

Returns:

True, se é caminho. False, caso contrário.

arestasDeArvore

java.util.Collection<Aresta> arestasDeArvore(Grafo g)

Arestas de arvore.

Parameters:

g -

Returns:

As arestas de arvore do grafo g.

arestasDeRetorno

java.util.Collection<Aresta> arestasDeRetorno(Grafo g)

Arestas de retorno.

Parameters:

g -

Returns:

As arestas de retorno do grafo g.

arestasDeAvanco

java.util.Collection<Aresta> arestasDeAvanco(Grafo g)

Arestas de avanço.

Parameters:

g -

Returns:

As arestas de avanço do grafo g.

arestasDeCruzamento

java.util.Collection<Aresta> arestasDeCruzamento(Grafo g)

Arestas de cruzamento.

Parameters:

g -

Returns:

As arestas de cruzamento do grafo g.