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 haveres_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 algorithmH_F == H_B: Bidirectional labeling algorithm with static halfway point.
direction
= “backward”: Monodirectional backward labeling algorithmH_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"]