BUG: Crash when path ends in a driveway not reachable from the beginning

PyTrack version checks

[X] I have checked that this issue has not already been reported.
[X] I have confirmed this bug exists on the latest version of PyTrack.
[X] I have confirmed this bug exists on the main branch of PyTrack.

Issue Description

First of all, thank you for your project. It seems very helpful!

I'm having an issue running pytrack for a track that starts on a well connected road and ends up in a parking lot. It's making the pytrack crash with an error shown below.

The predecessor list ends up missing the "target" here. I'm not sure, but I think it is caused by the track ending up on a parking lot driveway that PyTrack treats as unreachable from the main road the track starts at. This is caused by the parking lot having a osm highway with a tag "service:driveway" which is only connected to the street with a highway of "service:parking_aisle". Parking aisle is filtered out with network_type="drive" while driveway is not.

Here's a picture to show the issue better, red arrow shows the direction of the track:

Reproducible Example

import numpy as np
from pytrack.graph import graph, distance
from pytrack.matching import candidate, mpmatching_utils, mpmatching

coords = [
    (61.464851, 23.72293),
    (61.464935, 23.721074),
    (61.465018, 23.719238),
    (61.464761, 23.718313),
    (61.46429, 23.7183)]

north, east = np.max(np.array([*coords]), 0)
south, west = np.min(np.array([*coords]), 0)

G = graph.graph_from_bbox(*distance.enlarge_bbox(north, south, west, east, 500), simplify=True, network_type='drive')

G_interp, candidates = candidate.get_candidates(G, coords, interp_dist=10, closest=True, radius=30)

trellis = mpmatching_utils.create_trellis(candidates)

path_prob, predecessor = mpmatching.viterbi_search(G_interp, trellis, "start", "target")

Error Message

... (Cut out many of similar lines)
Node 1004937441 not reachable from 1279650117
Node 1004937441 not reachable from 1229986873
Node 1004937441 not reachable from 1242556796
Node 1004937441 not reachable from 1212946680
Node 1004937441 not reachable from 1085933389
Traceback (most recent call last):
  File "example.py", line 21, in <module>
    path_prob, predecessor = mpmatching.viterbi_search(G_interp, trellis, "start", "target")
                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "mpmatching.py", line 82, in viterbi_search
    predecessor = mpmatching_utils.get_predecessor("target", predecessor)
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "mpmatching_utils.py", line 191, in get_predecessor
    pred = predecessor[target]
           ~~~~~~~~~~~^^^^^^^^
KeyError: 'target'

PyTrack/Python version information

Python 3.11.5 PyTrack 2.0.6

Additional Context

No response

Hi,

the problem is due to the fact that there are two isolated graphs, where in the second smaller one a candidate point of the last gps coordinate (61.46429, 23.7183) lies. The problem, as you say, is due to the point being in a parking area and network_type='drive' does not take into account parking lots when constructing the road graph. However, from PyTrack version 2.0.8 (you have 2.0.6) it is possible to define custom network_type. Below is the working code and the results obtained.

Remember to leave a star for the repository 🤟

import numpy as np
from pytrack.graph import graph, distance
from pytrack.matching import candidate, mpmatching_utils, mpmatching
from pytrack.analytics import visualization

coords = [
    (61.464851, 23.72293),
    (61.464935, 23.721074),
    (61.465018, 23.719238),
    (61.464761, 23.718313),
    (61.46429, 23.7183)]

north, east = np.max(np.array([*coords]), 0)
south, west = np.min(np.array([*coords]), 0)

custom_filter = ('["highway"]["area"!~"yes"]["access"!~"private"]'
                 '["highway"!~"abandoned|bridleway|bus_guideway|construction|corridor|cycleway|'
                 'elevator|escalator|footway|path|pedestrian|planned|platform|proposed|raceway|steps|track"]'
                 '["service"!~"emergency_access|private"]')

G = graph.graph_from_bbox(*distance.enlarge_bbox(north, south, west, east, 500), simplify=True, custom_filter=custom_filter)

G_interp, candidates = candidate.get_candidates(G, coords, interp_dist=10, closest=True, radius=30)

trellis = mpmatching_utils.create_trellis(candidates)

path_prob, predecessor = mpmatching.viterbi_search(G_interp, trellis, "start", "target")

loc = (np.mean(np.array([*coords])[:, 0]), np.mean(np.array([*coords])[:, 1]))
maps = visualization.Map(location=loc, zoom_start=15)

maps.draw_candidates(candidates, 30)

maps.add_graph(G, plot_nodes=True)
maps.draw_path(G_interp, trellis, predecessor)
maps

github

cosbidev / PyTrack