cspy.BiDirectional

Python wrapper for the bidirectional labelling algorithm with dynamic half-way point (Tilk 2017).

Parameters

Gobject instance nx.Digraph()

must have n_res graph attribute and all edges must have res_cost attribute.

max_reslist of floats

[H_F, M_1, M_2, ..., M_{n\_res}] upper bounds for resource usage (including initial forward stopping point). We must have len(max_res) = len(max_res)

min_reslist of floats

[H_B, L_1, L_2, ..., L_{n\_res}] lower bounds for resource usage (including initial backward stopping point). We must have len(min_res) = len(max_res)

preprocessbool, optional

enables preprocessing routine. Default : False.

directionstring, optional

preferred search direction. Either “both”, “forward”, or, “backward”. Default : “both”.

methodstring, optional

preferred method for determining search direction. Either “generated” (direction with least number of generated labels), “processed” (direction with least number of processed labels), or, “unprocessed” (direction with least number of unprocessed labels). Default: “unprocessed”

time_limitfloat or int, optional

time limit in seconds. Default: None

thresholdfloat, optional

specify a threshold for a an acceptable resource feasible path with total cost <= threshold. Note this typically causes the search to terminate early. Default: None

elementarybool, optional

whether the problem is elementary. i.e. no cycles are allowed in the final path. Note, True increases run time. Default: False

bounds_pruningbool, optional

whether lower bounds based on shortest paths are used when pruning labels using primal bounds. Note this is an experimental feature. See issues. Default: False

find_critical_resbool, optional

bool with whether critical resource is found at the preprocessing stage. Note1: this is an experimental feature. See issues. Note2: overrides critical_res value. Default false.

critical_resint, optional

Resource index to use as primary resource. Note: corresponding resource has to fulfil some conditions (e.g. monotonicity). See REFs. Default: 0

seedNone or int, optional

Disabled seed for random method class. Default : None.

REF_callbackREFCallback, optional

Custom resource extension callback. See REFs for more details. Default : None

two_cycle_elimination: bool, optional

whether 2-cycles should be eliminated for non-elementary RCSPP

Notes

The input graph must have a n_res attribute equal to the number of resources. The edges in the graph must all have a res_cost attribute (with size equal to n_res).

According to the inputs, four different algorithms can be used.

  • direction = “forward”: Monodirectional forward labeling algorithm

  • H_F == H_B: Bidirectional labeling algorithm with static halfway point.

  • direction = “backward”: Monodirectional backward labeling algorithm

  • H_F > H_B: Bidirectional labeling algorithm with dynamic halfway point.

  • H_F < H_B: The algorithm won’t go anywhere!

Where H_F / H_B are the first elements in the maximum / minimum resources arrays.

Example

To run the algorithm, create a BiDirectional instance and call run.

>>> from cspy import BiDirectional
>>> from networkx import DiGraph
>>> from numpy import array
>>> G = DiGraph(directed=True, n_res=2)
>>> G.add_edge("Source", "A", res_cost=array([1, 2]), weight=0)
>>> G.add_edge("A", "B", res_cost=array([1, 0.3]), weight=0)
>>> G.add_edge("A", "C", res_cost=array([1, 0.1]), weight=0)
>>> G.add_edge("B", "C", res_cost=array([1, 3]), weight=-10)
>>> G.add_edge("B", "Sink", res_cost=array([1, 2]), weight=10)
>>> G.add_edge("C", "Sink", res_cost=array([1, 10]), weight=0)
>>> max_res, min_res = [4, 20], [1, 0]
>>> bidirec = BiDirectional(G, max_res, min_res, direction="both")
>>> bidirec.run()
>>> print(bidirec.path)
["Source", "A", "B", "C", "Sink"]