Skip to main content

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.

Metadata

Release files for routing-lib 0.2.3

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for routing-lib 0.2.3
File Size Uploaded
routing_lib-0.2.3.tar.gz 17.2 kB Details

Built distribution (wheel)

Table of built distributions (wheels) for routing-lib 0.2.3
File Interpreter ABI Platform
routing_lib-0.2.3-py3-none-any.whl Python 3 none any Details

Total release size: 33.4 kB

Release files / routing_lib-0.2.3.tar.gz

Download URL routing_lib-0.2.3.tar.gz
Size 17.2 kB
Tags Source
SHA-256 checksum
How to use checksums
28bf0be7f52ced99a4d08a0a3e0e376eca3ec66bb1fe0bec56e4b085d14f1454
BLAKE2b-256 checksum
How to use checksums
9204525a917d89638b027058d67e8249be063172679ec26d7da0b850e3c0b922
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/4.0.2 CPython/3.10.6

Release files / routing_lib-0.2.3-py3-none-any.whl

Download URL routing_lib-0.2.3-py3-none-any.whl
Size 16.2 kB
Tags Python 3
SHA-256 checksum
How to use checksums
895c74d755fe1759eb2f2340beb1027523d2959e73f3572b129a8845ba927e1f
BLAKE2b-256 checksum
How to use checksums
18db3d0b1223730912ba391fe9ea3b40eb7c686de0868d72c79912cdf80a9ccf
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/4.0.2 CPython/3.10.6

Release history Release notifications | RSS feed

This release

0.2.3 This release

2 release files

0.2.2

2 release files

0.2.1

2 release files

0.2.0

2 release files

0.1.9

2 release files

0.1.8

2 release files

0.1.7

2 release files

0.1.6

2 release files

0.1.5

2 release files

0.1.4

2 release files

0.1.3

2 release files

0.1.2

2 release files

0.1.1

2 release files

0.1.0

1 release file

0.0.9

2 release files

0.0.8

2 release files

0.0.7

2 release files

0.0.6

2 release files

0.0.5

2 release files

0.0.3

2 release files

0.0.2

2 release files

0.0.1

2 release files

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page