pyroutelib3

Route finding

pyroutelib3.find_route(g: ~pyroutelib3.protocols.GraphLike[~pyroutelib3.protocols.NodeLike], start: int, end: int, distance: ~typing.Callable[[~typing.Tuple[float, float], ~typing.Tuple[float, float]], float] = <function haversine_earth_distance>, step_limit: int | None = 1000000) → List[int]

find_route uses the A* algorithm to find the shortest route between two nodes in the provided graph.

Returns an empty list if there is no route between the two nodes.

For graphs with turn restrictions, use find_route_without_turn_around(), as this implementation will generate instructions with immediate turn-arounds (A-B-A) to circumvent any restrictions.

step_limit (if not None) limits how many nodes may be expanded during the 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 (like the whole planet). Defaults to DEFAULT_STEP_LIMIT. Only set to None on small, contained graphs.

pyroutelib3.find_route_without_turn_around(g: ~pyroutelib3.protocols.GraphLike[~pyroutelib3.protocols.ExternalNodeLike], start: int, end: int, distance: ~typing.Callable[[~typing.Tuple[float, float], ~typing.Tuple[float, float]], float] = <function haversine_earth_distance>, step_limit: int | None = 1000000) → List[int]

find_route_without_turn_around uses the A* algorithm to find the shortest route between two points in the provided graph.

Returns an empty list if there is no route between the two points.

For graphs without turn restrictions, use find_route(), as it runs faster. find_route_without_turn_around has an extra search dimension - it needs to not only consider the node, but also what was the previous node to prevent A-B-A immediate turn-around instructions.

step_limit (if not None) limits how many nodes may be expanded during the 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 (like the whole planet). Defaults to DEFAULT_STEP_LIMIT. Only set to None on small, contained graphs.

exception pyroutelib3.StepLimitExceeded

Bases: ValueError

Exception used when a route search has exceeded its limit of steps. Either the nodes are really far apart, or no route exists.

Concluding that no route exists requires traversing the whole graph, which on real OpenStreetMap data may require going through the whole planet, hence this exception.

pyroutelib3.DEFAULT_STEP_LIMIT = 1000000

int([x]) -> integer int(x, base=10) -> integer

Convert a number or string to an integer, or return 0 if no arguments are given. If x is a number, return x.__int__(). For floating point numbers, this truncates towards zero.

If x is not a number or if base is given, then x must be a string, bytes, or bytearray instance representing an integer literal in the given base. The literal can be preceded by ‘+’ or ‘-’ and be surrounded by whitespace. The base defaults to 10. Valid bases are 0 and 2-36. Base 0 means to interpret the base from the string as an integer literal. >>> int(‘0b100’, base=0) 4

Simple graphs

class pyroutelib3.SimpleGraph(nodes: ~typing.Dict[int, ~pyroutelib3.protocols.NodeLikeT_co] = <factory>, edges: ~typing.Dict[int, ~typing.Dict[int, float]] = <factory>)

Bases: GraphLike[NodeLikeT_co]

SimpleGraph provides a base class and a simple implementation of the GraphLike protocol over two dictionaries: one holding nodes, and another holding edge costs.

get_edges(id: int) → Iterable[Tuple[int, float]]

get_edges must return all edges outgoing from a node with the provided ID. The edges are a pair of (node_id, cost). All returned neighbor nodes must exist in the graph.

If there are no outgoing edges from the provided node, must return an empty iterable. If a node with the given ID, may return an empty iterable, or raise KeyError.

get_node(id: int) → NodeLikeT_co

get_node must return a NodeLike of a node by the provided ID. If such a node doesn’t exist, must raise KeyError.

edges: Dict[int, Dict[int, float]]

nodes: Dict[int, NodeLikeT_co]

class pyroutelib3.SimpleNode(id: int, position: Tuple[float, float])

Bases: object

SimpleNode provides a base class and a simple implementation of the NodeLike protocol.

id: int

position: Tuple[float, float]

class pyroutelib3.SimpleExternalNode(id: int, position: Tuple[float, float], external_id: int)

Bases: object

SimpleExternalNode provides a base class and a simple implementation of the ExternalNodeLike protocol.

classmethod with_same_external_id(id: int, position: Tuple[float, float]) → Self

with_same_external_id instantiates a SimpleExternalNode with external_id set to the same value as id.

external_id: int

id: int

position: Tuple[float, float]

k-d tree

class pyroutelib3.KDTree(pivot: WithPositionT, left: KDTree[WithPositionT] | None = None, right: KDTree[WithPositionT] | None = None)

Bases: Generic[WithPositionT]

KDTree implements the k-d tree data structure, which can be used to speed up nearest-neighbor search for large datasets. Practice shows that osm.Graph.find_nearest_neighbor() takes significantly more time than find_route() when generating multiple routes with pyroutelib3. A k-d tree can help with that, trading memory usage for CPU time.

This implementation assumes euclidean geometry, even though the default distance function used is haversine_earth_distance(). This results in undefined behavior when points are close to the ante meridian (180°/-180° longitude) or poles (90°/-90° latitude), or when the data spans multiple continents.

classmethod build(points: Iterable[WithPositionT]) → Self | None

Creates a new K-D tree with all of the provided objects with a Position.

Note that the type-complaint usage of class methods on generic types requires explicitly providing the type argument, e.g.:

tree = KDTree[Node].build(nodes)

find_nearest_neighbor(root: ~typing.Tuple[float, float], distance: ~typing.Callable[[~typing.Tuple[float, float], ~typing.Tuple[float, float]], float] = <function haversine_earth_distance>) → WithPositionT

Find the closest node to root, as determined by the provided distance function.

left: KDTree[WithPositionT] | None = None

pivot: WithPositionT

right: KDTree[WithPositionT] | None = None

Distance functions

pyroutelib3.euclidean_distance(p, q, /)

Return the Euclidean distance between two points p and q.

The points should be specified as sequences (or iterables) of coordinates. Both inputs must have the same dimension.

Roughly equivalent to:

sqrt(sum((px - qx) ** 2.0 for px, qx in zip(p, q)))

pyroutelib3.haversine_earth_distance(a: Tuple[float, float], b: Tuple[float, float]) → float

Calculates the great-circle distance between two lat-lon positions on Earth using the haversine formula. Returns the result in kilometers.

pyroutelib3.taxicab_distance(a: Tuple[float, float], b: Tuple[float, float]) → float

Calculates the Taxicab distance between two points, in the same units as the input positions.