cspy.GreedyElim
Simple Greedy elimination algorithm for the (resource) constrained shortest path problem. The algorithms solves a standard shortest path problem and eliminates resource infeasible edges iteratively until a resource feasible path is found.
Parameters
- Gobject instance
nx.Digraph()
must have
n_res
graph attribute and all edges must haveres_cost
attribute.- max_reslist of floats
[M_1, M_2, ..., M_{n\_res}] upper bounds for resource usage (including initial forward stopping point).
- min_reslist of floats
[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.
- algorithmstring, optional
shortest path algorithm to use. Options are “simple” or “astar”. If the input network has a negative cycle, the “simple” algorithm is automatically chosen (as the astar algorithm cannot cope).
- max_depthint, optional
depth for search of shortest simple path. Default : 1000. If the total number of simple paths is less than max_depth, then the shortest path is used.
- time_limitint, 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
- REF_callbackREFCallback, optional
Custom resource extension callback. See REFs for more details. Default : None
Raises
- Exception
if no resource feasible path is found
Notes
The input graph must have a n_res
attribute.
The edges in the graph must all have a res_cost
attribute.
See Using cspy
Example
To run the algorithm, create a GreedyElim
instance and call run.
>>> from cspy import GreedyElim
>>> from networkx import DiGraph
>>> from numpy import array
>>> G = DiGraph(directed=True, n_res=2)
>>> G.add_edge('Source', 'A', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('Source', 'B', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('A', 'C', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('B', 'C', res_cost=array([2, 1]), weight=-1)
>>> G.add_edge('C', 'D', res_cost=array([1, 1]), weight=-1)
>>> G.add_edge('D', 'E', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('D', 'F', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('F', 'Sink', res_cost=array([1, 1]), weight=1)
>>> G.add_edge('E', 'Sink', res_cost=array([1, 1]), weight=1)
>>> max_res, min_res = [5, 5], [0, 0]
>>> greedelim = GreedyElim(G, max_res, min_res)
>>> greedelim.run()
>>> print(greedelim.path)
['Source', 'A', 'C', 'D', 'E', 'Sink']