Does this produce a contraction hierarchy?

[r-barnes]

I've been using RoutingKit to make queryable contraction hierarchies, but am running into a situation where preprocessing on one of the road networks I'm using is taking a long (many hours) time. It looks like this repo might reduce preprocessing times, but it's unclear from the description how to generate a queryable contraction hierarchy using it.

[larsgottesbueren]

Hi,

take a look at query.cpp for how to get a customizable contraction hierarchy (CCH) with RoutingKit, and inertialflowcutter_order.py for how to do the preprocessing. If you're looking for CCHs, our preprocessing should be faster than that of RoutingKit, since our code is parallel. Also queries and customization should be faster since the elimination ordering is better. If you're looking for plain old CHs (no quick customization to changing edge weights), I'd be interested in the scale of the road networks you operate on. Continental size should take around a few minutes.

Best, Lars

[r-barnes]

Thanks, Lars! I foolishly forgot that geographic information is required to use this. The graph I'm operating on is a few levels abstracted from actual geography, so I probably won't be able to leverage your good work. The graph that's proving problematic for me has 70M edges with 364k vertices. The same computation worked fine for two slightly smaller graphs with 27M/638k and 17M/276k.

[michitux]

Doesn't RoutingKit also depend on geographic information for CCHs? I think RoutingKit should suffer even more from wrong coordinates than InertialFlowCutter. We also found sometimes that seemingly "simpler" graphs that are the result of, e.g., simple contraction steps to eliminate trivial substructures lead to worse cuts than the original graph not because the good cuts do not exist anymore but because they are harder to find. Your graph seems denser than typical road networks. Have you checked if maybe it also simply has worse cuts, e.g., by computing balanced cuts on the original graph? These algorithms (FlowCutter, InertialFlow, InertialFlowCutter) all have a running time that depends linearly on the cut size. Note that FlowCutter does not depend on geographic information. While it is slower on road networks, it could produce better cuts and thus still be faster on your graph.

[r-barnes]

RoutingKit doesn't, to my knowledge, require geographic information for constructing CCHs.

I took you up on your suggestion to try FlowCutter (because it doesn't require geographic information) and it seems to have worked! Computation on my graph completed in 25.5 hours with these output statistics:

running time : 91666692047musec
       super_graph_upward_arc_count : 41191425
             upper tree width bound : 41
            elimination tree height : 61
     average elimination tree depth : 19.2964
       maximum arcs in search space : 1488
       average arcs in search space : 216.286
 number of triangles in super graph : 12483879

The running time is probably shorter because I put the process to sleep for 7 hours at one point, so if you calculate wall-time from a simple time differencing scheme, rather than a process clock, it won't have accounted for that.

Meanwhile, RoutingKit has been running for 85 hours (3.5 days).

I'll test the output shortly.