search

graphhopper / map-matching

The map matching functionality is now located in the main repository https://github.com/graphhopper/graphhopper#map-matching
https://www.graphhopper.com/open-source/
Apache License 2.0
785 stars 274 forks source link

Allow map matching to use CH too #71

Closed kodonnell closed 7 years ago

kodonnell commented 8 years ago

Based on #60, though supports all (?) algorithms, not just CH.

GH change required

Not sure if it's a bug, but I had to change this:

if (cg.getWeighting() == weighting)

to

if (cg.getWeighting().getName() == weighting.getName())

Changed API

That is

new MapMatching(graph, locationIndex, encoder)

becomes

new MapMatching(hopper, algorithmOptions)

Easiest to see in the unit tests. Why did I change it?

Considerations (@karussell):

Seems to work fine, and I've parameterised some of the unit tests to run with both a CH and non-CH algorithm - both are passing fine. I'm still working on the Measurement option, but it's safe to say CH can be a fair bit faster.

karussell commented 8 years ago

Thanks a lot! Looks good.

There are some minor general things/thoughts. Would you mind to:

A pull request should be as small as possible. Feel free to create e.g. a new 'cleanup' pull request which we then could discuss, e.g. I do not find the mapMatching.match an improvement of the readability ;). But I also think that stuff like this needs an improvement e.g. we could architect map matching similar to GraphHopper.route but again this should be really another discussion/issue.

Not sure if it's a bug, but I had to change this

This should not be required: instead of creating a new Weighting object one would need to pass the existing one. Otherwise it is not guaranteed to work with CH if you create an arbitrary weighting just with the same name.

put("vehicle", "car")

In MapMatchingMain you should use the firstFlagEncoder.getName instead of the fixed "car"

karussell commented 8 years ago

Thanks a lot! Looks good.

There are some minor general things/thoughts. Would you mind to:

A pull request should be as small as possible. Feel free to create e.g. a new 'cleanup' pull request which we then could discuss, e.g. I do not find the mapMatching.match an improvement of the readability ;). But I also think that stuff like this needs an improvement e.g. we could architect map matching similar to GraphHopper.route but again this should be really another discussion/issue.

Not sure if it's a bug, but I had to change this

This should not be required: instead of creating a new Weighting object one would need to pass the existing one. Otherwise it is not guaranteed to work with CH if you create an arbitrary weighting just with the same name.

put("vehicle", "car")

In MapMatchingMain you should use the firstFlagEncoder.getName instead of the fixed "car"

kodonnell commented 8 years ago

Thanks @karussell. I hope I've made the requested changes, and I'll get the CLA to you in the next day or so. Does it look OK now? Interestingly, I noted that CH seems to be slower in the tests which is unexpected - looks like I need to hurry up with the measurement class!

FYI looks like that change made to Path is breaking map-matching i.e. the failed check above isn't related to this PR, I don't think.

karussell commented 8 years ago

Thanks!

Interestingly, I noted that CH seems to be slower in the tests which is unexpected

That would be strange. More or less unchanged could be expected for the normal case (as the routing in map matching involves usually only a few dozen nodes) but slower is indeed unexpected.

FYI looks like that change made to Path is breaking map-matching i.e. the failed check above isn't related to this PR, I don't think.

Yes, was a change in GH core, have fixed it in master here now.

AlgorithmOptions algoOptions

maybe we move this to the doWork method to avoid recreating the MapMatching class for every request, but can be done in a different PR.

firstEncoder.getClass().getName()

Sorry, here I meant: firstEncoder.toString which e.g. returns 'car' for CarFlagEncoder.

MapMatchingTest

This looks good with the parametrized code now.

FlexibleEncoder

The code formatting for variables in Java is flexibleEncoder, same for FlexibleHopper, FlexibleOpts, ...

testSmallSeparatedSearchDistance

The naming (and also your new description) does no longer make sense, but not really related to this PR

kodonnell commented 8 years ago

have fixed it in master here now

Merged

maybe we move this to the doWork method to avoid recreating the MapMatching class for every request, but can be done in a different PR

Maybe - though it could be problematic as then the user might try to use an algorithm that doesn't work for the provided hopper instance. So we'd probably want to move both constructor arguments to doWork. Yes on different PR.

The code formatting for variables

Silly, my bad

The naming (and also your new description) does no longer make sense, but not really related to this PR

I think I just copied the existing description that was in the code.

I better wait until Monday for the CLA, as (after reading the conditions) it looks like I'll need to check with my boss first. However, looks like the build is now tickety-boo.

karussell commented 8 years ago

Thanks!

I better wait until Monday for the CLA, as (after reading the conditions)

Sure. Just a clarification: you'd agree to submit your code under the Apache License, we do not take away your rights (which is necessary in other open source projects due to the dual licensing but we don't have this problem)

kodonnell commented 8 years ago

Done (I think). I'd prefer not to mess with main/server too much, as I'm only really familiar with the Java API.

karussell commented 7 years ago

Hmmh, I'll have to do some changes and add a test for this functionality.

karussell commented 7 years ago

Ok. This looks a bit ugly under the hood, but works for now and the usage scenario looks better.

See this new branch: https://github.com/graphhopper/map-matching/commits/issue_71

The only strange thing left is why with CH ".maxVisitedNodes(30)" the tests fails but for non-CH ".maxVisitedNodes(30)" or even ".maxVisitedNodes(20)" is okay. See my comment there: https://github.com/graphhopper/map-matching/commit/48b0f1bf446fbfe5ac9d02ffad09a824e50d3b69#commitcomment-19285949

kodonnell commented 7 years ago

Commented - I'm a bit confused too.

I'm not sure what to do now there are two branches, so if there's anything I need to change, let me know in which one.

karussell commented 7 years ago

Will look into it again. I'm sure the correct algos are picked but I'm not sure why CH requires more nodes.

I'm not sure what to do now there are two branches, so if there's anything I need to change, let me know in which one.

I just created a branch as I cannot push/edit to your pull request

kodonnell commented 7 years ago

Hi @karussell - are you waiting on me (or anything I can do?) to merge this? I'd find it easier to have this in master before doing any further work on it.

karussell commented 7 years ago

Just wanted to investigate regarding the confusing nodes limit, maybe it is just the maximum and the average nodes usage is lower for CH.

kodonnell commented 7 years ago

I'll have a look now at if it's a pure GH issue: I'll find the start/end points using > 20 visited nodes, and see if they also do they same in GH, etc.

karussell commented 7 years ago

This is merged now. @kodonnell you should update your git author information, otherwise the commits are not linked and incorrectly referring to 'kane'

karussell commented 7 years ago

See https://github.com/graphhopper/map-matching/commit/545319925d3d6e388b680a6a65e16d1a09eed522

kodonnell commented 7 years ago

Awesome, thanks @karussell. How do I do that - I checked and it appeared I had 'kane' plus a generic email in my git settings. I've added that email to my github account, but still no change. Do you mean something like this?

karussell commented 7 years ago

I think you need to use your github user name and then an email that you put into your account (hasn't to be public). You can try to commit stuff and push to github until you see your commits are linked to your account :)

Do you mean something like this?

No script necessary. I would just do it for future commits and change the git config appropriately.

kodonnell commented 7 years ago

Ok - will leave it as is, and be more careful next time. Thanks.

karussell commented 7 years ago

Commented - I'm a bit confused too.

Okay, this is the case for normal routing too. So if you look into the response JSON of this route and compare it with the CH version you see that you get "visited_nodes.average":"12.0" which is 4 more than for none-CH. So it might be worth to enable/disable CH per request e.g. if the GPS signal distance is always longer than lets say 200m (have not properly measured the beeline distance where it makes sense to use CH on average)

karussell commented 7 years ago

Forgot one comment: it might be also due to the missing 'stall on demand', which is also mentioned in this issue and should give us a rough '2x' boost according to different papers.

karussell commented 7 years ago

Now that landmarks are in the master https://github.com/graphhopper/graphhopper/pull/780 it could be interesting to test if bidir A* with or without landmarks are faster for map matching. For alternative routes this gave a good speed up already.

michaz commented 7 years ago

it seems cleaner as a user, all I need to provide is a GH instance, plus information about which algorithm to use, etc. No need to provide e.g. a LocationIndexMatch (which generally I have no need for) etc.

Well, now it's created in the MapMatching constructor, i.e. per request. I repeat, we are now creating one location index per request. That the location index is a long-lived object, and MapMatching is a per-request object, was the reason that the location index was dependency-injected into MapMatching.

In general, it's a good thing to pass dependencies "small-grained" -- i.e. LocationIndex and FlagEncoder instead of GraphHopper --, to indicate what is actually needed by MapMatching (!) and what not.

(which generally I have no need for) etc.

That's the dilemma of dependency injection. Injected dependencies should follow the needs of the thing which is created, not the needs of the user of that thing. Yes, that makes constructors long and ugly, and that's what those dependency-injection frameworks are there to resolve (if desired).

michaz commented 7 years ago

I noted that CH seems to be slower in the tests

Possibly related if it's about the web tests (otherwise not).

EDIT: Probably not, since "LocationIndexMatch" is just a wrapper around the real location index. Still, that looks more like a lucky accident and is very confusing to me.

michaz commented 7 years ago

(I may be addressing this in the upcoming dropwizardification, no action required.) :-)

kodonnell commented 7 years ago

I repeat, we are now creating one location index per request.

Depends how you use it. I use the (Java) API to

  1. create the type of map-matching I want
  2. call doWork on each 'request'

So only one LocationIndexMatch is created. This made sense to me, but that doesn't mean it's good ... or that I programmed it well = ) Also, as you say, LocationIndexMatch is just a wrapper (I think) so cheap to create.

In general, it's a good thing to pass dependencies "small-grained" -- i.e. LocationIndex and FlagEncoder instead of GraphHopper --, to indicate what is actually needed by MapMatching (!) and what not.

Agreed - except LocationIndexMatch is only ever needed by MapMatching, so I'd argue it should be internal, and the user need not worry about it. Put another way, there should be a wrapper so users don't have to worry about things they don't need to worry about. You could probably make LocationIndexMatch an optional argument, if you want that flexibility.

... dependency injection ...

That's beyond my Java level - it'd be great if you could use it to improve the API.

Possibly related if it's about the web test

I can't remember, but I think this was related to CH checking more nodes for smaller queries.

Still, that looks more like a lucky accident and is very confusing to me.

I was confused too = ) I tried to clarify a lot of the API (in my head) in the last PR I submitted, but it probably makes it more confusing for others.