openlr_dereferencer.maps.a_star package

Submodules

openlr_dereferencer.maps.a_star.tools module

Helper functions for A*

exception openlr_dereferencer.maps.a_star.tools.LRPathNotFoundError

Bases: Exception

No path was found through the map

openlr_dereferencer.maps.a_star.tools.heuristic

Estimated cost from current to target.

We use geographical distance here as heuristic here.

openlr_dereferencer.maps.a_star.tools.tautology(_) → bool

Returns always True, used as default line filter function.

Module contents

Provides the shortest_path(map, start, end) -> List[Line] function, which finds a shortest path between two nodes.

class openlr_dereferencer.maps.a_star.PQItem

Bases: tuple

A single item in the search priority queue

line

Alias for field number 2

node

Alias for field number 1

previous

Alias for field number 3

score

Alias for field number 0

class openlr_dereferencer.maps.a_star.Score

Bases: tuple

The score of a single item in the search priority queue

f

Alias for field number 0

g

Alias for field number 1

openlr_dereferencer.maps.a_star.shortest_path(start: openlr_dereferencer.maps.abstract.Node, end: openlr_dereferencer.maps.abstract.Node, linefilter: Callable[[openlr_dereferencer.maps.abstract.Line], bool] = <function tautology>, maxlen: float = inf) → List[openlr_dereferencer.maps.abstract.Line]

Returns a shortest path on the map between two nodes, as list of lines.

Uses the A* algorithm for this.

You may filter considered lines with linefilter and paths with maxlen.

Args:

start:

The node from which the path shall start

end:

The destination node of the path

linefilter:

The optional function parameter linefilter(Line) -> bool allows you to decide whether a line is allowed to be part of the path. If the function returns False, the line will not be taken into account. This is used for the ‘lowest frc next point’ attribute of openLR line references.

maxlen:

Maximum allowed path length. Abort the search for a shortest-path if this length is exceeded.

Returns:

A shortest path between the both nodes, after exclusion of lines according to linefilter

An empty path indicates that start and end node are the same.

Raises:

LRPathNotFoundError:

Raised if no path between the nodes could be found.

Even if a path exists, this may happen for two reasons:

• No path exists were all lines pass the linefilter
• All existing paths are longer than maxlen