Grafos em Java

L

lilcrazy

Power Member
Hey pessoal.

Eu estou a implementar uma aplicação do género de um grafo em Java.
A aplicação consiste na criação de companhias aéreas e respectivos percursos.

Por exemplo existem os seguintes comandos:
company:nomeDaCompanhia:velocidade -> cria um objecto do tipo companhia, atributos 2 parametros seguintes.

insert:nomeDaCompanhia:origem:destino:distancia -> se ainda não existir este percurso (e notar que as distancias teem de ser diferentes para origens e destinos iguais) insere-o

remove:nomeDaCompanhia:origem:destino -> se existir a companhia e a origem, remove o percurso

etc.

Para inserir percursos, eu tenho uma Hashtable que guarda objectos do tipo Companhia (key -> nome da companhia). Tenho outra Hashtable que guarda objectos do tipo Origem (key -> nome da cidade origem). Ao inserir percursos, vejo se ainda não existir essa origem na Hashtable, crio um objecto do tipo Destino e ligo a Origem ao destino. Ou seja a partir daqui são listas ligadas ordenadas alfabeticamente, ou seja, se inserirmos para a companhia TAP os seguintes percursos: Porto->Faro, Porto->Lisboa, Porto->Coimbra, ficaria na seguinte ordem

PORTO -> COIMBRA -> FARO -> LISBOA

Até aqui tudo bem...é de notar que podemos criar mais objectos do tipo Origem na Hashtable. Por exemplo, se inserirmos mais percursos...

PORTO -> COIMBRA -> FARO -> LISBOA

COIMBRA -> FARO -> LISBOA

FARO -> LISBOA -> PARIS

LISBOA -> FARO -> MADRID

MADRID -> PARIS

Agora estou a implementar um comando do tipo printByNumber, que percorre a partir duma origem várias cidades até encontrar a cidade destino passada como parametro (assim como a cidade origem). Se não encontrar o destino nunca, não imprime nada! Se encontrar, pode encontrá-lo de várias maneiras e podem ser necessários vários vôos. E aí tenho de no final ir comparando, se o numero de voos for maior que o percurso anterior, fica com o percurso anterior e imprime esse, pela ordem das cidades que passou. Se for menor, continua a procurar. Se não encontrar mais, imprime o último que encontrou, por ai em diante.

Exemplo do comando -> printByNumber:origem:destino

origem = porto, destino = paris

possibilidades: Porto->Faro->Paris
Porto->Lisboa->Madrid->Paris

Ficando a primeira opção, uma vez, que se realizam menor número de voos do Porto para Paris.

O problema está...como implemento isto? Percorrer todas as possibilidades? Já consegui este pedaço de código, mas qualquer coisa está mal, pois o percurso de Faro a Paris não é guardado :S

Alguma ajuda?
if(origens.containsKey(comandos[1].trim())){ //se a origem existir
Origem origem1 = ((Origem)origens.get(comandos[1].trim()));
Destino auxiliarP = origem1.primeiro;
//Destino aux = auxiliarP;
boolean existe = false;
boolean encontrou = false;
String outputActual = "";
String outputAnterior = outputActual;
int numVoosActual = 0;
int numVoosAnterior = numVoosActual;

//while(aux != null){
if(existeDestino(origem1, comandos[2].trim())){ //ve se é voo directo
numVoosActual++;
existe = true;
}else{ //se não for, entra num ciclo que vai da origem ate ao destino

while(auxiliarP != null){
if(origens.containsKey(auxiliarP.cidade)){ //se a origem existir
//System.out.println("Existem destinos a partir de " + auxiliarP.cidade);
Origem origem2 = ((Origem)origens.get(auxiliarP.cidade));
Destino auxiliarS = origem2.primeiro;
numVoosActual++;
outputActual = outputActual.concat(":" + auxiliarP.cidade);

if(existeDestino(origem2, comandos[2].trim())){
//System.out.println("Existem o percurso: " + auxiliarP.cidade + "-" + auxiliarS.cidade);
numVoosActual++;
existe = true;
break;
}else{
while(auxiliarS != null){
if(origens.containsKey(auxiliarS.cidade)){ //se a origem existir
numVoosActual++;
//System.out.println("Existem destinos a partir de " + auxiliarS.cidade);
Origem origem3 = ((Origem)origens.get(auxiliarS.cidade));
Destino auxiliarT = origem3.primeiro; //pode-se tirar

if(existeDestino(origem3, comandos[2].trim())){
//System.out.println("Existe percurso: " + auxiliarS.cidade + "-" + auxiliarT.cidade);
outputActual = outputActual.concat(":" + auxiliarS.cidade);
numVoosActual++;
existe = false;
if(auxiliarT.cidade.equals(comandos[2].trim())){
if(numVoosActual > numVoosAnterior){ //se o numero de voos actual for maior que o numero de voos calculado anteriormente sai do ciclo e escreve o que tem
encontrou = true;
System.out.print("printByNumber:" + comandos[1].trim() + outputActual + ":" + comandos[2].trim() + ":" + numVoosActual);
System.out.println();
}else{
numVoosActual = numVoosAnterior;
outputActual = outputAnterior;
}
}
}
}
auxiliarS = auxiliarS.proximo;
}
}
}

if(encontrou){
break;
}
else{
auxiliarP = auxiliarP.proximo;
System.out.println("PASSA PARA O PROXIMO DESTINO!");
numVoosAnterior = numVoosActual;
System.out.println("-" + numVoosAnterior + "-" + numVoosActual);
outputAnterior = outputActual;
numVoosActual = 0;
outputActual = "";
}
}
}
if(existe){
System.out.print("printByNumber:" + comandos[1].trim() + outputActual + ":" + comandos[2].trim() + ":" + numVoosActual);
System.out.println();
}
else{
System.out.print("printByNumber");
System.out.println();
}
//aux = aux.proximo;
//}
}
Clicar para expandir...


Ou alguma maneira mais fácil e menos confusa?

Obrigado ;-)
 
Pesquisa pelo algoritmo de Ford Fulkerson, e implementa em Java.

Ja fiz uma coisa parecida, mas em C++.
 
public static void busca(Origem verticeInicial, String cidadePartida, String cidadeAProcurar, int numVoosActual, String outputActual){
buscaEmProfundidade(verticeInicial, cidadePartida, cidadeAProcurar, numVoosActual, outputActual);
}

//método que, através da busca em profundidade (recursiva), procura todos os percursos possíveis a partir da origem passada como parâmetro
public static void buscaEmLargura(Origem verticeInicial, String cidadePartida, String cidadeChegada, int numVoosActual, String outputActual){
System.out.println("BUSCA...");
while(verticeInicial.primeiro != null){ //ciclo que visita desde o primeiro destino da origem até ao último
System.out.println("CICLO");
if(origens.containsKey(verticeInicial.primeiro.cidade)){ //se existem percursos a partir do último destino
System.out.println("|" + verticeInicial.cidade + "->" + verticeInicial.primeiro.cidade + "| " + numVoosActual++);
System.out.println("Existem destinos a partir de: " + verticeInicial.primeiro.cidade + " :)");
Origem adjacente = ((Origem)origens.get(verticeInicial.primeiro.cidade)); //vai buscar à hashtable origens o objecto adjacente, do tipo Origem, ligado aos vários destinos

buscaEmLargura(adjacente, cidadePartida, cidadeChegada, numVoosActual++, outputActual+":"+verticeInicial.primeiro.cidade); //pesquisa recursivamente os vários percursos possíveis

}else{ //se não existirem destinos a partir dessa origem imprime...
System.out.println("|" + verticeInicial.cidade + "->" + verticeInicial.primeiro.cidade + "| " + numVoosActual);
System.out.println("Não existem destinos a partir de: " + verticeInicial.primeiro.cidade + " :(");
}
if(verticeInicial.primeiro.cidade.equals(cidadeChegada)){ //se encontrar o destino final, passado como parâmetro, imprime a linha
System.out.println("printByNumber:" + cidadePartida + "" + outputActual + ":" + cidadeChegada + ":" + numVoosActual); //tudo certo, à excepção que imprime todos os percursos possíveis até à origem, e só queremos um!! método para comparar os dois últimos percursos possíveis e devolver o melhor (com número menor de vôos)??
}
verticeInicial.primeiro = verticeInicial.primeiro.proximo; //passa para o destino seguinte a analisar
numVoosActual = 1; //problema aqui! o objectivo é cada vez que chega à raiz inicializa a uma viagem...
}
/*O PROBLEMA AQUI É QUE QUANDO VEMOS TODOS OS PERCURSOS POSSÍVEIS A PARTIR DE UM VÉRTICE TEMOS DE ASSINALAR ESSE VÉRTICE COMO VISTO (visto = true; if(true) -> passa para o próximo vértice a verificar; else continua a procurar percursos a partir desse vértice e (visto = false)). Como não marco os vértices visitados, se for encontrado um destino que é origem e é o mesmo que a cabeça, ele entra em ciclo infinito e dá StackOverFlow!*/
}
Clicar para expandir...



Raio, nunca consigo colocar o código aqui identado para que toda a gente perceba! lool

O meu problema aqui é ir marcando os vértices, e depois ir verificando se o numVoos calculado no percurso anterior (isto caso tenha atingido o destino que se quer - passado como parametro) é maior ou menor. Se for menor entao guarda o menor, se for maior fica com o corrente (isto caso existam mais).

Nesta parte estou empancado. Alguma ajuda?

Obrigado pela disponibilidade ;-)
 
Isto não me parece ser um problema de Max Flow mas sim de Shortest Path com edges unitários.
Um Dijkstra ou um BFS (floodfill) resolvia o problema.
 
Um grafo tipo dijkstra era capaz de ser a melhor ideia, não sei é se seria bem implementável com as classes disponiveis na API, mas também ainda não investiguei a fundo. Só me lembro que precisei da noção de grafos num concurso de programação que tive.
 
Nao marques o vertice visitado, tendo em conta q e' um atributo do proprio vertice.

Usa um vector chamado visitados, em que cada numero corresponde a um vertice.
 
Alguma ajuda a implementar o algoritmo de Dijkstra?

É que procurei tanto mas a ideia ficou, só que implementar o código para o meu programa tá dificil...

Obrigado
 
No google encontrei isto:

1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2.
2. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
4. Let Si+1 = Si cup {ui+1}.
5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.

Tambem por la deve andar o codigo feito, mas acho q te faz bem faze-lo.
 
Inicie sessão ou registe-se para poder participar.
Back
Topo