Transfer Patterns functions

Module contains function related to transfer patterns, scalable transfer patterns

Algorithms.TRANSFER_PATTERNS.transferpattern_func.arrivaltme_query(stop1: int, stop2: int, deptime, routesindx_by_stop_dict: dict, stoptimes_dict: dict)[source]

Find the earliest trip departing from stop 1 after deptime and going to stop 2.

Parameters

  • stop1 (int) – Stop id

  • stop2 (int) – Stop id

  • deptime (pandas.datetime) –

  • routesindx_by_stop_dict (dict) – Keys: stop id, value: [(route_id, stop index), (route_id, stop index)]

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

Returns

pandas.datetime object

Algorithms.TRANSFER_PATTERNS.transferpattern_func.build_query_graph(SOURCE, NETWORK_NAME, hub_count, hubstops) → dict[source]

Builds the query graph for transfer patterns.

Parameters

  • SOURCE (int) – stop id of source stop.

  • NETWORK_NAME (str) – name of the network

  • hub_count (int) – Number of hub stops

  • hubstops (set) – set containing id’s of stop that are hubs

Returns

adjacency list for the query graph

Return type

adj_list (dist)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.build_query_graph_forSTP(SOURCE, DESTINATION, NETWORK_NAME, cluster_info) → dict[source]

Builds the query graph for scalable transfer patterns.

Parameters

  • SOURCE (int) – stop id of source stop.

  • DESTINATION (int) – stop id of destination stop. NETWORK_NAME (str): name of the network

  • cluster_info –

Returns

adjacency list for the query graph

Return type

adj_list (dist)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.check_dominance(t_l, adjlist_dict, DESTINATION) → bool[source]

Check if the best values in both the criteria is dominated by destination

Parameters

  • t_l (list) – list of tuples of format: (arrival time, number of transfer, predecessor node id, index of label updated from, self node_id)

  • adj_list (dist) – adjacency list for the query graph

  • DESTINATION (int) – stop id of destination stop.

Returns

True or False (boolean)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.enqueue_range_tbtr(connection_list, nextround, predecessor_label, R_t, Q, stoptimes_dict, MAX_TRANSFER) → None[source]

adds trips-segments to next round round and update R_t. Used in range queries

Parameters

  • connection_list (list) – list of connections to be added. Format: [(to_trip_id, to_trip_id_stop_index)].

  • nextround (int) – next round/transfer number to which trip-segments are added

  • predecessor_label (tuple) – predecessor_label for backtracking journey ( To be developed ).

  • R_t (nested dict) – Nested_Dict with primary keys as trip id and secondary keys as number of transfers. Format {trip_id: {[round]: first reached stop}}

  • Q (list) – list of trips segments

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

  • MAX_TRANSFER (int) – maximum transfer limit.

Returns: None

Algorithms.TRANSFER_PATTERNS.transferpattern_func.extract_transferpattern(pareto_journeys: list) → list[source]

Extract transfer patterns from pareto_journeys

Parameters

pareto_journeys (list) – pareto optimal set.

Returns

list of stop sequence transfer patterns

Return type

pareto_journeys (list)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.get_brutehubs(routes_by_stop_dict, NETWORK_NAME) → list[source]

Select hubs using brute force. This is Naive implementation that can be used to test the effectiveness of the hubs. The idea is to generate full transfer patterns (without hubs) and then use optimal paths to find hub stops.

Parameters

routes_by_stop_dict (dict) – preprocessed dict. Format {stop_id: [id of routes passing through stop]}. NETWORK_NAME (str): name of the network

Returns

list of tuples of format: (stop_id, number of optimal paths it stop_id is belongs to)

Return type

global_count (list)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.get_latest_trip_new(stoptimes_dict: dict, route: int, arrival_time_at_pi, pi_index: int, change_time) → tuple[source]

Get latest trip after a certain timestamp from the given stop of a route.

Parameters

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

  • route (int) – id of route.

  • arrival_time_at_pi (pandas.datetime) – arrival time at stop pi.

  • pi_index (int) – index of the stop from which route was boarded.

  • change_time (pandas.datetime) – change time at stop (set to 0).

Returns

trip index, trip else:

-1,-1 (e.g. when there is no trip after the given timestamp)

Return type

If a trip exists

Examples

>>> output = get_latest_trip_new(stoptimes_dict, 1000, pd.to_datetime('2019-06-10 17:40:00'), 0, pd.to_timedelta(0, unit='seconds'))
Algorithms.TRANSFER_PATTERNS.transferpattern_func.initialize_from_desti_onemany_tbtr(routes_by_stop_dict, stops_dict, DESTINATION_LIST, footpath_dict, idx_by_route_stop_dict) → dict[source]

Initialize routes/footpath to leading to destination stop in case of one-to-many rTBTR

Parameters

  • routes_by_stop_dict (dict) – preprocessed dict. Format {stop_id: [id of routes passing through stop]}.

  • stops_dict (dict) – preprocessed dict. Format {route_id: [ids of stops in the route]}.

  • DESTINATION_LIST (list) – list of stop ids of destination stop.

  • footpath_dict (dict) – preprocessed dict. Format {from_stop_id: [(to_stop_id, footpath_time)]}.

  • idx_by_route_stop_dict (dict) – preprocessed dict. Format {(route id, stop id): stop index in route}.

Returns

A dict to track routes/leading to destination stops. Key: route_id, value: {destination_stop_id: [(from_stop_idx, travel time, stop id)]}

Return type

L (nested dict)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.initialize_from_source_range_tbtr(dep_details, MAX_TRANSFER, stoptimes_dict, R_t) → list[source]

Initialize trips segments from source in rTBTR

Parameters

  • dep_details (list) – list of format [trip id, departure time, source index]

  • MAX_TRANSFER (int) – maximum transfer limit.

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

  • R_t (nested dict) – Nested_Dict with primary keys as trip id and secondary keys as number of transfers. Format {trip_id: {[round]: first reached stop}}

Returns

list of trips segments

Return type

Q (list)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.initialize_onemany_tbtr(MAX_TRANSFER, DESTINATION_LIST) → tuple[source]

Initialize values for one-to-many TBTR.

Parameters

  • MAX_TRANSFER (int) – maximum transfer limit.

  • DESTINATION_LIST (list) – list of stop ids of destination stop.

Returns

dict to store arrival timestamps. Keys: number of transfer, Values: arrival time. inf_time (pandas.datetime): Variable indicating infinite time.

Return type

J (dict)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.initialize_raptor(routes_by_stop_dict: dict, SOURCE: int, MAX_TRANSFER: int) → tuple[source]

Initialize values for RAPTOR.

Parameters

  • routes_by_stop_dict (dict) – preprocessed dict. Format {stop_id: [id of routes passing through stop]}.

  • SOURCE (int) – stop id of source stop.

  • MAX_TRANSFER (int) – maximum transfer limit.

Returns

deque to store marked stop. marked_stop_dict (dict): Binary variable indicating if a stop is marked. Keys: stop Id, value: 0 or 1. label (dict): nested dict to maintain label. Format {round : {stop_id: pandas.datetime}}. pi_label (dict): Nested dict used for backtracking labels. Format {round : {stop_id: pointer_label}} if stop is reached by walking, pointer_label= (‘walking’, from stop id, to stop id, time, arrival time)}} else pointer_label= (trip boarding time, boarding_point, stop id, arr_by_trip, trip id) star_label (dict): dict to maintain best arrival label {stop id: pandas.datetime}. inf_time (pd.timestamp): Variable indicating infinite time (pandas.datetime).

Return type

marked_stop (deque)

Examples

>>> output = initialize_raptor(routes_by_stop_dict, 20775, 4)
Algorithms.TRANSFER_PATTERNS.transferpattern_func.multicriteria_dij(SOURCE: int, DESTINATION: int, D_TIME, footpath_dict: dict, NETWORK_NAME: str, routesindx_by_stop_dict: dict, stoptimes_dict: dict, hub_count: int, hubstops: set) → dict[source]

Multicriteria Dijkstra’s algorithm to be used in transfer patterns query phase. The implementation has been borrowed from NetworkX.

Parameters

  • SOURCE (int) – stop id of source stop.

  • DESTINATION (int) – stop id of destination stop.

  • D_TIME (pandas.datetime) – departure time.

  • footpath_dict (dict) – preprocessed dict. Format {from_stop_id: [(to_stop_id, footpath_time)]}. NETWORK_NAME (str): name of the network

  • routesindx_by_stop_dict (dict) – Keys: stop id, value: [(route_id, stop index), (route_id, stop index)]

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

  • hub_count (int) – Number of hub stops

  • hubstops (set) – set containing id’s of stop that are hubs

Returns

adjacency list for the query graph

Return type

adj_list (dist)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.multicriteria_dij_alternate(SOURCE: int, DESTINATION: int, D_TIME, footpath_dict: dict, NETWORK_NAME: str, routesindx_by_stop_dict: dict, stoptimes_dict: dict, hub_count: int, hubstops: set) → dict[source]

Multicriteria Dijkstra’s algorithm to be used in transfer patterns query phase. The implementation has been borrowed from NetworkX. This is untested-varient of Martin’s algorithm

Parameters

  • SOURCE (int) – stop id of source stop.

  • DESTINATION (int) – stop id of destination stop.

  • D_TIME (pandas.datetime) – departure time.

  • footpath_dict (dict) – preprocessed dict. Format {from_stop_id: [(to_stop_id, footpath_time)]}. NETWORK_NAME (str): name of the network

  • routesindx_by_stop_dict (dict) – Keys: stop id, value: [(route_id, stop index), (route_id, stop index)]

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

  • hub_count (int) – Number of hub stops

  • hubstops (set) – set containing id’s of stop that are hubs

Returns

adjacency list for the query graph

Return type

adj_list (dist)

#TODO: Check correctness and efficiency

Algorithms.TRANSFER_PATTERNS.transferpattern_func.multicriteria_dij_forSTP(SOURCE: int, DESTINATION: int, D_TIME, footpath_dict: dict, NETWORK_NAME: str, routesindx_by_stop_dict: dict, stoptimes_dict: dict, cluster_info) → dict[source]

Multicriteria Dijkstra’s algorithm to be used in scalable transfer patterns query phase. The implementation has been borrowed from NetworkX.

Parameters

  • SOURCE (int) – stop id of source stop.

  • DESTINATION (int) – stop id of destination stop.

  • D_TIME (pandas.datetime) – departure time.

  • footpath_dict (dict) – preprocessed dict. Format {from_stop_id: [(to_stop_id, footpath_time)]}. NETWORK_NAME (str): name of the network

  • routesindx_by_stop_dict (dict) – Keys: stop id, value: [(route_id, stop index), (route_id, stop index)]

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

  • cluster_info –

Returns

adjacency list for the query graph

Return type

adj_list (dist)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.new_label_is_dominated(new_label, adjlist_dict, DESTINATION) → bool[source]

Check if the new_label dominates the destination label

Parameters

  • new_label (list) – list of tuples of format: (arrival time, number of transfer, predecessor node id, index of label updated from, self node_id)

  • adj_list (dist) – adjacency list for the query graph

  • DESTINATION (int) – stop id of destination stop.

Returns

True or False (boolean)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.onetoall_rraptor_forhubs(SOURCE: int, DESTINATION_LIST: list, d_time_groups, MAX_TRANSFER: int, WALKING_FROM_SOURCE: int, CHANGE_TIME_SEC: int, PRINT_ITINERARY: int, OPTIMIZED: int, routes_by_stop_dict: dict, stops_dict: dict, stoptimes_dict: dict, footpath_dict: dict, idx_by_route_stop_dict: dict, hubstops: set) → list[source]

One-To-Many rRAPTOR implementation. Trips are not scanned from the stops in hubstops set.

Parameters

  • SOURCE (int) – stop id of source stop.

  • DESTINATION_LIST (list) – list of stop ids of destination stop.

  • d_time_groups (pandas.group) – all possible departures times from all stops.

  • MAX_TRANSFER (int) – maximum transfer limit.

  • WALKING_FROM_SOURCE (int) – 1 or 0. 1 means walking from SOURCE is allowed.

  • CHANGE_TIME_SEC (int) – change-time in seconds.

  • PRINT_ITINERARY (int) – 1 or 0. 1 means print complete path.

  • OPTIMIZED (int) – 1 or 0. 1 means collect trips and 0 means collect routes.

  • routes_by_stop_dict (dict) – preprocessed dict. Format {stop_id: [id of routes passing through stop]}.

  • stops_dict (dict) – preprocessed dict. Format {route_id: [ids of stops in the route]}.

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

  • footpath_dict (dict) – preprocessed dict. Format {from_stop_id: [(to_stop_id, footpath_time)]}.

  • idx_by_route_stop_dict (dict) – preprocessed dict. Format {(route id, stop id): stop index in route}.

  • hubstops (set) – set containing id’s of stop that are hubs

Returns

out (list): list of trips required to cover all optimal journeys Format: [trip_id] elif OPTIMIZED==0:

out (list): list of routes required to cover all optimal journeys. Format: [route_id]

Return type

if OPTIMIZED==1

Examples

>>> output = onetomany_rraptor(36, [52, 43], pd.to_datetime('2019-06-10 00:00:00'), 4, 1, 0, 1, 0, routes_by_stop_dict, stops_dict, stoptimes_dict, footpath_dict, idx_by_route_stop_dict)
Algorithms.TRANSFER_PATTERNS.transferpattern_func.onetomany_rtbtr_forhubs(SOURCE: int, DESTINATION_LIST: list, d_time_groups, MAX_TRANSFER: int, WALKING_FROM_SOURCE: int, PRINT_ITINERARY: int, OPTIMIZED: int, routes_by_stop_dict: dict, stops_dict: dict, stoptimes_dict: dict, footpath_dict: dict, idx_by_route_stop_dict: dict, trip_transfer_dict: dict, trip_set: set, hubstops: set) → list[source]

One to many rTBTR implementation. Connections are not added from the stops in hubstops set.

Parameters

  • SOURCE (int) – stop id of source stop.

  • DESTINATION_LIST (list) – list of stop ids of destination stop.

  • d_time_groups (pandas.group) – all possible departures times from all stops.

  • MAX_TRANSFER (int) – maximum transfer limit.

  • WALKING_FROM_SOURCE (int) – 1 or 0. 1 means walking from SOURCE is allowed.

  • PRINT_ITINERARY (int) – 1 or 0. 1 means print complete path.

  • OPTIMIZED (int) – 1 or 0. 1 means collect trips and 0 means collect routes.

  • routes_by_stop_dict (dict) – preprocessed dict. Format {stop_id: [id of routes passing through stop]}.

  • stops_dict (dict) – preprocessed dict. Format {route_id: [ids of stops in the route]}.

  • stoptimes_dict (dict) – preprocessed dict. Format {route_id: [[trip_1], [trip_2]]}.

  • footpath_dict (dict) – preprocessed dict. Format {from_stop_id: [(to_stop_id, footpath_time)]}.

  • idx_by_route_stop_dict (dict) – preprocessed dict. Format {(route id, stop id): stop index in route}.

  • trip_transfer_dict (nested dict) – keys: id of trip we are transferring from, value: {stop number: list of tuples

  • form (of) –

  • trip_set (set) – set of trip ids from which trip-transfers are available.

  • hubstops (set) – set containing id’s of stop that are hubs

Returns

out (list): list of trips required to cover all optimal journeys Format: [trip_id] elif OPTIMIZED==0:

out (list): list of routes required to cover all optimal journeys. Format: [route_id]

Return type

if OPTIMIZED==1

Algorithms.TRANSFER_PATTERNS.transferpattern_func.post_process_range_onemany_tbtr(J, Q, rounds_desti_reached, PRINT_ITINERARY, desti, SOURCE, footpath_dict, stops_dict, stoptimes_dict, d_time, MAX_TRANSFER, trip_transfer_dict) → list[source]

Contains all the post-processing features for One-To-Many rTBTR. Currently supported functionality:

Collect list of trips needed to cover pareto-optimal journeys.

Parameters

  • J (dict) – dict to store arrival timestamps. Keys: number of transfer, Values: arrival time

  • Q (list) – list of trips segments.

  • rounds_desti_reached (list) – Rounds in which DESTINATION is reached.

  • desti (int) – destination stop id.

Returns

Trips needed to cover pareto-optimal journeys.

Return type

TBTR_out (set)

Algorithms.TRANSFER_PATTERNS.transferpattern_func.post_processing_onetoall_rraptor(DESTINATION_LIST: list, pi_label: dict, PRINT_ITINERARY: int, label: dict, OPTIMIZED: int) → list[source]
post processing for Ont-To-Many rRAPTOR. Currently supported functionality:

  1. Print the output

  2. Routes required for covering pareto-optimal set.

  3. Trips required for covering pareto-optimal set.

Parameters

  • DESTINATION_LIST (list) – list of stop ids of destination stop.

  • pi_label (dict) – Nested dict used for backtracking. Primary keys: Round, Secondary keys: stop id. Format- {round : {stop_id: pointer_label}}

  • PRINT_ITINERARY (int) – 1 or 0. 1 means print complete path.

  • label (dict) – nested dict to maintain label. Format {round : {stop_id: pandas.datetime}}.

  • OPTIMIZED (int) – 1 or 0. 1 means collect trips and 0 means collect routes.

Returns

final_trips (list): list of trips required to cover all pareto-optimal journeys. format - [trip_id] elif OPTIMIZED==0:

final_routes (list): list of routes required to cover all pareto-optimal journeys. format - [route_id]

Return type

if OPTIMIZED==1

Examples

>>> output = post_processing_onetomany_rraptor([1482], pi_label, 1, label, 0)
Algorithms.TRANSFER_PATTERNS.transferpattern_func.update_label_tbtr(label, no_of_transfer, predecessor_label, J, MAX_TRANSFER) → dict[source]

Updates and returns destination pareto set.

Parameters

  • label (pandas.datetime) – optimal arrival time .

  • no_of_transfer (int) – number of transfer.

  • predecessor_label (tuple) – predecessor_label for backtracking (To be developed)

  • J (dict) – dict to store arrival timestamps. Keys: number of transfer, Values: arrival time

  • MAX_TRANSFER (int) – maximum transfer limit.

Returns

dict to store arrival timestamps. Keys: number of transfer, Values: arrival time

Return type

J (dict)