labeling_v2.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2023/5/6 14:21
# @Author  : Xavier Ma
# @Email   : xavier_mayiming@163.com
# @File    : labeling_v2.py
# @Statement : The hybrid link-node-based labeling method for the shortest path problem with turn restrictions (SPPTR)
# @Reference : Li Qingquan, et al. A hybrid link-node approach for finding shortest paths in road networks with turn restrictions[J]. Transactions in GIS, 2015.
from numpy import inf
from pqdict import PQDict


def find_neighbors(network):
    # find the neighbors of each node
    neighbor = []
    for i in network.keys():
        neighbor.append(list(network[i].keys()))
    return neighbor


def main(network, source, destination, tr):
    """
    The main function
    :param network: {node1: {node2: length, node3: length, ...}, ...}
    :param source: the source node
    :param destination: the destination node
    :param tr: turn restrictions
    :return:
    """
    # Step 1. Initialize parameters
    neighbor = find_neighbors(network)
    omega = []  # the list of explored labels
    queue = PQDict({})  # priority queue
    p_list = {}  # path label
    label_in = 0  # the number of labels added to the priority queue
    label_out = 0  # the number of labels popped from the priority queue
    rn = set()  # restricted nodes
    for turn in tr:
        if turn[1] != source and turn[1] != destination:
            rn.add(turn[1])

    # Step 2. Add the first labels
    for node in neighbor[source]:
        ind = str([source, node]) if node in rn else node
        queue[ind] = network[source][node]
        p_list[ind] = [source, node]
        label_in += 1

    # Step 3. The main loop
    while queue:

        # Step 3.1. Select the label with the minimum length
        (label, length) = queue.popitem()
        label_out += 1
        path = p_list[label]
        omega.append(label)
        i = path[-2]
        j = path[-1]
        if j == destination:
            return {
                'path': path,
                'length': length,
                'label in': label_in,
                'label out': label_out,
            }

        # Step 3.2. Extend labels
        for k in neighbor[j]:
            ind = str([j, k]) if k in rn else k
            if [i, j, k] not in tr and ind not in omega:
                temp_length = length + network[j][k]
                if temp_length < queue.get(ind, inf):
                    temp_path = path.copy()
                    temp_path.append(k)
                    queue[ind] = temp_length
                    p_list[ind] = temp_path
                    label_in += 1

    return {}


if __name__ == '__main__':
    test_network = {
        0: {2: 1},
        1: {2: 1},
        2: {0: 1, 1: 1, 3: 2, 5: 1},
        3: {4: 1},
        4: {5: 2},
        5: {2: 1},
    }
    s = 0
    d = 5
    tr = [[0, 2, 5]]
    print(main(test_network, s, d, tr))