Small package with alternative routing algorithms and measures.
Project description
Routing Library
A simple routing library implementing algorithms available in literature
Installation
With Python and Pip installed, do:
pip install routing-lib
Functionalities
There are 3 modules which can be imported as it follows:
from routing_lib.routing_algorithms import *
from routing_lib.routing_measures import *
from routing_lib.routing_utils import *
Algorithms
The routing_algorithms module provides various routing algorithms:
apply_penalization: Applies penalization to edges in a graph based on a specific weight update criteria.
path_penalization: This function applies penalization to edge weights specifically for shortest paths in a graph. It uses a specified function to update edge weights iteratively.
graph_randomization: Randomizes weights for all edges in a graph to find k paths with updated costs. It extract the penalization values froma a random distribution function.
path_randomization: Performs randomization on edge weights specifically for shortest paths in a graph, like before extracting penalization values from a random distribution.
duarouter: Applies edge weight adjustments using a specified disturbance factor.
k_disjointed: Penalizes edges to infinity to get to the results of quasi-disjointed paths.
no_randomization: Applies no randomization to edge weights.
k_mdnsp: This function applies a specified function to update edge weights for finding k paths with cost under a certain threshold while ensuring the maximum possible level of dissimilarity.
next_ssvp_by_length: This function generates the next simple single-via path based on edge lengths in a graph.
kspml: This function provides k-shortest paths with minimum collective length, by using the SSVP.
kspmo: This function is similar to ‘kspml’ but employs a different dissimilarity metric to evaluate the similarity between paths.
plateau_algorithm: This function runs the plateau-based algorithm to find k plateaus and build paths from it. It ensures that that the plateaus are disjointed, a maximum distance threshold must be specified.
k_shortest_paths: This function implements the Yen algorithm for finding k shortest paths in a graph.
MEASURES
The routing_measures module includes functions for computing various measures related to routing:
distinct_edges_traveled: Computes the set of distinct edges traveled in a list of paths.
redundancy: Computes the redundancy score of a set of paths.
normalized_jaccard_coefficient: Computes the normalized Jaccard coefficient between two sets of edges.
compute_edge_load: Computes the load on each edge in a list of paths.
compute_edge_load_normalized: Computes the load normalized by path cardinality on each edge in a list of paths.
get_load_balance_entropy: Computes the entropy of the set of paths on the road network.
compute_edge_capacity: Computes the capacity of each edge in a road network.
compute_voc: Computes the volume-over-capacity ratio for each edge in a road network.
dis: Computes the dissimilarity between two paths.
div: Computes the diversity between a list of paths.
compute_driver_sources: Provide a list of paths with an edge to tile mapping and get the traffic source tiles for each edge
compute_MDS: Get the Major Driver Sources by filtering according to a threshold
compute_k_road: Get the kroad values for each edge based on the MDS.
split_interval_sliding: Get specified window intervals
compute_temp_redundancy_sliding: Compute the Temp Redundancy of a certain traffic assignment result according to a specified time interval
UTILS
The routing_utils module offers utility functions for road routing:
from_sumo_to_igraph_network: Converts a SUMO road network to an igraph network.
get_shortest_path: Finds the shortest path between two edges in a igraph graph and translates it to SUMO format.
compute_path_cost: Computes the cost of a path in a graph.
test_sumo_ig_shortest_paths: Tests the conversion of sumo to iGraph with the shortest path algorithm with randomly selected edges.
visualize_paths: Visualizes paths on a map using folium.
edge_list_to_gps_list: Converts a list of edges to a list of GPS points.
compute_ellipse: Computes an ellipse representing the region around an edge pair.
ellipse_subgraph: Extracts a subgraph within the region defined by an ellipse.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for routing_lib-0.2.3-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 895c74d755fe1759eb2f2340beb1027523d2959e73f3572b129a8845ba927e1f |
|
MD5 | a93ae62b14d721e737a267118014ee6e |
|
BLAKE2b-256 | 18db3d0b1223730912ba391fe9ea3b40eb7c686de0868d72c79912cdf80a9ccf |