routx 1.1.0

No project description provided

routx-python

GitHub | Documentation | Issue Tracker | PyPI

Python bindings for routx - library for simple routing over OpenStreetMap data.

Routx converts OSM data into a standard weighted directed graph representation, and runs A* to find shortest paths between nodes. Interpretation of OSM data is customizable via profiles. Routx supports one-way streets, access tags (on ways only) and turn restrictions.

Usage

pip install routx in a virtual environment.

Precompiled wheels are available for most popular platforms (aarch64, x86-64 × GNU Linux, musl Linux, MacOS and Windows). On anything else, cargo (please don't curl | sh and install from your system's package manager), ninja and a C/C++ compiler toolchain are required to properly compile the library.

import routx

g = routx.Graph()
g.add_from_osm_file("path/to/monaco.pbf", routx.OsmProfile.CAR)

start_node = g.find_nearest_node(43.7384, 7.4246)
end_node = g.find_nearest_node(43.7478, 7.4323)
route = g.find_route(start_node.id, end_node.id)

for node_id in route:
    node = g[node_id]
    print(node.lat, node.lon)

Reference

Unless noted otherwise, __init__ methods behave as expected for standard NamedTuple/dataclass/IntEnum objects.

routx.DEFAULT_STEP_LIMIT

DEFAULT_STEP_LIMIT: Final[int] = 1000000

Recommended A* step limit for routx.Graph.find_route.

routx.Node

class Node(NamedTuple):
    id: int
    osm_id: int
    lat: float
    lon: float

An element of a Graph. A named tuple.

Due to turn restriction processing, one OpenStreetMap node may be represented by multiple nodes in the graph. If that is the case, a "canonical" node (not bound by any turn restriction) will have id == osm_id.

Nodes with id == 0 are used by the underlying library to signify the absence of a node, are considered false-y and must not be used by consumers.

Methods:

• __bool__(self) -> bool - True if id is not zero.

Read-only properties:

• is_canonical: bool - True if id == osm_id.

routx.Edge

class Edge(NamedTuple):
    to: int
    cost: float

Outgoing (one-way) connection from a Node. A named tuple.

cost must be greater than the crow-flies distance between the two nodes.

routx.Graph

class Graph(MutableMapping[int, Node]):
    pass  # no attributes, constructor accepts no arguments

OpenStreetMap-based network representation as a set of nodes and edges between them.

Node access is implemented through the standard MutableMapping interface from ids (integers) to nodes.

Note that overwriting existing nodes preserves all outgoing and incoming edges. Thus updating a node position might result in violation of the Edge invariant and break route finding. It is discouraged to update nodes, and it is the caller's responsibility not to break this invariant.

Methods (other than the implemented for and inherited from MutableMapping[int, Node]):

• find_nearest_node(lat: float, lon: float) -> Node - find the closest canonical (id == osm_id) Node to the given position.

  This function requires computing distance to every Node in the graph and is not suitable for large graphs or for multiple searches. Use KDTree for faster NN finding.

  If the graph is empty, raises KeyError.

• get_edges(self, from_: int) -> list[Edge] - gets all outgoing edges from a node with a given id.

• get_edge(self, from_: int, to: int) -> float - gets the cost of traversing an edge between nodes with provided ids. Returns positive infinity when the provided edge does not exist.

• set_edge(self, from_: int, to: int, cost: float) -> bool - creates or updates an Edge from one node to another.

  The cost must not be smaller than the crow-flies distance between nodes, as this would violate the A* invariant and break route finding. It is the caller's responsibility to uphold this invariant.

  Returns True if an existing edge was overwritten, False otherwise.

  Note that given an Edge object, this method may be called with graph.set_edge(from_, *edge).

• delete_edge(self, from_: int, to: int, /, missing_ok: bool = True) -> None - ensures an Edge from one node to another does not exist. If no such edge exists and missing_ok is set to False, raises KeyError.

•   find_route(
        self,
        from_: int,
        to: int,
        /,
        without_turn_around: bool = True,
        step_limit: int = DEFAULT_STEP_LIMIT,
    ) -> array[int]
  

  Finds the cheapest way between two nodes using the A* algorithm. Returns an array of type q containing node IDs of such route. The array may be empty if no route exists.

  from_id must identify a specific node in the graph, and to_id must identify a specific canonical (id == osm_id) node; otherwise KeyError is raised.

  without_turn_around defaults to True and prevents the algorithm from circumventing turn restrictions by suppressing unrealistic turn-around instructions (A-B-A). This introduces an extra dimension to the search space, so if the graph doesn't contain any turn restrictions, this parameter should be set to False.

  step_limit limits how many nodes can be expanded during search before raising StepLimitExceeded. Concluding that no route exists requires expanding all nodes accessible from the start, which is usually very time consuming, especially on large datasets.

• simplify_route(self, route: Iterable[int], epsilon: float = 1e-5) -> array[int] - Simplifies a route (sequence of nodes) using the Ramer-Douglas-Peucker algorithm.

  If line is an instance of an array of type q (int64), then it is modified in-place, and a slice containing the simplified route is returned. Other elements are left undefined. Note that find_route returns such an array.

  Epsilon represents the maximum distance (in decimal degrees, as the implementation assumes flat, Euclidean geometry) for a point's distance to a line segment to be considered insignificant and therefore removed.

•   add_from_osm_file(
        self,
        filename: str | bytes | PathLike[str] | PathLike[bytes],
        profile: OsmProfile | OsmCustomProfile,
        /,
        format: OsmFormat = OsmFormat.UNKNOWN,
        bbox: tuple[float, float, float, float] = (0.0, 0.0, 0.0, 0.0),
    ) -> None
  

  Parses OSM data from the provided file and adds them to this graph.

  profile describes how the OSM data should be interpreted.

  format describes the file format of the input OSM data. Defaults to auto-detection.

  bbox filters features by a specific bounding box, in order: left (min lon), bottom (min lat), right (max lon), top (max lat). Ignored if all values are zero (default).

•   add_from_osm_memory(
        self,
        mv: memoryview,
        profile: OsmProfile | OsmCustomProfile,
        /,
        format: OsmFormat = OsmFormat.UNKNOWN,
        bbox: tuple[float, float, float, float] = (0.0, 0.0, 0.0, 0.0),
    ) -> None
  

  Parses OSM data from the provided contents of a memory file. The buffer must be contiguous and also mutable (for reasons only known to ctypes, because the underlying library takes a const pointer).

  profile describes how the OSM data should be interpreted.

  format describes the file format of the input OSM data. Defaults to auto-detection.

  bbox filters features by a specific bounding box, in order: left (min lon), bottom (min lat), right (max lon), top (max lat). Ignored if all values are zero (default).

•   def read_from_file(
        self,
        filename: str | bytes | PathLike[str] | PathLike[bytes],
        format: GraphFormat,
    ) -> None
  

  Reads data from a serialized graph file, and adds it to the provided graph.

• read_from_memory(self, mv: memoryview, format: GraphFormat) -> None - Reads data from a serialized graph buffer, and adds it to the provided graph.

  The buffer must be contiguous and also mutable (for reasons only known to ctypes, because the underlying library takes a const pointer).

•   write_to_file(
        self,
        filename: str | bytes | PathLike[str] | PathLike[bytes],
        format: GraphFormat,
    ) -> None
  

  Writes graph data to a file, as per the selected wire format.

• write_to_memory(self, format: GraphFormat) -> bytearray - Writes graph data to an in-memory buffer, as per the selected wire format.

routx.KDTree

class KDTree:
    pass # no attributes, private constructor

Methods:

• find_nearest_node(self, lat: float, lon: float) -> Node - finds the closest node to the provided position and returns its id. Raises KeyError when the k-d tree contains no nodes.

Class Methods:

• KDTree.build(graph: Graph) -> Self - builds a k-d tree with all canonical (id == osm_id) nodes contained in the provided graph.

routx.GraphFormat

class GraphFormat(IntEnum):
    BINARY = 1

Wire format of a full/serialized Graph. An IntEnum.

• BINARY - Custom, routx binary file format.

routx.OsmProfile

class OsmProfile(IntEnum):
    CAR = 1
    BUS = 2
    BICYCLE = 3
    FOOT = 4
    RAILWAY = 5
    TRAM = 6
    SUBWAY = 7

Predefined OSM conversion profiles. An IntEnum.

CAR

Penalties:

Tag	Penalty
highway=motorway	1.0
highway=motorway_link	1.0
highway=trunk	2.0
highway=trunk_link	2.0
highway=primary	5.0
highway=primary_link	5.0
highway=secondary	6.5
highway=secondary_link	6.5
highway=tertiary	10.0
highway=tertiary_link	10.0
highway=unclassified	10.0
highway=minor	10.0
highway=residential	15.0
highway=living_street	20.0
highway=track	20.0
highway=service	20.0

Access tags: access, vehicle, motor_vehicle, motorcar.

Allows motorroads and considers turn restrictions.

BUS

Penalties:

Tag	Penalty
highway=motorway	1.0
highway=motorway_link	1.0
highway=trunk	1.0
highway=trunk_link	1.0
highway=primary	1.1
highway=primary_link	1.1
highway=secondary	1.15
highway=secondary_link	1.15
highway=tertiary	1.15
highway=tertiary_link	1.15
highway=unclassified	1.5
highway=minor	1.5
highway=residential	2.5
highway=living_street	2.5
highway=track	5.0
highway=service	5.0

Access tags: access, vehicle, motor_vehicle, psv, bus, routing:ztm.

Allows motorroads and considers turn restrictions.

BICYCLE

Penalties:

Tag	Penalty
highway=trunk	50.0
highway=trunk_link	50.0
highway=primary	10.0
highway=primary_link	10.0
highway=secondary	3.0
highway=secondary_link	3.0
highway=tertiary	2.5
highway=tertiary_link	2.5
highway=unclassified	2.5
highway=minor	2.5
highway=cycleway	1.0
highway=residential	1.0
highway=living_street	1.5
highway=track	2.0
highway=service	2.0
highway=bridleway	3.0
highway=footway	3.0
highway=steps	5.0
highway=path	2.0

Access tags: access, vehicle, bicycle.

Disallows motorroads and considers turn restrictions.

FOOT

Penalties:

Tag	Penalty
highway=trunk	4.0
highway=trunk_link	4.0
highway=primary	2.0
highway=primary_link	2.0
highway=secondary	1.3
highway=secondary_link	1.3
highway=tertiary	1.2
highway=tertiary_link	1.2
highway=unclassified	1.2
highway=minor	1.2
highway=residential	1.2
highway=living_street	1.2
highway=track	1.2
highway=service	1.2
highway=bridleway	1.2
highway=footway	1.05
highway=path	1.05
highway=steps	1.15
highway=pedestrian	1.0
highway=platform	1.1
railway=platform	1.1
public_transport=platform	1.1

Access tags: access, foot.

Disallows motorroads.

One-way is only considered when explicitly tagged with oneway:foot or on highway=footway, highway=path, highway=steps, highway/public_transport/railway=platform.

Turn restrictions are only considered when explicitly tagged with restriction:foot.

RAILWAY

Penalties:

Tag	Penalty
railway=rail	1.0
railway=light_rail	1.0
railway=subway	1.0
railway=narrow_gauge	1.0

Access tags: access, train.

Allows motorroads and considers turn restrictions.

TRAM

Penalties:

Tag	Penalty
railway=tram	1.0
railway=light_rail	1.0

Access tags: access, tram.

Allows motorroads and considers turn restrictions.

SUBWAY

Penalties:

Tag	Penalty
railway=subway	1.0

Access tags: access, subway.

Allows motorroads and considers turn restrictions.

routx.OsmFormat

class OsmFormat(IntEnum):
    UNKNOWN = 0
    XML = 1
    XML_GZ = 2
    XML_BZ2 = 3
    PBF = 4

Format of the input OSM file. An IntEnum.

Values:

• UNKNOWN - unknown format - guess based on content.
• XML - force uncompressed OSM XML.
• XML_GZ - force OSM XML with gzip compression.
• XML_BZ2 - force OSM XML with bzip2 compression.
• PBF - force OSM PBF.

routx.OsmPenalty

class OsmPenalty(NamedTuple):
    key: str
    value: str
    penalty: float

Numeric multiplier for OSM ways with specific keys and values. A named tuple.

Attributes:

• key: str - key of an OSM way for which this penalty applies, used for value comparison (e.g. "highway" or "railway").
• value: str - value under key of an OSM way for which this penalty applies.E.g. "motorway", "residential", or "rail".
• penalty: float - multiplier of the length, to express preference for a specific way. Must be not less than one and be finite.

routx.OsmCustomProfile

@dataclass
class OsmCustomProfile:
    name: str
    penalties: list[OsmPenalty]
    access: list[str]
    disallow_motorroad: bool = False
    disable_restrictions: bool = False

Describes how to convert OSM data into a Graph. A dataclass.

If possible, usage of pre-defined OsmProfiles should be preferred. Using custom profile involves reallocation of all arrays and strings two times to match ABIs (first from Python to C, then from C to Rust). This is only a constant cost incurred on call to Graph.add_from_file or Graph.add_from_memory.

Attributes:

• name: str - human readable name of the routing profile, customary the most specific access tag.

  This value is not used for actual OSM data interpretation, except when set to "foot", which adds the following logic:

  • oneway tags are ignored - only oneway:foot tags are considered, except on:
    • highway=footway,
    • highway=path,
    • highway=steps,
    • highway=platform
    • public_transport=platform,
    • railway=platform;
  • only restriction:foot turn restrictions are considered.

• penalties: list[OsmPenalty] - tags of OSM ways which can be used for routing.

  A way is matched against all OsmPenalty objects in order, and once an exact key and value match is found; the way is used for routing, and each connection between two nodes gets a resulting cost equal to the distance between nodes multiplied the penalty.

  All penalties must be normal and not less than zero.

  For example, if there are two penalties:

  1. highway=motorway, penalty=1
  2. highway=trunk, penalty=1.5

  This will result in:

  • a highway=motorway stretch of 100 meters will be used for routing with a cost of 100.
  • a highway=trunk motorway of 100 meters will be used for routing with a cost of 150.
  • a highway=motorway_link or highway=primary won't be used for routing, as they do not any penalty.

• access: list[str] - list of OSM access tags (in order from least to most specific) to consider when checking for road prohibitions.

  This list is used mainly to follow the access tags, but also to follow mode-specific one-way and turn restrictions.

• disallow_motorroad: bool - force no routing over motorroad=yes ways.

• disable_restrictions: bool - force ignoring of turn restrictions.

routx.OsmLoadingError

class OsmLoadingError(ValueError):
    pass  # attributes and constructor the same as for ValueError

Raised when the underlying library has failed to load OSM data data. See logs for details.

routx.SerializationError

class SerializationError(ValueError):
    pass

Raised when the underlying library has failed to read/write graph data. See logs for details.

routx.StepLimitExceeded

class StepLimitExceeded(ValueError):
    pass  # attributes and constructor the same as for ValueError

Raised when Graph.find_route exceeded its step limit.

routx.earth_distance

def earth_distance(
    lat1: float,
    lon1: float,
    lat2: float,
    lon2: float,
) -> float:

Calculates the great-circle distance between two positions using the haversine formula.

Returns the result in kilometers.

routx.simplify_line

simplify_line(line: Iterable[float], epsilon: float = 1e-5) -> array[float]

Simplifies a line (an iterable of point coordinates) using the Ramer-Douglas-Peucker algorithm.

Points must be encoded as [x0 y0 x1 y1 x2 y2 ...]. Any odd trailing elements are ignored.

If line is an instance of an array of type f (float32), then it is modified in-place, and a slice containing the simplified line is returned. Other elements are left undefined.

Epsilon represents the maximum distance (in decimal degrees, as the implementation assumes flat, Euclidean geometry) for a point's distance to a line segment to be considered insignificant and therefore removed.

License

routx and routx-python are made available under the MIT license.