|
Dynamical System Framework
|
Plans routes on a road network with the A* algorithm. More...
#include <Router.hpp>
Public Types | |
| using | EdgeWeight = std::function<double(Street const&)> |
| A street cost function. | |
Public Member Functions | |
| void | setEdgeWeight (std::string_view name, double distanceCost=0.1) |
| Set the street costs of the routes. | |
| double | distanceCost () const noexcept |
| Get the distance cost of the routes, in s/m (0 unless "datt"). | |
| void | setPathRandomness (double sigma) |
| Set the path randomness. | |
| double | pathRandomness () const noexcept |
| Get the path randomness (see setPathRandomness). | |
| void | setAlgorithm (RouteAlgorithm const algorithm) noexcept |
| Set the search algorithm. | |
| auto | algorithm () const noexcept |
| Get the search algorithm. | |
| void | build (RoadNetwork const &network) |
| Build the routing graph of a network. | |
| void | updateCurrentWeights () |
| Take a snapshot of the current street weights (see setEdgeWeight). | |
| std::vector< Id > | route (Id fromStreetId, Id goalStreetId, RouteWeights weights, std::uint64_t agentKey=0) const |
| Plan a route from a street to the end of a street. | |
| std::vector< Id > | routeFromNode (Id fromNodeId, Id goalStreetId, RouteWeights weights, std::uint64_t agentKey=0) const |
| Plan a route from a node to the end of a street. | |
| double | routeCost (std::span< Id const > route, RouteWeights weights, std::uint64_t agentKey=0) const |
| Get the cost of a route. | |
| bool | isTurnAllowed (Id fromStreetId, Id toStreetId) const |
| Check whether the routing graph allows a turn. | |
| bool | isBuilt () const noexcept |
| Check whether the router has been built. | |
| std::size_t | nEdges () const noexcept |
| Get the number of streets of the routing graph. | |
| bool | hasHeuristic () const noexcept |
| Check whether the coordinates allow the straight-line distance heuristic. | |
Static Public Member Functions | |
| static EdgeWeight | edgeWeightFunction (std::string_view name, double distanceCost=0.1) |
| Get a street cost function by name. | |
| static double | noise (std::uint64_t agentKey, Id streetId, double sigma) |
| Get the noise an agent perceives on a street cost. | |
Plans routes on a road network with the A* algorithm.
The search runs on the streets (the dual graph), so that forbidden turns and the U-turn rule of RoadNetwork::isTurnAllowed are honoured. A route ends with the goal street, entered by an allowed turn: it reaches the end of it. The router holds a compact copy of the network's topology and of the street costs: it must be rebuilt (see build) whenever streets are added, opened or closed, or their turns or speeds change. Route queries are const and thread-safe, as each thread searches with its own buffers; building and taking snapshots are not.
The heuristic is the straight-line distance to the goal street's target node, scaled by the lowest cost per unit of distance over all streets, which makes it admissible and consistent for any non-negative costs and any coordinate system. Without coordinates on every node touching a street the heuristic is zero, i.e. the search is Dijkstra's.
With "datt" (the detour-avoiding travel time, see setEdgeWeight) every street also costs distanceCost · length. With path randomness (see setPathRandomness) each agent perceives each street cost multiplied by its own log-normal noise (see noise), so that agents with the same trip spread over more routes, whatever the weight.
| void dsf::mobility::Router::build | ( | RoadNetwork const & | network | ) |
Build the routing graph of a network.
| network | The road network |
Also takes a snapshot of the current weights (see updateCurrentWeights)
|
static |
Get a street cost function by name.
| name | One of:
|
| distanceCost | The cost of a unit of length of "datt", in time per unit of length (s/m): 0.1 makes a metre cost as much as driving it at 10 m/s |
| bool dsf::mobility::Router::isTurnAllowed | ( | Id | fromStreetId, |
| Id | toStreetId ) const |
Check whether the routing graph allows a turn.
| fromStreetId | The street the agent is on |
| toStreetId | The street the agent would take next |
|
static |
Get the noise an agent perceives on a street cost.
| agentKey | A key identifying the agent |
| streetId | The street id |
| sigma | The spread of the noise |
| std::vector< Id > dsf::mobility::Router::route | ( | Id | fromStreetId, |
| Id | goalStreetId, | ||
| RouteWeights | weights, | ||
| std::uint64_t | agentKey = 0 ) const |
Plan a route from a street to the end of a street.
| fromStreetId | The street the route starts with: its own cost is not counted |
| goalStreetId | The street to reach and travel: its cost is counted |
| weights | The street costs to plan on |
| agentKey | A key identifying the agent, for its noise (see setPathRandomness) |
| std::out_of_range | if a street is not in the routing graph |
| double dsf::mobility::Router::routeCost | ( | std::span< Id const > | route, |
| RouteWeights | weights, | ||
| std::uint64_t | agentKey = 0 ) const |
Get the cost of a route.
| route | The ids of the streets of the route |
| weights | The street costs to use |
| agentKey | A key identifying the agent, for its noise (see setPathRandomness) |
| std::out_of_range | if a street is not in the routing graph |
| std::vector< Id > dsf::mobility::Router::routeFromNode | ( | Id | fromNodeId, |
| Id | goalStreetId, | ||
| RouteWeights | weights, | ||
| std::uint64_t | agentKey = 0 ) const |
Plan a route from a node to the end of a street.
| fromNodeId | The node the route starts from: the cost of the first street counts |
| goalStreetId | The street to reach and travel: its cost is counted |
| weights | The street costs to plan on |
| agentKey | A key identifying the agent, for its noise (see setPathRandomness) |
| std::out_of_range | if the node or the street is not in the routing graph |
|
inlinenoexcept |
Set the search algorithm.
| algorithm | The algorithm (A* by default) |
| void dsf::mobility::Router::setEdgeWeight | ( | std::string_view | name, |
| double | distanceCost = 0.1 ) |
Set the street costs of the routes.
| name | The name of the cost function (see edgeWeightFunction), "traveltime" by default. It sets the current weights; "datt" also adds distanceCost · length to every street of every route, free-flow ones included |
| distanceCost | The cost of a unit of length of "datt", in s/m |
The current weights change at the next snapshot (see updateCurrentWeights)
| std::invalid_argument | if distanceCost is negative |
| void dsf::mobility::Router::setPathRandomness | ( | double | sigma | ) |
Set the path randomness.
| sigma | The spread of the log-normal noise each agent perceives on each street cost (see noise), 0 (the default) to plan without noise |
| std::invalid_argument | if sigma is negative |
| void dsf::mobility::Router::updateCurrentWeights | ( | ) |
Take a snapshot of the current street weights (see setEdgeWeight).
The streets are evaluated in parallel: no street may change meanwhile.