Home
O modelo de grafo é representado por 3 interfaces no Graphast:
Node
Edge
Observe que as arestas não referenciam os objetos nós(vértices) que a formam, mas sim os id destes nós
Graph
As interfaces são base para implementações de modelos, no entanto, o Graphast-core possui suas próprias implementações (GraphImpl, EdgeImpl e NodeImpl)
Graphast oferece dois tipos de algoritmo: menor caminho(Dijkstra e A Star) e vizinhos mais próximos(KNN)
Os serviços de menor caminho estendem a classe AbstractShortestPathService, que por sua vez implementa a interface ShortestPathService. Estes serviços retornam um objeto Path representando o menor caminho
Os serviços de vizinhos mais próximos estendem a classe AbstractKNNService
Os serviços Dijkstra estendem a classe abstrata Dijkstra
A classe Dijkstra implementa o algoritmo de Dijkstra para menor caminho entre dois nós do grafo. O método shortestPath recebe um Node fonte, um Node destino, uma Date e retorna um Path. Existem mais três assinaturas para este método, em algumas os parâmetros fonte e destino podem ser do tipo long ou o parâmetro Date deixa de ser necessário
É importante atentar para o método abstrato expandVertex, ele é usado em shortestPath. A implementação deste método determinará qual variação de Dijkstra será usada. O Graphast oferece duas opções: peso constante e função linear
Usado na classe DijkstraConstantWeight, implementa o método expandVertex baseado nas distâncias do grafo
Usado na classe DijkstraLinearFunction, implementa o método expandVertex baseado no vetor de tempos do grafo
Os serviços A Star estendem a classe abstrata AStar
A classe AStar implementa o algoritmo A-Star para menor caminho entre dois pontos no grafo. O método shortestPath recebe um Node fonte, um Node destino, uma Date e retorna um Path. Este método possui mais três variações de assinatura, em algumas os parâmetros fonte e destino podem ser do tipo long ou o parâmetro Date deixa de ser necessário
É importante atentar para o método abstrato expandVertex, ele é usado em shortestPath. A implementação deste método determinará qual variação de A-Star será usada. O Graphast oferece duas opções: peso constante e função linear
Usado na classe AStarConstantWeight, implementa o método expandVertex baseado nas distâncias do grafo
Usado na classe AStarLinearFunction, implementa o método expandVertex baseado no vetor de tempos do grafo
A classe AbstractKNNService implementa métodos auxiliáres para o KNN e cabe a classe concreta implementar o método search para realizar a busca de vizinhos mais próximos
Usado na classe KNNSearch, implementa o método search com base apenas nas distâncias do grafo e retorna uma lista de NearestNeighbor
Usado na classe KNNTCSearch, implementa o método search com base no vetor de tempos do grafo e retorna uma lista de NearestNeighborTC
Este exemplo mostra como usar o Graphast para instanciar um grafo a partir de um mapa e realizar uma consulta de menor caminho
- O mapa deve ser um arquivo de extensão .osm.pbf. O mapa de Mônaco será usado neste exemplo
- O grafo é instanciado pela classe OSMImporterImpl passando como parâmetros uma String do local do arquivo mapa e uma String do local onde o grafo será arquivado
- Se houver pontos de interesse no grafo, é possível importá-los usando a classe POIImporter e seu método importerPoILists passando como parâmetros o grafo e o arquivo contendo os pontos de interesse (no formato .csv)
- Para gerar os custos usaremos a classe CostGenerator e seu método generateAllSyntheticEdgesCosts passando o grafo como parâmetro
O código abaixo ilustra os passos:
public class GenerateGraphExample {
public GraphBounds monacoExample() {
//pegando o caminho para o mapa (.osm.pbf)
String osmFile = this.getClass().getResource("/monaco-150112.osm.pbf").getPath();
//apontando o diretório de armazenamento do grafo
String graphastMonacoDir = Configuration.USER_HOME + "/graphast/test/monaco";
/*a clase OSMImporter é instanciada com os diretorios do mapa e de onde queremos guardar,
o método .execute() transforma esse mapa em um GraphBounds*/
GraphBounds graph = new OSMImporterImpl(osmFile, graphastMonacoDir).execute();
/*caso queira importar pontos de interesse para o grafo, podemos chamar o método abaixo passando
o grafo e o diretório do arquivo contendo os pontos de interesse(o arquivo precisa ser .scv)*/
POIImporter.importPoIList(graph, "src/main/resources/monaco-latest.csv");
/*para gerar os custos do grafo, basta utilizar o método abaixo passando o grafo como parâmetro*/
CostGenerator.generateAllSyntheticEdgesCosts(graph);
return graph;
}
}Com o método para gerar um grafo de Monaco iremos, neste exemplo, instanciá-lo e realizar uma busca por menor caminho entre dois pontos utilizando o método de Dijkstra
- Instanciar o grafo
- Instanciar um serviço, neste caso, o DijkstraConstantWeight, que por sua vez estende AbstractShortestPathService
- Escolher dois pontos, dando suas latitude e longitudes. Gerar um Path com o método shortestPath do serviço passando os dois pontos como parâmetro
O código abaixo ilustra os passos:
public class QueryExample {
public static void main(String[] agrs) {
/*instanciando o grafo pelo método criando na classe GenerateGraphExample
criada anteriormente no exemplo*/
Graph graph = new GenerateGraphExample().monacoExample();
/*instanciando um serviço, no caso de menor caminho, mais precisamente o Dijkstra de pesos constantes.
basta passar o grafo como parâmetro para omstanciar o serviço*/
AbstractShortestPathService service = new DijkstraConstantWeight(graph);
/*nesta parte são escolhidos dois nós do grafo de acordo com as coordenadas passadas,
então chama-se o método para encontrar o menor caminho entre os dois*/
Long source = graph.getNodeId(43.740174,7.424376);
Long target = graph.getNodeId(43.735554,7.416147);
Path shortestPath = service.shortestPath(source, target);
}
}