| Forum | GitHub | Maps | Blog

Contraction time


Sorry for a noob question, I just try to make sure I’m not doing anything stupid here.
So I’m currently testing a graph contraction performance, here’s my code:

GraphHopperStorage g = createGHStorage();
CHGraph lg = g.getGraph(CHGraph.class);

SecureRandom rand = new SecureRandom();
// A random graph of ~10000 vertexes and ~30000 edges

for (int i = 0 ; i < 30000 ; i++) {
    int node1 = rand.nextInt(10000);
    int node2 = rand.nextInt(10000);
    if (node1 == node2) continue;

    g.edge(node1, node2, 1 + rand.nextInt(20), false);


long time = System.currentTimeMillis();

// Contract the graph
PrepareContractionHierarchies prepare = new PrepareContractionHierarchies(dir, g, lg, weighting, tMode);

System.out.println("Contraction took: " + (System.currentTimeMillis() - time));

It takes about 20 minutes on my computer to get this done. Is this awfully long? If times like this are expected, is there a way to speed it up?



I can’t tell you if this is the expected time for a random graph to be honest. It seems quite long for just 30000 edges. Did you try to increase the Java Heap Space? Without checking, I would have said, that contracting the graph of Germany might take about 20 minutes on my computer.

In general, the contraction speed of GraphHopper is already pretty tuned. I don’t think that there are many obvious ways to further tune this. It might be possible to improve the speed by contracting in multiple threads, but this is not trivial.