Routing Library
===============
A simple routing library implementing algorithms available in literature
Installation
============
With Python and Pip installed, do:
.. code:: sh
pip install routing-lib
Functionalities
===============
There are 3 modules which can be imported as it follows:
.. code:: sh
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.
Raw data
{
"_id": null,
"home_page": "https://github.com/lwdovico/routing-lib",
"name": "routing-lib",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "Utils",
"author": "Ludovico Lemma",
"author_email": "lwdovico@protonmail.com",
"download_url": "https://files.pythonhosted.org/packages/92/04/525a917d89638b027058d67e8249be063172679ec26d7da0b850e3c0b922/routing_lib-0.2.3.tar.gz",
"platform": null,
"description": "Routing Library\r\n===============\r\n\r\nA simple routing library implementing algorithms available in literature\r\n\r\nInstallation\r\n============\r\n\r\nWith Python and Pip installed, do:\r\n\r\n.. code:: sh\r\n\r\n\r\n pip install routing-lib\r\n \r\n\r\nFunctionalities\r\n===============\r\n\r\nThere are 3 modules which can be imported as it follows:\r\n\r\n.. code:: sh\r\n\r\n\r\n from routing_lib.routing_algorithms import *\r\n from routing_lib.routing_measures import *\r\n from routing_lib.routing_utils import *\r\n \r\n\r\nAlgorithms\r\n----------\r\n\r\nThe ``routing_algorithms`` module provides various routing algorithms:\r\n\r\n- ``apply_penalization``: Applies penalization to edges in a graph\r\n based on a specific weight update criteria.\r\n- ``path_penalization``: This function applies penalization to edge\r\n weights specifically for shortest paths in a graph. It uses a\r\n specified function to update edge weights iteratively.\r\n- ``graph_randomization``: Randomizes weights for all edges in a graph\r\n to find k paths with updated costs. It extract the penalization\r\n values froma a random distribution function.\r\n- ``path_randomization``: Performs randomization on edge weights\r\n specifically for shortest paths in a graph, like before extracting\r\n penalization values from a random distribution.\r\n- ``duarouter``: Applies edge weight adjustments using a specified\r\n disturbance factor.\r\n- ``k_disjointed``: Penalizes edges to infinity to get to the results\r\n of quasi-disjointed paths.\r\n- ``no_randomization``: Applies no randomization to edge weights.\r\n- ``k_mdnsp``: This function applies a specified function to update\r\n edge weights for finding k paths with cost under a certain threshold\r\n while ensuring the maximum possible level of dissimilarity.\r\n- ``next_ssvp_by_length``: This function generates the next simple\r\n single-via path based on edge lengths in a graph.\r\n- ``kspml``: This function provides k-shortest paths with minimum\r\n collective length, by using the SSVP.\r\n- ``kspmo``: This function is similar to \u00e2\u20ac\u02dckspml\u00e2\u20ac\u2122 but employs a\r\n different dissimilarity metric to evaluate the similarity between\r\n paths.\r\n- ``plateau_algorithm``: This function runs the plateau-based algorithm\r\n to find k plateaus and build paths from it. It ensures that that the\r\n plateaus are disjointed, a maximum distance threshold must be\r\n specified.\r\n- ``k_shortest_paths``: This function implements the Yen algorithm for\r\n finding k shortest paths in a graph.\r\n\r\nMEASURES\r\n--------\r\n\r\nThe ``routing_measures`` module includes functions for computing various\r\nmeasures related to routing:\r\n\r\n- ``distinct_edges_traveled``: Computes the set of distinct edges\r\n traveled in a list of paths.\r\n- ``redundancy``: Computes the redundancy score of a set of paths.\r\n- ``normalized_jaccard_coefficient``: Computes the normalized Jaccard\r\n coefficient between two sets of edges.\r\n- ``compute_edge_load``: Computes the load on each edge in a list of\r\n paths.\r\n- ``compute_edge_load_normalized``: Computes the load normalized by\r\n path cardinality on each edge in a list of paths.\r\n- ``get_load_balance_entropy``: Computes the entropy of the set of\r\n paths on the road network.\r\n- ``compute_edge_capacity``: Computes the capacity of each edge in a\r\n road network.\r\n- ``compute_voc``: Computes the volume-over-capacity ratio for each\r\n edge in a road network.\r\n- ``dis``: Computes the dissimilarity between two paths.\r\n- ``div``: Computes the diversity between a list of paths.\r\n- ``compute_driver_sources``: Provide a list of paths with an edge to\r\n tile mapping and get the traffic source tiles for each edge\r\n- ``compute_MDS``: Get the Major Driver Sources by filtering according\r\n to a threshold\r\n- ``compute_k_road``: Get the kroad values for each edge based on the\r\n MDS.\r\n- ``split_interval_sliding``: Get specified window intervals\r\n- ``compute_temp_redundancy_sliding``: Compute the Temp Redundancy of a\r\n certain traffic assignment result according to a specified time\r\n interval\r\n\r\nUTILS\r\n-----\r\n\r\nThe ``routing_utils`` module offers utility functions for road routing:\r\n\r\n- ``from_sumo_to_igraph_network``: Converts a SUMO road network to an\r\n igraph network.\r\n- ``get_shortest_path``: Finds the shortest path between two edges in a\r\n igraph graph and translates it to SUMO format.\r\n- ``compute_path_cost``: Computes the cost of a path in a graph.\r\n- ``test_sumo_ig_shortest_paths``: Tests the conversion of sumo to\r\n iGraph with the shortest path algorithm with randomly selected edges.\r\n- ``visualize_paths``: Visualizes paths on a map using folium.\r\n- ``edge_list_to_gps_list``: Converts a list of edges to a list of GPS\r\n points.\r\n- ``compute_ellipse``: Computes an ellipse representing the region\r\n around an edge pair.\r\n- ``ellipse_subgraph``: Extracts a subgraph within the region defined\r\n by an ellipse.\r\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Small package with alternative routing algorithms and measures.",
"version": "0.2.3",
"project_urls": {
"Homepage": "https://github.com/lwdovico/routing-lib"
},
"split_keywords": [
"utils"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "18db3d0b1223730912ba391fe9ea3b40eb7c686de0868d72c79912cdf80a9ccf",
"md5": "a93ae62b14d721e737a267118014ee6e",
"sha256": "895c74d755fe1759eb2f2340beb1027523d2959e73f3572b129a8845ba927e1f"
},
"downloads": -1,
"filename": "routing_lib-0.2.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "a93ae62b14d721e737a267118014ee6e",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 16209,
"upload_time": "2023-11-22T22:32:32",
"upload_time_iso_8601": "2023-11-22T22:32:32.303823Z",
"url": "https://files.pythonhosted.org/packages/18/db/3d0b1223730912ba391fe9ea3b40eb7c686de0868d72c79912cdf80a9ccf/routing_lib-0.2.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "9204525a917d89638b027058d67e8249be063172679ec26d7da0b850e3c0b922",
"md5": "889446ccf52e4f61f2e0fe429f5d3cd7",
"sha256": "28bf0be7f52ced99a4d08a0a3e0e376eca3ec66bb1fe0bec56e4b085d14f1454"
},
"downloads": -1,
"filename": "routing_lib-0.2.3.tar.gz",
"has_sig": false,
"md5_digest": "889446ccf52e4f61f2e0fe429f5d3cd7",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 17164,
"upload_time": "2023-11-22T22:32:34",
"upload_time_iso_8601": "2023-11-22T22:32:34.595178Z",
"url": "https://files.pythonhosted.org/packages/92/04/525a917d89638b027058d67e8249be063172679ec26d7da0b850e3c0b922/routing_lib-0.2.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-11-22 22:32:34",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "lwdovico",
"github_project": "routing-lib",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "routing-lib"
}
JSON
