Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I'am trying to utilize osm2po as java lib for calculation of distances matrix between some set of points (lat/lon) and for each pair of points I call the following method that code is based on sample provided at osm2po.de web-site:

public int getDistance(GeoPoint source, GeoPoint target) {
        int res = Integer.MAX_VALUE;
        int sourceId = graph.findClosestVertexId(source.getLatitude(), source.getLongitude(), 1);
        int targetId = graph.findClosestVertexId(target.getLatitude(), target.getLongitude(), 1);

        router.traverse(graph, sourceId, targetId, Float.MAX_VALUE, params);

        if (router.isVisited(targetId)) { // Found!
            int[] path = router.makePath(targetId);
            float distKm = 0.0f;

            for (int segmentId : path) {
                RoutingResultSegment rrs = graph.lookupSegment(segmentId);
                distKm = distKm + rrs.getKm();
            }

            res = (int)(distKm * 1000);
        }

        router.reset();
        return res;

But I noticed that it takes about 2-3 seconds per one point to calculate whole distance matrix (I have 10-25 points per matrix in average) that looks not too fast (30-60secs per matrix). Could someone advice what could be improved here - especially I am not sure in correct usage of reset() call - when actually it should be done? - it's not too much documentation on osm2po usage within java...
Also I would appreciate any performance tips to improve this code. One more guess I have is that findClosestVertexId() is expensive enough call and cashing its results for subsequent calls could improve the situation.

share|improve this question

3 Answers 3

up vote 2 down vote accepted
package de.cm.osm2po.test;

import java.io.File;
import java.util.Arrays;

import de.cm.osm2po.logging.Log;
import de.cm.osm2po.logging.Log2poConsoleWriter;
import de.cm.osm2po.model.LatLon;
import de.cm.osm2po.routing.Graph;
import de.cm.osm2po.routing.MultiTargetRouter;
import de.cm.osm2po.routing.PoiRouter;

public class MatrixDemo {

    // ###################### Demo Main ##############################

    public static void main(String[] args) {
        File graphFile = new File("D:/work/osm2po/hh/hh_2po.gph");

        MatrixDemo matrixDemo = new MatrixDemo(graphFile);
        int[] vertexIds = matrixDemo.findClosestVertexIds(
                new LatLon(53.5, 10.1),
                new LatLon(53.4, 10.0),
                new LatLon(53.5, 9.9));
        float[][] matrix = matrixDemo.createMatrix(vertexIds);
        matrixDemo.close();

        for (int i = 0; i < matrix.length; i++) {
            System.out.println(Arrays.toString(matrix[i]));
        }
    }

    // ##################### Intrinsic Clazz #########################

    private Graph graph;
    private MultiTargetRouter router;

    public MatrixDemo(File graphFile) {
        Log log = new Log(Log.LEVEL_DEBUG).addLogWriter(new Log2poConsoleWriter());
        graph = new Graph(graphFile, log, Graph.SUPPORT_LATLON);
        router = new PoiRouter();
    }

    public void close() {
        graph.close();
    }

    public int[] findClosestVertexIds(LatLon... latLons) {
        int[] vertexIds = new int[latLons.length];
        for (int i = 0; i < latLons.length; i++) {
            vertexIds[i] = graph.findClosestVertexId(
                    (float)latLons[i].getLat(), (float)latLons[i].getLon());
        }
        return vertexIds;
    }

    public float[][] createMatrix(int... vertexIds) {
        int n = vertexIds.length;
        int[] cpVertexIds = Arrays.copyOf(vertexIds, n);
        float[][] matrix = new float[n][n];

        for (int y = 0; y < n; y++) {

            int swap = cpVertexIds[0];
            cpVertexIds[0] = cpVertexIds[y];
            cpVertexIds[y] = swap;

            int sourceId = cpVertexIds[0];
            int[] targetIds = Arrays.copyOfRange(cpVertexIds, 1, n -1);

            router.reset();
            router.traverse(graph, sourceId, targetIds, Float.MAX_VALUE, null);

            for (int z = 0; z < n; z++) {
                int x = z + y;
                if (x >= n) x -= n;

                matrix[y][x] = Float.MAX_VALUE;
                if (router.isVisited(vertexIds[x])) {
                    matrix[y][x] = router.getCost(vertexIds[x]);  
                }
            }

        }

        return matrix;
    }

}

If you have big data but only need the matrix for a small region, you can improve the performance by setting the MaxCost-Parameter to sth. smaller than Float.MAXVALUE. Tipp: Mostly it is sufficient to call a full traversal using MaxValue twice or thrice. After these loops the longest path should be found and you can replace the MaxValue with the cost * <some buffer>

router.traverse(graph, sourceId, targetIds, longestPathCost * 1.5, null);

The last parameter (null) are optional additional properties.

Properties params = new Properties();
params.setProperty("findShortestPath", "true");
router.traverse(graph, sourceId, targetIds, Float.MAX_VALUE, params);
share|improve this answer
    
Carsten, than you for the sample! Quick question: as I understand router.getCost() actually returns travel time but I need distance as well but do not see corresponding method in PoiRouter class - how distances could be get? –  Andrew Apr 8 '13 at 9:25
1  
Indeed, the above example only calculates the matrix. If you need full resulting paths with all information insert int[] path=router.makePath(vertexIds[x]) inside the isVisited()-IF-Block or route over your resulting VertexIds in standard fashion. –  Carsten Apr 8 '13 at 10:06
1  
makePath() returns an array of pointer to the underlying Edge-List (edgeIdx's). If you only need the length, call Graph.calcPathLength(int[] path) after having found your tour. If you need more infos, call lookupSegment(int edgeIdx) for each index in the int[] path-Array. –  Carsten Apr 8 '13 at 10:18
    
ok, thanks. And one more clarification. Could uncommenting of any of the following options from osm2po.config speedup execution of the code above: #graph.support.segments = true #graph.support.edgeflags = true #graph.support.reverse = true #graph.support.raster = true #graph.support.raster.e = true #graph.support.raster.v = true #graph.support.barriers = true #graph.support.extensions = true I guess that two first could be useful here - am I right? –  Andrew Apr 22 '13 at 9:52
1  
The SUPPORT-Parameters enrich a graph object at runtime (via Constructor). A stupid Graph would only know its vertexes and edges which is sufficient if you knew the IDs. e.g. from pgRouting. In order to find closestVertexes you'll need the coordinates. Here it is necessary to load them into memory. This is triggered by the SUPPORT_LATLON const. You'll recognize other SUPPORT-options. Each loads or creates additional data for the Graph at construction time. Another important one is SUPPORT_SEGMENTS which loads all streetnames and geometries into RAM. –  Carsten Apr 23 '13 at 17:10

Indeed, you can improve the performance a lot. What you are doing here in order to fetch a distance between two points is to call the entire routing batch for each pair.

Usually a routing needs three steps:

  1. Finding the nearest Source- and TargetVertex on the network.
  2. Calculating the shortest path between them
  3. Reconstructing all path informations (geometries, street names, etc.)

Assuming you have a matrix of 10x10, why are you calling findClosestVertexId() 200 times? You are going to calcule an adjaceny/cost-matrix. This can be done with a trick. To get a first idea of what I'm talking about read my answer/comment on this thread: Unreachable vertex. Finally step 3 (lookupSegment) is not needed at all.

share|improve this answer
    
thanks for the answer, I do understand the idea but I do not know how it should be properly implemented in the code as the only documentation I found on the lib is a code sample on osm2po.de web-site (also libs source code is closed). I.e. the following questions stay for me open: how to run Dijkstra algo once and then get distances to set of points? how to get distance information without lookupSegment() call? What is a proper sequence of router object calls? What implementation of router is better to use here? (at the moment I use DefaultRouter) –  Andrew Apr 5 '13 at 10:29
    
You can use the DefaultRouter for it. But I've implemented a special one for exactly this purpose. –  Carsten Apr 5 '13 at 12:22
    
Carsten, in the release 4.7.7 of osm2po I see in release notes that there is new MlgRouter (MultiLevelGridRouter) "which is an at least five times faster DefaultRouter". Could you please clarify why it's so fast and whether it could be used here? (what is the main idea of Multi Level Grid?) –  Andrew Apr 19 '13 at 8:37
    
Can you move this question to a new thread? It has nothing to do with creating a matrix. –  Carsten Apr 19 '13 at 17:31
    
ok, agree - I just posted a new question on this - gis.stackexchange.com/questions/58735/… –  Andrew Apr 22 '13 at 7:03

!!! IMPORTANT !!!

The new 4.8.8 API provides a Default-MatrixCreator which exactly does the steps explained above. So there is no need to overwrite anything anymore.

share|improve this answer
    
It would be better if you could edit your answer instead of posting a new one. –  underdark Nov 24 '13 at 10:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.