There are many route-blocking barriers like gate, lift_gate, cycle_barrier or bollard in the OSM data. Graphhopper does not evaluate them. This will lead to rouiting through the obstacles.

Most of these barriers are tagged on nodes. These nodes are always pillar nodes.

What would be the proper way to introduce such blocks into the graph?

1. unjoin the way at the blocked node and add it as two disconnected ways?
2. split the way in 3 and replace the blocked node with a very short edge which is marked with neither FORWARD nor BACKWARD? (Is it possible to block an edge this way?)
3. Something completely different is required?

If it works, I would suggest 2. as the block can be different for foot, bike and car.

See http://srtm.csi.cgiar.org/, http://wiki.openstreetmap.org/wiki/SRTM and http://ned.usgs.gov/

Also the ele tag from OSM http://wiki.openstreetmap.org/wiki/Key:ele

Discussion: http://lists.openstreetmap.org/pipermail/graphhopper/2013-May/000118.html and http://lists.openstreetmap.org/pipermail/graphhopper/2013-May/000156.html

I initialize a graph

GraphStorage graph = new GraphStorage(new RAMDirectory());
graph.createNew(10);

Now regardless of whether I add the directed edge 3 --> 2

graph.edge(3, 2, 1, false);

or the directed edge 2 --> 3

graph.edge(2, 3, 1, false);

if I print the edges with the following method inserted in the GraphStorage class

public void printEdges() {
        EdgeWriteIterator iter = this.getAllEdges();
        while (iter.next()) {
            System.out.println(
                    "Start node: " + iter.fromNode()
                    + ", End node: " + iter.node()
                    + ", Distance: " + iter.distance()
                    + ", Both directions: " 
                    + CarStreetType.isBoth(iter.flags()));
        }
    }

then the output is always

Start node: 2, End node: 3, Distance: 1.0, Both directions: false

For my application, if I add the edge using

graph.edge(3, 2, 1, false);

I need the output to be

Start node: 3, End node: 2, Distance: 1.0, Both directions: false

suggested by @orangeman:

Instead of the visited boolean array/set we could try to introduce a boolean flag in EdgeEntry and see if this is faster (if we avoid the visit.contains check + rely entirely on the map.get check)

I tried to build the route by using .osm file but i am getting this error
gondal@gondal-PC:~/Downloads/graphhopper-master$ ./run.sh pakistan.osm

using java 1.7.0_15 from

using existing osm file pakistan.osm

now building graphhopper jar: target/graphhopper-0.1-SNAPSHOT-jar-with-dependencies.jar

using maven at /usr/local/apache-maven-3.0.5

compilation failed

gondal@gondal-PC:~/Downloads/graphhopper-master$

The result returned by astar is not optimal for fastest calc problems ...

GraphStorage graph = new GraphBuilder().create();
final VehicleEncoder enc = AcceptWay.parse("CAR").firstEncoder();
graph.setNode(1, 1, 3);
graph.setNode(2, 2, 3);
graph.setNode(3, 3, 3);
graph.edge(2,3, 100, enc.flags(50, true));
graph.edge(1,2, 100, enc.flags(50, true));
graph.edge(1,3, 800, enc.flags(50, false));
AlgorithmPreparation op= new NoOpAlgorithmPreparation() {
@OverRide public RoutingAlgorithm createAlgo() {
return new AStar(_graph, enc).type(new FastestCalc(enc));
}
}.graph(graph);
Path path = op.createAlgo().calcPath(1,3);

The optimal solution is 1->2->3 and it is correctly given by Dijkstra, DijkstraBidirection and AStarBidirection; the AStar algorithm instead returns 1->3.

1. can u kindly guide me in executing this project .
   2)I want to use my input file for executing this project .
2. I need to apply CH on my input file

how can I create a routing map in windows?

Sorting LevelGraph after preparation is currently not supported. When copying it does not transfer the skippedEdges and levels for nodes. Also see #9. Especially for Android this could speed up queries!

External nominatim is slow, so we should either use an own instance of Nominatim, or switch to a complete different/custom solution like ElasticSearch or Lucene: https://github.com/ncolomer/elasticsearch-osmosis-plugin/

Further things we would solve with a custom solution

• location suggestions while typing
• quality of nominatim is sometimes bad
• a mobile version for offline address search!

see this for a simple quality check

i have problem with import the OverlayList and PolygonalChain the import cannot be resolved

I used the OSMReader (osmreader.graph=sg-sh osmreader.osm=malaysia_singapore_brunei.osm osmreader.size=5000000 osmreader.dataaccess=mmap) to create a graph for android.
But if I want to use this graph with GraphHopper I'm getting following error:
"D/RouteCalculation(2119): An error happend while creating graph: Cannot load the graph - it wasn't create via com.graphhopper.storage.LevelGraphStorage! sdcard/graphhopper/singapore-gh/"

hppc looks fast, is 2 times smaller and is apache licensed. so we should try out if speed is the same after replacing it. test:

• preparation of contraction
• routing speed for CH
• routing speed for normal algorithms. as more nodes are visited => collection lib needs to be more efficient

Related to #562

I just found out that there is no support of the access-property of ways. At least the CarFlagEncoder should pay attention to ways which have the property access=no|private|agricultural|forestry and should restrict/avoid routing over such ways.
more details here: http://wiki.openstreetmap.org/wiki/Key:access

Example: Shortest way from (13.481249,52.538691) to (13.471243,52.538893). There are several ways trough "Sportforum Hohenschönhausen" which are marked as private but which are taken into the shortest path.
MapQuest and OSRM do not route over those ways, but OpenRouteService also seems not to be able to handle this property.

Just started playing with graphhopper. I ran run.sh with the ui argument, on some data in the US, and this bit of code in MiniGraphUI.java

                    if (lat2 <= 0 || lon2 <= 0)
                        logger.info("ERROR " + nodeId + " " + iter.distance() + " " + lat2 + "," + lon2);

causes thousands of errors to be sent to the console. Should it be removed?

See http://wiki.openstreetmap.org/wiki/Import/Software#Negative_IDs

Windows does not allow to rename an open file or change the length of an open file. We need to fix this as e.g. for the memory mapped we do raFile.setLength without closing it.

And we should not rename the file without closing it in the Directory implementation.

1. can u kindly guide me in executing this project .
   2)I want to use my input file for executing this project .
2. I need to apply CH on my input file

In my use of GraphHopper for network analysis, I keep finding it necessary to obtain the set of nodes, often in order to iterate over them. It would be useful to me to have the following method available for any GraphHopper graph.

    /**
     * Returns a {@link TIntHashSet} of the nodes of this graph.
     *
     * @return The set of nodes of this graph.
     */
    protected TIntHashSet nodeSet() {
        // Initialize the Set.
        TIntHashSet nodeSet = new TIntHashSet();
        // Get all the edges.
        EdgeIterator iter = graph.getAllEdges();
        // Add each source and destination node to the set.
        while (iter.next()) {
            nodeSet.add(iter.baseNode());
            nodeSet.add(iter.node());
        }
        return nodeSet;
    }

Add the capability to calculate routes based on a current understanding of road speeds based on live traffic conditions. This would need to include the capability to initialize the graph with known speeds (attained via some data source or via estimate) and then update it later based on changing conditions. The key intentions being that when major conditions exist and the road speeds drop to near zero, that different routes are selected, and in all cases that realistic time estimates are provided for the route based current conditions.

At the moment the lookup of node ids via gps coordinates has the limitation that it would require lots of memory for world wide coverage as it is a quadtree of depth one (simple array), or if less memory is used for the index the precision is suboptimal.

Different requirements makes the new Location2NodesNtree a challenge:

1. should be precise and robust, i.e. should fetch exact matches as well as not so close nodes
2. should work for edges close to the query point, not only for nodes => use bresenham
3. should be fast to create
4. should work world wide => depth of the quadtree has to be bigger than 1
5. very memory efficient, e.g. do not store lat,lon instead use a graph-traversal as post-processing step to get the lat,lon for distance comparison. And remove nodes from an quadtree entry if the nodes' network (within the borders) is already represented from a different node. And the quadtree depth shouldn't be that big
6. querying should be fast => quadtree traversal and post processing should be fast
7. should work on Android and can be loaded from disc => store into a DataAccess (but one could use an in-memory quadtree with normal Java-references to construct such an on-disc index)
8. support to accept only edges/nodes for a specific vehicle
9. support LevelGraph -> do not index shortcuts + while searching do not include shortcuts for distance check - only for traversal. Also avoid problems if high-level nodes are disconnect from its lower-level nodes!

In line 82 and 95 you refer to egde, not edge.

I noticed this because the edge file generated by osmreader has a wrong name

• add a new DataAccess to GraphStorage. But you'll need to store UTF strings in it - so you'll probably change the underlying int access to a byte access (either a new subclass or more complicated but cleaner completely change the DataAccess interface to byte access). Also DataAccess should be accessed with byte offset not - as it is currently done - via integer offset. See MMapDataaccess (and not RAMDataAccess)
• then - while import via OSMReader - you'll need to memorize the names associated with an edge. E.g. add something like name(nameFromOSM) to the EdgeIterator interface.
• Finally in path create a method which returns all names of the edges (similar like the pointList is created), but add a name only if it changes from edge to edge. Additionally you'll need to calculate the angle between the streets and add instructions.
• The byte array should be compressed before stored. See com.graphhopper.coll.CompressedArray.compress

Later on: prepare to be used from address lookup as well #16

I am from pakistan. so i want to build routes for pakistan.osm. So what changes i have to make to achieve this. Thanks

Hi,

It isn't possible to switch to the foot encoder. There are two issues, the first is from the web service, the value passed in the http request doesn't get passed through. I didn't track this one down because I won't be using the web service for my application.

The next issue is that there are so many places where the vehicle/encoder could be specified. Firstly I specified it on the request:

VehicleEncoder algoVehicle = new FootFlagEncoder();
.
.
.
GHResponse rsp = hopper.route(new GHRequest(start, end).
                    vehicle(algoVehicle).type(algoType).
                    algorithm(algoStr).
                    putHint("douglas.minprecision", minPathPrecision));

and before the load:

hopper.forServer();
hopper.acceptWay().car(false).bike(false).foot(true);
hopper.load(osmFile);

This still resulted in car like times being calculated for the route...

I then specified it in the route method:

if (chUsage) {
            prepare.graph(graph);
            ((PrepareContractionHierarchies) prepare).vehicle(request.vehicle());
            if (request.algorithm().equals("dijkstrabi"))
                algo = prepare.createAlgo();

At this point I can see that the correct encoder arrives in the Path instance (where the time gets calculated), but the distance then evaluates to 0, and therefore so does the time. At which point I decided to discuss this with you.

There seems to be a few concepts mixed, first there is acceptWay, then there is encoder, then there is vehicle. They seem to be used semi interchangeably. My suggestion is to use one, and then stick with it.

Then it needs to be clear at which point in time such a setting should be supplied by the API user. Is it at load time? In which case I would assume from this that it effect the graph gen/load/contraction in some way (which doesn't seem to be the case from the code). Or is it at request time, in which case the value needs to be taken into account during the route request.

Part of the problem also seems to the preparation abstraction which creates the algorithm instances, because it is also created in different ways, and so the encoder sometimes doesn't get passed along, or does in a way that is hidden by the preparation interface (in the case of the PrepareContractionHierarchies) .

So, like I said, when I got to this many variables I decided to log an issue before I make a mess of your code or having to fork it away completely, either of which is obviously bad.

I'm trying to use the demo app, i downloaded my own osm file, i used the run.sh script to create the graph (it ran with the ui), i also created the .map file from the same osm file with osmosis and writer plugin. I putted the myosm-gh folder (with .map of course) in /sdcard/graphhopper/maps/ , when i try to use this map a toast appears with the following message: "An error happend while creating graph: Couldn't load load storage at /mnt/sdcard/graphhopper/maps/myosm-gh. ". I'm very confused because when i tried for first time with the berlin.ghz default file it worked fine!. I saw that the content of my gh folder is different from the folder berlin-gh which worked ... , my folder contains 4 files :
edges, geometry, nodes, spatialNIndex.
the berlin default folder contains:
egdes (not edges is it normal? !), geometry, nodes, loc2idIndex
i don't understand why the run script give me different files ... please i really need help ! thanks !

The OSM Reader is ignoring multiple taggings allowing ways like bicycle=designated, bicycle=official etc. It is also ignoring motorroads which are prohibited to pedestrians and cyclists.

For details, see attached picture.

The green flag is totally elsewhere.

At the moment the routing start and end point can be only on a node. We need to extend the algorithm and the querying to allow arbitrary GPS coordinates on an edge (the road) too.

• depends on #17
• extend the algorithm to allow two multiple start nodes (start(node), end(someCondition) and default is end(PointCondition(endNode))?)
• calculate the shortest path from the GPS coordinate to one of the start nodes
• do the same for the end point

I am integrating a PBF reader into the OSM parsing. This will likely be much faster than XML parsing and should need less memory/gcs due to fewer string operations.

As a side effect, the PBF reader will be able to use multiple threads.

Several of the links on the wiki page are broken. Thanks!

There should be a graph implementation which is disc based to avoid loading the full graph into memory.

Additionally there should be a memory bound A* implementation like http://en.wikipedia.org/wiki/SMA* to reduce memory consumption while executing the algorithm. Or CH could help here too.

I'm having trouble digesting a cloudmade OSM download of Berlin.

http://downloads.cloudmade.com/europe/western_europe/germany/berlin#downloads_breadcrumbs

Exception in thread "main" java.lang.AssertionError: Conversation pillarNode to towerNode already happended!? osmId:99128942 pillarIndex:13589

i tried to build graph using pakistan-latest.osm downloaded from http://download.geofabrik.de/asia/pakistan-latest.osm.bz2 i have installed maven. but i got error

C:\Users\Awais\graphhopper>run.sh pakistan-latest.osm ui
Welcome to Git (version 1.8.1.2-preview20130201)

Run 'git help git' to display the help index.
Run 'git help ' to display help for specific commands.

using java from C:\Program Files\Java\jdk1.7.0

using existing osm file pakistan-latest.osm

existing jar found target/graphhopper-0.1-SNAPSHOT-jar-with-dependencies.jar

now running com.graphhopper.ui.MiniGraphUI. algo=ui. JAVA_OPTS=-XX:PermSize=3

0m -XX:MaxPermSize=30m -Xmx1000m -Xms1000m
C:\Users\Awais\graphhopper\run.sh: line 124: C:\Program: No such file or directo
ry

kindly help me how can i fix this.

Currently the filtering for routable ways and the handling of more detailed properties is mixed in AcceptWays. Also, the code is executed twice, during both passes. This will become worse as the parsing becomes more detailed.

Suggestion:

• seperate filtering and property analysis in two methods
• run filtering only in pass1
• run property analysis only in pass2
• store the result of filtering from pass1 and re-use it in pass2

The result of the filtering should be be stored per way with one bit for each allowed mode of travel and re-used in pass 2 to skip the redundant filtering. This would speed up parsing on expense of memory. (optional switch?)

At least we should remove String.isEmpty from graphhopper

I want to use this project to generate contraction hireachy alone ..can u kindly tell me the steps in detail ?

OSM uses oneway=-1 for oneways that run against the natural direction of the way for some reason. (>120000 uses). Graphhopper does not evaluate this type of oneway.

This should be easily fixable by transposing it into a BACKWARD flag if I understood the flags correctly.

If you look into http://graphhopper.com/maps/?point=47.100541,17.932842&point=47.102981,17.931297 the destination is close to the way but matches the other more western node.

Improve new index to close #17

Hello,

I am currently writing a plugin for the open-source Geographic Information System (GIS) OrbisGIS called GDMS-topology consisting of several graph traversal tools and network analysis measures (e.g., closeness and betweenness centrality) for use on transportation networks. The issue is that these centrality measures require the calculation of all shortest paths in the network, and depending on the network, this calculation can take a very long time.

I have tested the NetworkAnalyzer plugin for Cytoscape on Nantes (Métropole), France using a graph produced from the IGN's BD TOPO route data. The graph has about 180 000 nodes and 235 000 edges, and the calculation has been running for almost a week on a personal computer. To try to cut down on this calculation time, I have become interested in contraction hiearchies. I looked for a Java implementation and I found GraphHopper.

I originally tried using JGraphT-SNA, a Java library based on JGraphT where these centrality measures and many other social network analysis algorithms are implemented. I used JGraphT-SNA to calculate closeness centrality on Nantes, but the calculation was about 7 times slower than NetworkAnalyzer. I'm hoping that a GraphHopper-based (and more specifically, a contraction hierarchies-based) implementation of these centrality measures will be much quicker.

For this reason, I have a few questions:

1. Though GraphHopper was designed for use with OSM data, I would like to use it on graphs constructed in OrbisGIS. A graph in OrbisGIS consists of a table of nodes and a table of edges listing start nodes and end nodes. Do you think it will be relatively easy to make the connection between an OrbisGIS graph and GraphHopper? I would be possible to supply the tables in .csv format, for example. I'm looking into LevelGraphStorage.
2. I was also wondering if you could explain the format GraphHopper uses to store the graph. GraphHopper seems to produce three files: edges, loc2idIndex and nodes. I would be particularly interested in the case where we calculate the contraction hierarchies, make some updates to the graph (delete a road, for example), and recalculate the contraction hiearchies. Is it necessary to start over, or can the contraction hierarchies be updated in an efficient manner?
3. What heuristics are used to establish the node order necessary for calculating the contraction hierarchies?
4. Which weight is used in determining the shortest path? (Only distance?) Is it possible to use different weights?

Thank you for your time and help!

See here.

An IllegalStateException is thrown every time I try to calculate a path more than once because I can't call the clear() method since it no longer exists.

Refactor AcceptWay to use a dynamic List of Encoders instead of a hardcoded set. This would allow for easily adding new evaluation sets for trucks, horses, mtb etc. (up to 4 because of the flag limitation)

Also seperate the logic whether a way is allowed from the property handling to speed up the first parsing run in the 2pass reader.

Hello, I'm trying to follow the instructions on the Usage page of your wiki.

If I try

./run.sh unterfranken.osm

or

./run.sh germany.osm

the script pauses at the following output:

using java 1.7.0_09 from 
No OSM file found or specified. Grabbing it from internet. Press CTRL+C if you do not have enough disc space or you don't want to download several MB

I press enter, and the file seems to be saved:

2012-12-04 15:19:30 (124 MB/s) - `unterfranken.osm.bz2' saved [4505/4505]

But I then encounter some exceptions:

Exception in thread "main" java.lang.IllegalStateException: Your specified OSM file does not exist:unterfranken.osm

and

Exception in thread "main" java.lang.IllegalArgumentException: Graph not found and no OSM xml provided.

See the full output below.*

If I try running the script on an osm I download from the internet, the graph is built just fine. But if I rerun the script, the tests are performed, but the UI never pops up. I would love to see the UI!

Thanks!

*Output:

$ ./run.sh unterfranken.osm
using java 1.7.0_09 from 
No OSM file found or specified. Grabbing it from internet. Press CTRL+C if you do not have enough disc space or you don't want to download several MB

rm: cannot remove `unterfranken.osm.bz2': No such file or directory
## now downloading OSM file from http://download.geofabrik.de/osm/europe/germany/bayern/unterfranken.osm.bz2
--2012-12-04 15:19:30--  http://download.geofabrik.de/osm/europe/germany/bayern/unterfranken.osm.bz2
Resolving download.geofabrik.de (download.geofabrik.de)... 46.4.99.10
Connecting to download.geofabrik.de (download.geofabrik.de)|46.4.99.10|:80... connected.
HTTP request sent, awaiting response... 302 Found
Location: http://download.geofabrik.de/ [following]
--2012-12-04 15:19:30--  http://download.geofabrik.de/
Reusing existing connection to download.geofabrik.de:80.
HTTP request sent, awaiting response... 200 OK
Length: 4505 (4,4K) [text/html]
Saving to: `unterfranken.osm.bz2'

100%[========================================================================================>] 4 505       --.-K/s   in 0s      

2012-12-04 15:19:30 (124 MB/s) - `unterfranken.osm.bz2' saved [4505/4505]

## extracting unterfranken.osm.bz2
bzip2: unterfranken.osm.bz2 is not a bzip2 file.
## existing jar found target/graphhopper-0.1-SNAPSHOT-jar-with-dependencies.jar
## now creating graph unterfranken-gh (folder) from unterfranken.osm (file),  JAVA_OPTS=-XX:PermSize=20m -XX:MaxPermSize=20m -Xmx500m -Xms500m
## HINT: put the osm on an external device to speed up import time
2012-12-04 15:19:31,098 [main] INFO  com.graphhopper.reader.OSMReader - using GraphStorage|RAMDirectory|1, memory:totalMB:479, usedMB:5
Exception in thread "main" java.lang.IllegalStateException: Your specified OSM file does not exist:unterfranken.osm
    at com.graphhopper.reader.OSMReader.osm2Graph(OSMReader.java:170)
    at com.graphhopper.reader.OSMReader.osm2Graph(OSMReader.java:144)
    at com.graphhopper.reader.OSMReader.main(OSMReader.java:70)
## now running com.graphhopper.reader.OSMReader. java opts=-XX:PermSize=20m -XX:MaxPermSize=20m -Xmx500m -Xms500m
2012-12-04 15:19:31,346 [main] INFO  com.graphhopper.reader.OSMReader - using GraphStorage|RAMDirectory|1, memory:totalMB:479, usedMB:5
Exception in thread "main" java.lang.IllegalArgumentException: Graph not found and no OSM xml provided.
    at com.graphhopper.reader.OSMReader.osm2Graph(OSMReader.java:166)
    at com.graphhopper.reader.OSMReader.osm2Graph(OSMReader.java:144)
    at com.graphhopper.reader.OSMReader.main(OSMReader.java:70)

If you really want to refactor the reader into a clean state, I will transfer some code from the reader of my map compiler. It has a set of OSM object classes and an OSMFile class to read them.

This could later be extended to a PBF parser.

When recovering a shortest Path from a RoutingAlgorithm, there is currently no easy way to tell which edge between two nodes has the smallest weight / shortest distance.

It would be nice to add edge IDs to Path since there could be several edges with different weights between two nodes.

I'm really impressed by the speed of Graphhopper. Will there be support for turn restrictions in future releases?

Hi,

I was interested in the project based on the timings I see on the web demo. I am seeing roughly 6ms times for complex routes across London. So I thought I would try this locally to see how you had done this and get my hands dirty with the code. I started by getting things built and then adding a simple unit test, which you can see here: https://gist.github.com/quintona/5385839

Essentially, I took the british Isles dataset from OSM and reduced it down to a sub set of London using osmosis. This output file I called london.osm.

When I run without contraction hierarchies, it works fine but takes 300ms. It doesn't work at all when I set contraction hierarchies to true, fastest or shortest.

I obviously delete the associated data directory (london-gh) after I change between these. Is this a defect or am I doing something wrong in this example?

The roundabout has no oneway=yes tag but it still should get the proper direction like OSRM.

http://graphhopper.com/maps/?point=49.950602,11.576656&point=49.951085,11.576859

vs. OSRM

http://osrm.at/3nI

Occasional profiling does not hurt and I could not resist.

Do you have profiling methods available or included with graphhopper?

I had a closer look at the import using jrat because it is so simple to use.
http://jrat.sourceforge.net/

Here's the results for the import of bavaria.osm:

As you can see the most time is spent

• parsing XML ~50%
• using LongIntTree ~15%

Two ideas come to mind to speed up the import

• replace the SAX parser with a custom XML reader based on FileChannel. Probably faster, but could not read text values like names, only numbers and tags
• try a PBF reader which is custom and binary anyway