Hi, I am working with a ~60 million node dataset that I would like to perform efficient, customizable-contraction-hierarchy shortest path algorithms on, but it has nothing to do with maps or geolocation. Is it possible to use some subset of the GraphHopper open source library to do this? If so, is there any documentation regarding this type of use? Thank you for your help.
It might be possible but everything is heavily tuned towards a roads graph. E.g. if your graph has a different average degree it might be that the default values for CH preparation are completely off and take ages to complete. And very likely other properties will cause more problems.
Have a look into the docs: graphhopper/technical.md at master · graphhopper/graphhopper · GitHub
and the low level API: graphhopper/low-level-api.md at master · graphhopper/graphhopper · GitHub
GraphHopper’s Contraction Hierarchies implementation does not rely on geolocations so you could just try. However, it is not customizable in the sense that if you need to change the edge weights you’ll have to re-generate the index data/run the preparation again. One thing you can do though is re-use the contraction order which will speed up the preparation but the resulting query speed will depend on how close the changed weights are to the original ones you used to determine the order.
The code you’ll need is roughly this:
@Test
void contractionHierarchiesSimple() {
BaseGraph graph = new BaseGraph.Builder(1).create();
graph.edge(0, 1).setDistance(100);
graph.edge(1, 2).setDistance(200);
// ... more edges here
graph.freeze();
Weighting weighting = new Weighting() {
@Override
public double getMinWeight(double distance) {
// not needed
return 0;
}
@Override
public boolean edgeHasNoAccess(EdgeIteratorState edgeState, boolean reverse) {
return false;
}
@Override
public double calcEdgeWeight(EdgeIteratorState edgeState, boolean reverse) {
return edgeState.getDistance();
}
@Override
public long calcEdgeMillis(EdgeIteratorState edgeState, boolean reverse) {
// not needed
return 0;
}
@Override
public double calcTurnWeight(int inEdge, int viaNode, int outEdge) {
return 0;
}
@Override
public long calcTurnMillis(int inEdge, int viaNode, int outEdge) {
return 0;
}
@Override
public boolean hasTurnCosts() {
return false;
}
@Override
public String getName() {
return "does not matter";
}
};
PrepareContractionHierarchies pch = PrepareContractionHierarchies.fromGraph(graph, CHConfig.nodeBased("whatever", weighting));
PrepareContractionHierarchies.Result result = pch.doWork();
CHRoutingAlgorithmFactory algoFactory = new CHRoutingAlgorithmFactory(new RoutingCHGraphImpl(graph, result.getCHStorage(), weighting));
BidirRoutingAlgorithm algo = algoFactory.createAlgo(new PMap());
Path path = algo.calcPath(0, 2);
assertEquals(300, path.getDistance());
}
Note that this is for a weighted, undirected graph (the weight is the ‘distance’ here).
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.