GraphHopper.com | Forum | GitHub | Maps | Blog

Contraction time


#1

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);
}

g.freeze();

long time = System.currentTimeMillis();

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

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?


#2

Hi,

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.

Cheers,
Robin