Distance Discrepancy Between Latvia and Poland Round Trip Using Python’s scgraph Package

Question

I came across a strange behavior, which I do not understand and might also be a bug. By coincidence, I found out that the distance in the rail network between Latvia and Poland is significantly higher than the return trip. I do not have an explanation for this.

import pandas as pd
import plotly.express as px
from scgraph_data.world_railways import world_railways_geograph
from haversine import haversine, Unit

# Latvia -> Poland
origin_node = {'latitude': 57.44720526589874, 'longitude': 25.349758294373878}
destination_node = {'latitude': 53.19471528057347, 'longitude': 14.658120650544548} 

# Poland -> Latvia
# destination_node = {'latitude': 57.44720526589874, 'longitude': 25.349758294373878}
# origin_node = {'latitude': 53.19471528057347, 'longitude': 14.658120650544548} 

sp = world_railways_geograph.get_shortest_path(origin_node=origin_node, destination_node=destination_node)

network_distance = sp['length']
direct_distance = haversine((origin_node['latitude'], origin_node['longitude']), (destination_node['latitude'], destination_node['longitude']), unit=Unit.KILOMETERS)
detour_index = round(network_distance / direct_distance, 4)    

print('Direct distance:', direct_distance, ', Network distance:', network_distance, ', Detour Index:', detour_index)

# Print route
df = pd.DataFrame(sp['coordinate_path'], columns=['latitude', 'longitude'])
fig = px.scatter_mapbox(df, lat='latitude', lon='longitude', zoom=3, height=400)
fig.update_layout(mapbox_style="open-street-map")
fig.show()

Answer 1

Quick Answer

This has to do with how scgraph adds your arbitrary origin / destination nodes into each geograph. Bumping up node_addition_circuity to something larger like 10 should fix the issue.

See the docs here.

Long Answer

By default, origin nodes are added into the network connecting the closest 4 nodes to it in each quadrant (ne, nw, se, sw).This is parameterized as node_addition_type. This allows much faster route searching through the network.

The destination node is added into the network connecting all nodes in the network to it (including the origin node). This is not parameterized and can not be changed to ensure solutions are possible for non connected geographs.

By default node_addition_circuity=4 when adding origin and destination nodes. This means that the haversine * 4 is what is calculated as the distance to each node for solving purposes. After solving, those distances are modified to be the off_graph_circuity factor which defaults to 1 (just the haversine). The goal of this is to prevent unreasonable solutions travelling off graph, but still allowing it and still providing accurate distances when travelling off graph.

Rationalization

Use Case: Bolognia -> New York using a maritime network. Port requirements not withstanding, the shortest path would be to ship from west coast Italy even though Bolognia is closer to east coast Italy. Travelling a bit farther off graph would be preferable to travelling all the way around Italy.

Alt Use Case: Ningbo -> Berlin using a maritime network. You wouldn't want to just go all off network straight to Berlin since you are trying to use the maritime network even though the graph route would be much longer.

Back to your question

In your case, the data for the rail network in Latvia is not connected between Jelgava and Riga. This is likely an issue with Open Street Maps data (missing links / misclassified railways - we only used major commercial for the world railways data).

When the destination was near Valmiera, it was more than 4x shorter to go off network in Jelgava straight to Valmiera than to go all the way around through Russia on the connected network. When the origin was near Valmiera, there were only 4 off network options (the 4 quadrants) so there was not an option to jump all the way to Jelgava.

Modified Example

from scgraph_data.world_railways import world_railways_geograph
import folium

# Poland -> Latvia
destination_node = {'latitude': 57.44720526589874, 'longitude': 25.349758294373878}
origin_node = {'latitude': 53.19471528057347, 'longitude': 14.658120650544548} 

# Note: The following functions are just for clean Folium mapping 
# and are otherwise irrelevant to the discussion.
def adjustArcPath(path):
    for index in range(1, len(path)):
        x = path[index][1]
        prevX = path[index - 1][1]
        path[index][1] = x - (round((x - prevX)/360,0) * 360)
    return path

def modifyArcPathLong(points, amount):
    return [[i[0], i[1]+amount] for i in points]

def getCleanArcPath(path):
    path = adjustArcPath(path)
    return [
        path,
        modifyArcPathLong(path, 360),
        modifyArcPathLong(path, -360),
        modifyArcPathLong(path, 720),
        modifyArcPathLong(path, -720)
    ]

Using node_addition_circuity=4 (default):

sp4 = world_railways_geograph.get_shortest_path(
    origin_node=origin_node, 
    destination_node=destination_node,
    node_addition_circuity=4,
)
# Create a folium map
map4 = folium.Map([55, 20], zoom_start=6)
# Populate it with the path
folium.PolyLine(
    getCleanArcPath(sp4['coordinate_path']),
    color='green',
    weight=5,
    opacity=0.5,
    popup='Length (KM): ' + str(sp4['length'])
).add_to(map4)
map4

Notice how the route jumps off graph and has a final leg that is a perfectly straight line to the destination.

Using node_addition_circuity=10:

sp10 = world_railways_geograph.get_shortest_path(
    origin_node=origin_node, 
    destination_node=destination_node,
    node_addition_circuity=10,
)
# Create a folium map
map10 = folium.Map([55, 20], zoom_start=6)
# Populate it with the path
folium.PolyLine(
    getCleanArcPath(sp10['coordinate_path']),
    color='green',
    weight=5,
    opacity=0.5,
    popup='Length (KM): ' + str(sp10['length'])
).add_to(map10)
map10

This should match almost exactly to the alternate direction path and distance.

Other Notes

It is also worth noting that scgraph has a haversine built in if you want to avoid the extra export.

See: https://connor-makowski.github.io/scgraph/scgraph/utils.html#haversine

from scgraph.utils import haversine

haversine(
    origin=[origin_node['latitude'], origin_node['longitude']], 
    destination=[destination_node['latitude'], destination_node['longitude']],
    units='km',
    circuity=1
)