search

opentripplanner / OpenTripPlanner

An open source multi-modal trip planner
http://www.opentripplanner.org
Other
2.2k stars 1.03k forks source link

IntermediatePlaces doesn't seem to work #1784

Closed clinct closed 3 years ago

clinct commented 9 years ago

When passing along the intermediatePlaces parameter in the request (for either a WALK or BIKE route) the returned route is not different then when not passing it along:

http://demo.planner.plannerstack.com/?module=planner&fromPlace=52.04879567682429%2C4.3196868896484375&toPlace=52.039187769080094%2C4.32389831542969&time=4%3A59pm&date=03-02-2015&mode=BICYCLE&maxWalkDistance=804.672&arriveBy=false&wheelchair=false&showIntermediateStops=false&itinIndex=0

http://demo.planner.plannerstack.com/?module=planner&intermediatePlaces=51.9896509%2C4.2468206&intermediatePlaces=51.9952128%2C4.2635225&intermediatePlacesOrdered=true&fromPlace=52.04879567682429%2C4.3196868896484375&toPlace=52.039187769080094%2C4.32389831542969&time=4%3A59pm&date=03-02-2015&mode=BICYCLE&maxWalkDistance=804.672&arriveBy=false&wheelchair=false&showIntermediateStops=false&itinIndex=0

The parameter does arrive at the server, but does not end up in the final request.

I have the feeling it goes wrong in Response.java:45:

public Response(UriInfo info) {
    this.requestParameters = new HashMap<String, String>();
    if (info == null) { 
        // in tests where there is no HTTP request, just leave the map empty
        return;
    }
    for (Entry<String, List<String>> e : info.getQueryParameters().entrySet()) {
        // include only the first instance of each query parameter
        requestParameters.put(e.getKey(), e.getValue().get(0));
    }
}

'info' still contains 'IntermediatePlaces', while 'requestParameters' doesn't.

buma commented 9 years ago

You are correct that something goes wrong in Response.java:45. Because only the last intermediatePlaces is used. But requestParameters is used only to show you which parameters were requested in response it isn't used in routing or anywhere else.

Real problem is somewhere in RoutingResource where intermediatePlaces are read with help of Jersey (I think). Both values of intermediatePlaces should be read into a list but only second is read for some reason.

EDIT: Interestingly with this URL: http://localhost:8080/otp/routers/default/plan?fromPlace=46.557443853672524%2C15.61208724975586&toPlace=46.559450479472936%2C15.64023971557617&time=4%3A59pm&date=03-02-2015&mode=BICYCLE&maxWalkDistance=804.672&arriveBy=false&wheelchair=false&showIntermediateStops=false&intermediatePlaces=46.54882632290703%2C15.624961853027346&intermediatePlaces=46.55260403908481%2C15.630798339843752&intermediatePlacesOrdered=true

I have 2 intermediatePlaces in RoutingResource

buma commented 9 years ago

Bug is on a client side. Because with your URL only second intermediatePlaces is sent to server.

buma commented 9 years ago

Found a bug doing PR.

buma commented 9 years ago

Another thing to change would be to support list of parameters in requestParameters. Now only first appearance of each parameter is returned.

clinct commented 9 years ago

Another solution could be to not have multiple request parameters, and just have these things comma separated. I actually haven't seen another API that has multiple parameters.

buma commented 9 years ago

But then I think it would be necessary to write parsing of parameters to list by ourselves. Now Jersey does it.

clinct commented 9 years ago

Indeed, and we should decide how we would like to send along a list of coordinates, something like (52.6,4.2),(51.7,4.5) might work?

Beside this, I do believe there's also a backend issue as I tried the following on the Portland graph, just directly towards the API:

clinct commented 9 years ago

Although the client issue has been resolved, the backend issue has not: planning a trip with an intermediatePlace still results in the error: 

 ERROR (GraphPathFinder.java:334) A graph path leaves before the requested time. This implies a bug.

When commenting out line 335, the correct trip is returned:

// gpi.remove();

So somehow the check that is used for countering path reversal asymmetry doesn't seem to work for requests with intermediatePlaces set.

I'm using the portland graph, this is an example request, even setting the intermediatePlaces multiple times is nicely rendered in the client if the line above is commented out.

Could this issue be re-opened? Perhaps some pointers could be given to where to solve this in a correct manner?

mukhark commented 9 years ago

The problem with the backend is that the code that finds the path with intermediatePlaces modifies the request to find each segment in the path. To find each segment, the request is modified by changing the start location to be the same as the destination location in the previous segment, changing the destination location to be the next intermediatePlace, and changing the request start time to be the arrival time of the previous segment. Thus when the path is completed, the request start time has been modified to be the start time of the final segment in the path (the segment from the final intermediatePlace to the destination location.

Thus when GraphPathFinder checks the path start time (which is based on the original requested start time), it occurs before start time recorded in the request object which has been reset to be the start time of the final segment in the path. GraphPathFinder then tries to call gpi.remove on the path, but the implementation class does not support remove() and an UnsupportedOperationException is thrown. I'm running Java 1.7.0_60 on a Windows Server 2008 machine; the iterator implementation class is java.util.AbstractList$Itr.

clinct commented 9 years ago

@mukhark: still thanks for your research.

If it's the case that that class doesn't support `remove()', would it then be a solution to make sure that this exception is correctly handled?

What would be the consequence of wrapping it in a try catch? So at least the intermediate places request works again?

I'm just not completely sure what is meant with the comment on line 322 of GraphPathFinder.java that states Detect and report that most obnoxious of bugs: path reversal asymmetry., and thus what it would result into when this .remove() is not done.

clinct commented 9 years ago

The work-around I used (to comment out gpi.remove() ) has appeared to stop working since version 0.19.0 (SNAPSHOT), as in, adding any intermediatePlaces parameter results in PATH_NOT_FOUND. Would anyone know what the reason behind this might be? Thanks!

abyrd commented 9 years ago

I recently made some big changes where I removed the entire path parser mechanism. This may have something to do with it but I don't have any clear idea about the source of the problem. We'd have to trace execution and look for the cause.

clinct commented 9 years ago

@abyrd Could I do anything to help?

abyrd commented 9 years ago

@clinct: nothing off the top of my head. I'll have to test it with the Portland URL you provided above and trace execution. Not sure when I'll be able to look at it.

leoromanovsky commented 8 years ago

Is this working in 0.18 ?

abyrd commented 8 years ago

Not yet. @clinct had a patch that got it working for a while, but we need to transform that into a true fix for the current version of OTP. Just for information, internally intermediate places just performs N searches, one for each sub-segment of the trip. It's possible to get the same results by just calling the API multiple times.

leoromanovsky commented 8 years ago

Ah nice, sounds good, I'll do that and merge results!

maracas44 commented 8 years ago

Hello everyone,

I have been working on this and I believe I have a fix. So far all my testing is going well. I would like to get feedback on my modifications to see if I am going about it the right way.

My fix was a modification of the getGraphPathsConsideringIntermediates Method. I noticed that the original request was being modified instead of a clone of the request. I made changes so that each intermediate path search has a clone of the original request which is modified with a new dateTime, from, and to, as well as setting the routing context.

`

private List<GraphPath> getGraphPathsConsideringIntermediates (RoutingRequest request) {
    if (request.hasIntermediatePlaces()) {
        long time = request.dateTime;
        GenericLocation from = request.from;
        List<GenericLocation> places = Lists.newLinkedList(request.intermediatePlaces);
        places.add(request.to);
        request.clearIntermediatePlaces();
        List<GraphPath> paths = new ArrayList<>();

        for (GenericLocation to : places) {
            //Modified the code as to create a new clone of the original
            //request for each intermediate place path search we would make.
            RoutingRequest tempRequest = request.clone();
            tempRequest.dateTime = time;
            tempRequest.from = from;
            tempRequest.to = to;
            tempRequest.rctx = null;
            tempRequest.setRoutingContext(router.graph);
            // TODO request only one itinerary here

            List<GraphPath> partialPaths = getPaths(tempRequest);
            if (partialPaths == null || partialPaths.isEmpty()) {
                return null;
            }

            GraphPath path = partialPaths.get(0);
            paths.add(path);
            from = to;
            time = path.getEndTime();
        }
        //Set the routing context for the original request
        request.setRoutingContext(router.graph);
        return Arrays.asList(joinPaths(paths));
    } else {
        return getPaths(request);
    }
}

`

Please check my work and let me know of any issues.

pieterbuzing commented 8 years ago

Hi @maracas44 ! I'm also currently working on this issue... (I know, I should have made a note in this issue). My solution looks almost identical, except that I keep track of the same DebugOutput instance which I attach to the context for each partial getPaths() call. Otherwise you don't have valid calculation times. I'm still working on some unit tests to make sure it won't break again in the future.

maracas44 commented 8 years ago

Hello @pieterbuzing ! Thank you for the feedback. It is nice to know that I am on the right track. I did not think of the DebugOutput that is a very nice catch! Do you then set the original request's context to the context of the last partial getPaths() call?

pieterbuzing commented 8 years ago

This is my current version. Note that this will not be final, because it doesn't work for arriveBy=true. In that case we have to create the subpaths in reverse order, i.e. for a trip with two intermediate places we first have to calculate the path (i_2, to), then (i_1, i_2), and then (from, i_1). So that will require some restructuring if we want to maintain elegance.

private List<GraphPath> getGraphPathsConsideringIntermediates (RoutingRequest request) {
        if (request.hasIntermediatePlaces()) {
            long time = request.dateTime;
            GenericLocation from = request.from;
            List<GenericLocation> places = Lists.newLinkedList(request.intermediatePlaces);
            places.add(request.to);
            request.clearIntermediatePlaces();
            List<GraphPath> paths = new ArrayList<>();
            DebugOutput debugOutput = null;

            for (GenericLocation to : places) {
                RoutingRequest intermediateRequest = request.clone();
                intermediateRequest.setNumItineraries(1);
                intermediateRequest.dateTime = time;
                intermediateRequest.from = from;
                intermediateRequest.to = to;
                intermediateRequest.rctx = null;
                intermediateRequest.setRoutingContext(router.graph);

                if (debugOutput != null) {// Restore the previous debug info accumulator
                    intermediateRequest.rctx.debugOutput = debugOutput;
                } else {// Store the debug info accumulator
                    debugOutput = intermediateRequest.rctx.debugOutput;
                }
                List<GraphPath> partialPaths = getPaths(intermediateRequest);
                assert partialPaths != null;
                if (partialPaths.size() == 0) {
                    return partialPaths;
                }

                GraphPath path = partialPaths.get(0);
                paths.add(path);
                from = to;
                time = path.getEndTime();
            }
            request.setRoutingContext(router.graph);
            request.rctx.debugOutput = debugOutput;

            return Collections.singletonList(joinPaths(paths));
        } else {
            return getPaths(request);
        }
    }
maracas44 commented 8 years ago

This is more or less what I understood you meant about the DebugOutput. Regarding the arriveBy=true I can only think of making a case for when this option is selected and reversing the "places" list and "to" and "from" then reverting the change, but I am not sure how elegant this would be. I will continue to work on this.

pieterbuzing commented 8 years ago

I created a pull request for this: https://github.com/opentripplanner/OpenTripPlanner/pull/2253 @abyrd would you be so kind to have a look at this?

One of my unittests revealed that there was a hidden problem in transit mode: the TransitBoardAlight.traverse() method checks whether we are not boarding a trip pattern that we just got off. In general this is smart, but when you visit an intermediate place then you are quite likely to take the same bus line again to get out of that place. So I had to make an ugly fix for that.

abyrd commented 8 years ago

@pieterbuzing 's fix for this in #2253 has been applied, but for some reason two of the tests now fail. This is probably due to interactions with other changes that have happened in the mean time since the patch was written. I have disabled these tests since @pieterbuzing has indicated he can't take a look at it right away, and we're no worse off now that before (because intermediate places weren't working). The tests should obviously be re-activated when we get a chance to clean this up.

abyrd commented 3 years ago

Superseded in OTP2 by #3183, closing.