|
1
|
|
mutable struct ElementaryPathAlgosSolver <: ElementaryPathSolver
|
|
2
|
|
graph::SimpleDiGraph
|
|
3
|
|
source::Int
|
|
4
|
|
destination::Int
|
|
5
|
|
|
|
6
|
|
function ElementaryPathAlgosSolver()
|
|
7
|
1
|
return new(DiGraph(0), -1, -1)
|
|
8
|
|
end
|
|
9
|
|
end
|
|
10
|
|
|
|
11
|
|
function build!(solver::ElementaryPathAlgosSolver, graph::SimpleDiGraph, source::Int, destination::Int)
|
|
12
|
1
|
solver.graph = graph
|
|
13
|
1
|
solver.source = source
|
|
14
|
1
|
solver.destination = destination
|
|
15
|
|
end
|
|
16
|
|
|
|
17
|
0
|
has_lp_formulation(::ElementaryPathAlgosSolver) = false
|
|
18
|
|
|
|
19
|
1
|
_tuple_dict_to_edge_dict(d::Dict{Tuple{Int, Int}, T}) where T =
|
|
20
|
|
Dict(Edge(k...) => v for (k, v) in d)
|
|
21
|
|
|
|
22
|
|
function solve_linear(solver::ElementaryPathAlgosSolver, reward::Dict{Tuple{Int, Int}, Float64})
|
|
23
|
1
|
i = ElementaryPathInstance(solver.graph, _tuple_dict_to_edge_dict(reward),
|
|
24
|
|
solver.source, solver.destination)
|
|
25
|
1
|
s = lp_dp(i).path
|
|
26
|
1
|
return [(src(e), dst(e)) for e in s]
|
|
27
|
|
end
|
|
28
|
|
|
|
29
|
|
function solve_budgeted_linear(solver::ElementaryPathAlgosSolver,
|
|
30
|
|
reward::Dict{Tuple{Int, Int}, Float64},
|
|
31
|
|
weights::Dict{Tuple{Int, Int}, Int},
|
|
32
|
|
budget::Int)
|
|
33
|
1
|
i = BudgetedElementaryPathInstance(solver.graph,
|
|
34
|
|
_tuple_dict_to_edge_dict(reward), _tuple_dict_to_edge_dict(weights),
|
|
35
|
|
solver.source, solver.destination, budget=budget)
|
|
36
|
1
|
s = budgeted_lp_dp(i).path
|
|
37
|
1
|
return [(src(e), dst(e)) for e in s]
|
|
38
|
|
end
|
|
39
|
|
|
|
40
|
|
function solve_all_budgeted_linear(solver::ElementaryPathAlgosSolver,
|
|
41
|
|
reward::Dict{Tuple{Int, Int}, Float64},
|
|
42
|
|
weights::Dict{Tuple{Int, Int}, Int},
|
|
43
|
|
max_budget::Int)
|
|
44
|
0
|
i = BudgetedElementaryPathInstance(solver.graph,
|
|
45
|
|
_tuple_dict_to_edge_dict(reward), _tuple_dict_to_edge_dict(weights),
|
|
46
|
|
solver.source, solver.destination, budget=max_budget)
|
|
47
|
0
|
return paths_all_budgets_as_tuples(budgeted_lp_dp(i), max_budget)
|
|
48
|
|
end
|
dourouc05