Possible to use GraphHopper on a general, non-geographical graph?

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).

Powered by Discourse