Functions related to Dijktra’s Algorithm

This module contains functions related to Time-expanded Dijkstra’s algorithm

Algorithms.TIME_EXPANDED_DIJKSTRA.TE_DIJ_functions.edited_dijkstra_multitarget(G, SOURCE: int, target_list: tuple, weight) → dict[source]

Uses Dijkstra’s algorithm to find shortest weighted paths. This functions builds on top of networkx implementation of Dijkstra’s algorithm

Parameters

  • G – NetworkX graph

  • SOURCE – non-empty iterable of nodes Starting nodes for paths. If this is just an iterable containing a single node, then all paths computed by this function will start from that node. If there are two or more nodes in this iterable, the computed paths may begin from any one of the start nodes.

  • target_list – node label, optional Ending node for path. Search is halted when target is found.

  • weight – function Function with (u, v, data) input that returns that edges weight

Returns

dictionary

A mapping from node to shortest distance to that node from one of the SOURCE nodes.

Return type

distance

Examples

>>> dist = edited_dijkstra_multitarget(G, SOURCE, target_list, weight)
Algorithms.TIME_EXPANDED_DIJKSTRA.TE_DIJ_functions.get_possible_targets(stops_group, DESTINATION: int, D_TIME, stopevent_mapping: dict) → tuple[source]

Get the list of events from DESTINATION stop Id after D_TIME. These serve as possible target nodes for Dijkstra’s algorithm

Parameters

  • stops_group – pandas group object on stoptimes file using stop id column.

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

  • D_TIME (pandas.datetime) – departure time.

  • stopevent_mapping (dict) – mapping dictionary. Format: {(stop id, arrival time): new node id}

Returns

tuple containing Indexes of the reachable event of target node in stoptimes file target_list (tuple): tuple containing node Id corresponding reachable target nodes of to TE graph

Return type

idx (tuple)

Examples

>>> idx, target_list = get_possible_targets(stops_group, 52, pd.to_datetime('2019-06-10 00:00:00'), stopevent_mapping)
Algorithms.TIME_EXPANDED_DIJKSTRA.TE_DIJ_functions.get_sourcenode(stops_group, SOURCE: int, D_TIME, stopevent_mapping: dict) → int[source]

Using the earliest arrival event from the source node (after D_TIME), find the ID of the node in TE graph. This serves as source stop for Dijkstra’s algorithm.

Parameters

  • stops_group – pandas group object on stoptimes file using stop id column.

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

  • D_TIME (pandas.datetime) – departure time.

  • stopevent_mapping (dict) – mapping dictionary. Format: {(stop id, arrival time): new node id}

Returns

Source node Id corresponding to TE graph

Return type

source_node (int)

Examples

>>> source_node = get_sourcenode(stops_group, 36, pd.to_datetime('2019-06-10 00:00:00'), stopevent_mapping)
Algorithms.TIME_EXPANDED_DIJKSTRA.TE_DIJ_functions.heappop(heap)[source]

Pop the smallest item off the heap, maintaining the heap invariant.

Algorithms.TIME_EXPANDED_DIJKSTRA.TE_DIJ_functions.heappush(heap, item)[source]

Push item onto heap, maintaining the heap invariant.

Algorithms.TIME_EXPANDED_DIJKSTRA.TE_DIJ_functions.post_process_TE_DIJ(out_dist: dict, target_list: tuple, stop_times_file, D_TIME, idx: tuple) → tuple[source]

Post processing for TE_DIJ

Parameters

  • out_dist (dict) – Distance dictionary of format {node id : arrival time}

  • target_list (tuple) – tuple containing node Id corresponding reachable target nodes of to TE graph

  • stop_times_file (pandas.dataframe) – stop_times.txt file in GTFS.

  • D_TIME (pandas.datetime) – departure time.

  • idx (tuple) – tuple containing Indexes of the reachable event of target node in stoptimes file

Returns

Stop event that is reached time_reached (pandas.timestamp): arrival time at the stop event

Return type

stop_reached (tuple)

Examples

>>> stop_reached, time_reached = post_process_TE_DIJ(out_dist, target_list, stop_times_file, pd.to_datetime('2019-06-10 00:00:00'), idx)
Algorithms.TIME_EXPANDED_DIJKSTRA.TE_DIJ_functions.weight_function(G, weight)[source]

(Borrowed from NetworkX) Returns a function that returns the weight of an edge.

The returned function is specifically suitable for input to functions _dijkstra() and _bellman_ford_relaxation().

Parameters

  • G (NetworkX graph.) –

  • weight (string or function) – If it is callable, weight itself is returned. If it is a string, it is assumed to be the name of the edge attribute that represents the weight of an edge. In that case, a function is returned that gets the edge weight according to the specified edge attribute.

Returns

  • function – This function returns a callable that accepts exactly three inputs: a node, an node adjacent to the first one, and the edge attribute dictionary for the eedge joining those nodes. That function returns a number representing the weight of an edge.

  • If G is a multigraph, and weight is not callable, the

  • minimum edge weight over all parallel edges is returned. If any edge

  • does not have an attribute with key weight, it is assumed to

  • have weight one.