filter by road classes doesn't sync with the rtree input plugin

[robfitzgerald]

this issue imported from the internal repo

r-tree pre-processing maps coordinates to vertex ids on the map. if the user chooses a frontier model that restricts some links, the r-tree will not know of these restrictions. as a result, when the road class frontier model ignores TomTom's "restricted links" (road class 7), the denver beer run test case fails, as the origin or destination must have been pegged to vertices that are only connected via restricted links:

[frontier]
type = "road_class"
road_class_file = "data/tomtom_metro_denver_network/edges-road-class-enumerated.txt.gz"
valid_road_classes = ["1", "2", "3", "4", "5", "6"]  # ignore 7, "restricted road"

{
        "error": "no path exists between vertices 57209 and 356583",
        "request": {
            "destination_name": "Comrade Brewing Company",
            "destination_vertex": 356583,
            "destination_x": -104.9009913,
            "destination_y": 39.6757025,
            "energy_cost_coefficient": 0.0,
            "origin_name": "NREL",
            "origin_vertex": 57209,
            "origin_x": -105.1710052,
            "origin_y": 39.7402804
        }
    },

some possible solutions:

• make an edge-oriented rtree that is built based on the DirectedGraph or otherwise knows the list of valid edges
  • may require passing the DirectedGraph or the SearchApp in the InputPlugin constructor
• promote map matching algorithms from InputPlugin to its own component of SearchApp, where we can build it based on the combination of the frontier model and the directed graph
• ~modify the a star priority values so they are a tuple of (-int(cost * f), -road_class) where f is some factor such as 100~
  • no longer possible since we removed road class annotations from Edge
  • requires a lower-bound on cost values, which is practical if cost is utility-based
  • cast to integers in order to make an equality check possible
  • follows the road network hierarchy as a tie breaker, using higher-priority links when the costs are equivalent

[robfitzgerald]

the first solution may be best, but i'm finding it still may make my life complicated with my sub-project of creating a MEP tool using compass.

my problem is transit, but i think this applies to any mode which only has access to a subset of links. for a transit MEP search, i want to be able to 1) walk on road network links, 2) ride transit on transit links. i also want one instance of CompassApp to serve search for 4 travel modes - walk, bike, transit, drive - and so i want them all to share the same Graph instance and just have different traversal models. for this, the search algorithm needs

• all edges for all modes to exist
• some way for the traversal model to know which edges are valid
• some way for the frontier model to know which edges are valid for a given traversal model
• some way for the map matching rtree to know which edges are valid for a given traversal model

so, my problems:

1. frontier models in this case should change with the traversal model
2. rtree input plugin happens without having a way to know which edges are valid for the query

just thinking out loud here, trying to think about the options...

1. instead of having one CompassApp, have one for each mode and handle switching at the main.rs entry point, but sharing the Graph between each app, which allows rtree plugin, traversal and frontier models to be paired; then, specify those models in a way that they all know about the same valid set of edges
2. make an edge-based rtree, and share the &SearchApp as an argument to the InputPlugin builder or have it know the list of valid edges
3. extend the vertex rtree with a "departure search" which runs from the nearest vertex to the nearest valid edge
   • but we would need an "arrival search" too

all of these solutions sound spooky to me right now. hopefully with some more iteration a better way forward will become more clear.

[robfitzgerald]

i like the edge rtree idea the best. working back from the implementation, the input plugin would have an rtree of edges, a Box<[T]> of length $|E|$ with road class information, and a set of valid road classes HashSet<T>. it would probably build a nearest neighbor iterator (or maybe this one so we can still have a distance tolerance) and take from the iterator until it finds an edge with a valid road class.

this means we would load the road class information twice - once in the input plugin, once in the road class frontier model - doubling the RAM for a large dataset. we would also depend on the user to make sure their input plugin and frontier configuration have matching road class parameters. both of which sound a bit sloppy.

i like the design we have, so maybe this sloppyness is worth it, but maybe there's something we could fix to make it possible to share these data dependencies.

oh, also, this assumes that the edge-oriented search code (untested) is correct.

[robfitzgerald]

wondering here, does the list of valid road classes come from

• the input plugin configuration
• the query
• both? input plugin, but can be overridden by the query?