Banning routes using route ID

[Laurent GRÉGOIRE]

Hi all,

Currently we ban routes based on Agency ID and route short name. For
the WS API, this parameter, named "bannedRoutes", is a comma-separated
list of agency ID + route name, the two IDs separated by an
underscore. For adding route ID we have several solutions to this, the
main requirement being ensuring backward compatibility:

1. Considering route name and route ID both the same parameter. I
would be strongly against this as this would break if you have common
route short name and route IDs in the same feed (I know lots of feeds
presenting that configuration, route short names and ID are very often
small integers).
2. Adding a new parameters (bannedRouteIds). This seems a bit
cumbersome and complexify the client API.
3. Setting a new (optional) field to current comma-separated list,
that is something like:
3a. AGENCYID__ROUTEID (two underscores: regexp is something like
".+?_(.+?)?(_.+)?" -- with the advantage that we do not add new magic
character that could break existing ID's)
3b. AGENCYID#ROUTEID (or any fancy character not present in GTFS
ID's, with the possibility of a conflict: escaping?)
3c. #AGENCYID_ROUTEID
...
4. Breaking backward-compatibility and creating a new format.

Any new idea?

--Laurent

[Andrew Byrd]

Hi Laurent,

I see in your pull request that you implemented option (3), which does
seem to be the best option. The double-underscore variant (3a) seems as
good as any. Thanks for including tests.

Could you add some documentation of this convention to the code? It is
the kind of thing with the potential to be very confusing unless clearly
stated.

Note that Javadoc on REST parameters (in the RoutingResource superclass)
will also automatically make it into the API docs
(http://www.opentripplanner.org/apidoc/resource_Planner.html) so that's
a good place for comments besides the RouteSpec(String) constructor.

-Andrew

[Laurent GRÉGOIRE]

Hi Andrew,

Thanks for your review. I've expanded the comments and copied them
over for preferred and unpreferred routes since the change also impact
them. Commit is in the pull request.

--Laurent

[Lukasz Witkowski]

Hi Laurent, Andrew

As I understand now this parameters (banned routes, prefered, unprefered) should work for configuration:

AGENCYID_ROUTESHORTNAME

AGENCYID__ROUTEID

and also 

AGENCYID_ROUTESHORTNAME_ROUTEID ?

Have you thought about changing this parameter so that it could work without specify AGENCYID (so for example _ROUTESHORTNAME banned all routes with this short name in given graph across all agencies) ?

Łukasz

2013/3/27 Laurent GRÉGOIRE <laurent....@gmail.com>

--
You received this message because you are subscribed to the Google Groups "OpenTripPlanner Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to opentripplanner...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Laurent GRÉGOIRE]

Hi Łukasz,

> As I understand now this parameters (banned routes, prefered, unprefered)
> should work for configuration:
> AGENCYID_ROUTESHORTNAME
> AGENCYID__ROUTEID

Yes indeed.

> and also
> AGENCYID_ROUTESHORTNAME_ROUTEID ?

As long as both name and ID matches, that's also possible. This was
not meant to be really supported and I don't think it's really useful
(since the client can provide incompatible short name and ID and have
to know both), but should work. In fact since route ID and short name
are usually unique within an agency that's probably redundant.

> Have you thought about changing this parameter so that it could work without
> specify AGENCYID (so for example _ROUTESHORTNAME banned all routes with this
> short name in given graph across all agencies) ?

To be honest no, but that could be implemented. Implementing that
would be a bit harder though: the way we use RouteSpec shoud be
modified a bit, as currently we rely on the equals/hashCode semantics
in order to use Java Sets. If you remove agency altogether this
semantics is no longer valid and you can't use simple Sets anymore. A
brute-force scan on a big list could have performance impact as you
need to check if a trip is banned for a boarding state change. There
are probably more clever approach (indexing on route name when you do
not provide agency for example), but that would need a bit of
refactoring, such as creating a "RouteSpecCollection" for example.

HTH,

--Laurent

[Andrew Byrd]

On 03/28/2013 02:56 PM, Laurent GRÉGOIRE wrote:

>> Have you thought about changing this parameter so that it could work without
>> specify AGENCYID (so for example _ROUTESHORTNAME banned all routes with this
>> short name in given graph across all agencies) ?
>
> To be honest no, but that could be implemented. Implementing that
> would be a bit harder though: the way we use RouteSpec shoud be
> modified a bit, as currently we rely on the equals/hashCode semantics
> in order to use Java Sets. If you remove agency altogether this
> semantics is no longer valid and you can't use simple Sets anymore. A
> brute-force scan on a big list could have performance impact as you
> need to check if a trip is banned for a boarding state change. There
> are probably more clever approach (indexing on route name when you do
> not provide agency for example), but that would need a bit of
> refactoring, such as creating a "RouteSpecCollection" for example.

So yes, it is possible, but I have to ask if this no-agency option is
worth added complexity. Lukasz, can you clarify why this would be
useful? I am wary of accumulating unused features.

-Andrew

[Lukasz Witkowski]

In our situation we build an OTP graph for group of 5 agencies. When we for example want user to list all banned routes, he does not think of different agency just put into the box route short name, So now I have to find agencies ids and combine it with user input. Do you have any thought how to do it better? (it is possible to prepare for the user some boxes or drop down list with all choices but we thinking of saving space in user interface.)

Łukasz

[Andrew Byrd]

On 03/28/2013 08:52 PM, Lukasz Witkowski wrote:
> So yes, it is possible, but I have to ask if this no-agency option is
> worth added complexity. Lukasz, can you clarify why this would be
> useful? I am wary of accumulating unused features.
>
> In our situation we build an OTP graph for group of 5 agencies. When we
> for example want user to list all banned routes, he does not think
> of different agency just put into the box route short name, So now I
> have to find agencies ids and combine it with user input. Do you have
> any thought how to do it better? (it is possible to prepare for the user
> some boxes or drop down list with all choices but we thinking of saving
> space in user interface.)

Well, it could "work" with improperly defined hashcode/equals methods:
if the agency is not included in the hashcode calculation and a null
agency name matches any other agency in the equals method.

Typically, how long is a list of banned routes? A linear search without
bizarre equals semantics would probably have a negligible effect on
performance for reasonable list lengths.

But just taking a step back here, why do users want to ban a route? I
think in Laurent's or my case the answer is simply "project
specifications require it", but has anyone actually observed this
feature being used?

-Andrew

[Thomas Koch]

I use it to avoid certain Highspeed trains. There is also a useful feature in quick feature to apply a thinned out timetable

[Laurent GRÉGOIRE]

> Well, it could "work" with improperly defined hashcode/equals methods:
> if the agency is not included in the hashcode calculation and a null
> agency name matches any other agency in the equals method.

Well, in the current form no: we already exclude routeName and routeId
in the hashCode since both values can be different and the object
still equals. The only remaining field on which we hash is agency: if
we remove it we end up with a constant hash and all map/set
degenerates into lists :)

> Typically, how long is a list of banned routes? A linear search without
> bizarre equals semantics would probably have a negligible effect on
> performance for reasonable list lengths.

I would not be so sure about route list length, we could have quite a
long list for certain use cases (I'm thinking about analyst here, like
banning all routes except one or including big sets in
preferred/unpreferred). Especially that the test is being made quite
often in the route plan. But we can always optimize common scenario
where we can hash and leave uncommon ones where we can't with a
brute-force approach.

--Laurent

[Laurent GRÉGOIRE]

What could be done however is to transform all partial RouteSpec (no
agency or no route id) at request time to a list of complete RouteSpec
of all matching routes, by scanning the whole list of routes of the
graph. This scan would be done once per request only. Then when
routing we would compare with a proper full hash.

--Laurent

[Andrew Byrd]

On 03/29/2013 10:35 AM, Laurent GRÉGOIRE wrote:
>> Typically, how long is a list of banned routes? A linear search without
>> bizarre equals semantics would probably have a negligible effect on
>> performance for reasonable list lengths.
>
> I would not be so sure about route list length, we could have quite a
> long list for certain use cases (I'm thinking about analyst here, like
> banning all routes except one or including big sets in
> preferred/unpreferred). Especially that the test is being made quite
> often in the route plan. But we can always optimize common scenario
> where we can hash and leave uncommon ones where we can't with a
> brute-force approach.

The only place I've used BannedRoutes is in Analyst with a set size of 1
or 2 maximum, but you're right, I can imagine needing to make that much
larger. I guess we should stay with sets.

[Andrew Byrd]

On 03/29/2013 10:40 AM, Laurent GRÉGOIRE wrote:
> What could be done however is to transform all partial RouteSpec (no
> agency or no route id) at request time to a list of complete RouteSpec
> of all matching routes, by scanning the whole list of routes of the
> graph. This scan would be done once per request only. Then when
> routing we would compare with a proper full hash.

Yes, agreed, this is the way to do it: Resolve the query parameters to
complete RouteSpecs beforehand.

[Laurent GRÉGOIRE]

Yes, agreed, this is the way to do it: Resolve the query parameters to
complete RouteSpecs beforehand.

 

I'm a bit afraid of doing so, as you would need access to the Graph data to get a list of transit route/agencies during the construction of the RoutingRequest in RoutingResource. AFAIK RoutingRequest and RoutingResource are independant from the actual used Graph (and should probably remain so). It could be done, but doing so would be making RoutingResource definitively dependent from the used Graph...

I'm more and more thinking that the ability to skip agency ID in banned route should be done on the client side, maybe by asking the server through some web-services the list of all agencies and mapping the routes itself.

--Laurent

[Lukasz Witkowski]

2013/4/2 Laurent GRÉGOIRE <laurent....@gmail.com>

Yes, agreed, this is the way to do it: Resolve the query parameters to
complete RouteSpecs beforehand.

 

I'm a bit afraid of doing so, as you would need access to the Graph data to get a list of transit route/agencies during the construction of the RoutingRequest in RoutingResource. AFAIK RoutingRequest and RoutingResource are independant from the actual used Graph (and should probably remain so). It could be done, but doing so would be making RoutingResource definitively dependent from the used Graph...

I agree that such change will somehow change the conception OTP was design, so if no one else see this problem in production, I vote for now to leave it in current state. 

I'm more and more thinking that the ability to skip agency ID in banned route should be done on the client side, maybe by asking the server through some web-services the list of all agencies and mapping the routes itself.

This is my current solution just to use http://.../ws/transit/agencyIds. 

--Laurent

[Andrew Byrd]

Great, sounds like everyone is in agreement here. Let's just stick with
the current implementation then.

-Andrew

On 04/03/2013 09:10 AM, Lukasz Witkowski wrote:
>
> 2013/4/2 Laurent GR�GOIRE <laurent....@gmail.com
> <mailto:laurent....@gmail.com>>

[Laurent GRÉGOIRE]

Well, thinking again about it, the current implementation is not ideal. The main drawbacks of the current implementation are:

A) RouteSpec class is used in two differents context that do not really model the same thing:

1/ representing a defined instance of a route

2/ representing a pattern (agency + route short name or agency + route ID) and maybe later a route short name only.

The two use case deserve their own class I would say (or case 1/ could maybe use directly the Route object)

B) We keep a set of RouteSpec to represent the set of Banned/(un)preferredRoute, which do not shield the client from implementation details on how we model a "set of routes", which may be more complex than a simple collection of partial values (and which prevent us to easily skip the agency ID).

C) To match a route with either name or ID we have a partial hash (agency only) on RouteSpec which can degrade performance (since usually we have few agencies and lots of routes -- this hashing degenerates a set of routes into a few big lists), and a weird and convoluted equals() semantics: bad for maintenance and re-usability.

We could thus introduce a "RouteSet" or "RouteMatcher" class:

class RouteSet {

    public boolean contains(RouteSpec | Route route) { ... };

}

class RoutingRequest {

    RouteSet bannedRoutes;

    RouteSet preferredRoutes;

    RouteSet unpreferredRoutes;

}

RouteSet/RouteMatcher could then use and hide any needed hacks to model route patterns based on names, Ids, with/without agencies, etc...

I may propose a new implementation soon. Comments welcome.

--Laurent

On 3 April 2013 14:38, Andrew Byrd <and...@fastmail.net> wrote:

Great, sounds like everyone is in agreement here. Let's just stick with
the current implementation then.

-Andrew

On 04/03/2013 09:10 AM, Lukasz Witkowski wrote:
>

> 2013/4/2 Laurent GRÉGOIRE <laurent....@gmail.com

[Laurent GRÉGOIRE]

Hi again,

https://github.com/openplans/OpenTripPlanner/pull/1037

Łukasz: good news for you, you can omit the agency ID in the spec list.

Any comments welcome,

--Laurent

[Lukasz Witkowski]

Hi,

I will use it for sure ! Thanks.

Łukasz

2013/4/4 Laurent GRÉGOIRE <laurent....@gmail.com>