Debugging DC.Fast
Mix.install([
{:fixpoint, path: "/Users/bokner/projects/cpsolver"},
:replbug,
# :fixpoint,
:kino
])
Logger.configure(level: :notice)
defmodule DCFast.Helper do
def visualize_value_graph(value_graph) do
{:ok, graph_content} = Graph.to_dot(value_graph)
# route_graph_content =
# Enum.reduce(0..(len - 1), route_graph_content, fn idx, acc ->
# {x, y} = Enum.at(table_coordinates, idx)
# replace_params = "[label=#{Enum.at(tables, idx)}; pos=\"#{x},#{y}!\"]"
# || "[label=#{Enum.at(tables,idx)}]"
# String.replace(acc, "[label=#{idx}]", replace_params)
# end)
dir = System.tmp_dir!()
dot_file = Path.join(dir, "value_graph.dot")
png_file = Path.join(dir, "value_graph.png")
File.write(dot_file, graph_content)
System.cmd("neato", [
"-Tpng:quartz",
dot_file,
"-o",
png_file,
"-Nfontsize=12",
#"-Nshape=square",
"-Nfontcolor=red",
"-scale=10",
"-Efontcolor=blue",
"-Efontsize=12"
])
## Render with Kino
content = File.read!(png_file)
Kino.Image.new(content, "image/png")
end
end
Zhang algo
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Variable.Interface
# alias CPSolver.Propagator
alias CPSolver.Propagator.AllDifferent.DC.Fast
alias BitGraph.Algorithms.Matching.Kuhn
alias CPSolver.Utils
alias CPSolver.Propagator
alias BitGraph.Dfs
alias CPSolver.ValueGraph
alias CPSolver.Propagator.AllDifferent.Zhang
domains = [
1, 1..2, 1..4, [1, 2, 4, 5]
#2, [-1, 0, 2], [-2, -1, 1], [-3, -2, 0]
#10, [7, 9], [8, 10]
]
vars =
#[_x0, x1, x2, x3] =
Enum.map(Enum.with_index(domains, 0), fn {d, idx} ->
Variable.new(d, name: "x#{idx}")
end)
%{
value_graph: graph,
variable_vertices: variable_vertices,
fixed_matching: fixed_matching,
reduction_callback: remove_edge_fun,
propagator_variables: variables
} = initial_state = Fast.initial_state(vars) |> tap(fn res -> IO.inspect(Map.keys(res), label: :state_keys) end)
# BitGraph.Algorithms.bipartite_matching(graph, variable_vertices)
%{free: free_nodes, matching: matching} =
Fast.find_matching(graph, variable_vertices, fixed_matching)
#
IO.inspect(Enum.map(vars, fn var -> {var.name, Utils.domain_values(var)} end),
label: :before_reduction)
%{value_graph: graph} = zhang_state = Zhang.remove_type1_edges(graph, free_nodes, matching, remove_edge_fun)
#IO.inspect(Enum.map(vars, fn var -> {var.name, Utils.domain_values(var)} end),
# label: :after_step1)
graph_step2 = zhang_state[:value_graph]
Map.new(BitGraph.vertices(graph),
fn v -> {v,
%{
in: BitGraph.in_neighbors(graph_step2, v),
out: BitGraph.out_neighbors(graph_step2, v)
}
} end)
zhang_state =
Map.put(zhang_state, :value_graph,
BitGraph.update_opts(graph,
neighbor_finder: ValueGraph.matching_neighbor_finder(graph, vars, matching, free_nodes)
))
Zhang.remove_type2_edges(zhang_state, remove_edge_fun)
#IO.inspect(BitGraph.edges(reduced_state.value_graph), label: :reduced_value_graph)
#IO.inspect(reduced_state.components, label: :components)
IO.inspect(Enum.map(vars, fn var -> {var.name, Utils.domain_values(var)} end),
label: :after_step2)
#zhang_state[:value_graph]
Filtering
domains = [1, 1..2, 1..4, [1, 2, 4, 5]]
[_x0, x1, x2, x3] =
vars =
Enum.map(Enum.with_index(domains, 0), fn {d, idx} ->
Variable.new(d, name: "x#{idx}")
end)
dc_propagator = Propagator.new(Fast, vars)
%{active?: true, state: state1} =
Propagator.filter(dc_propagator)
## Variable filtering
IO.inspect(Enum.map(vars, fn var -> {var.name, Utils.domain_values(var)} end),
label: :after_step1)
## More filtering
domain_change = Interface.fix(x2, 4)
IO.inspect(state1.components, label: :step1_components)
%{active?: false} = state2 =
#Fast.apply_changes(state1, %{2 => domain_change})
Propagator.filter(Map.put(dc_propagator, :state, state1),
changes: %{2 => domain_change})
IO.inspect(Enum.map(vars, fn var -> {var.name, Utils.domain_values(var)} end),
label: :after_step2)
Disjoint domains
alias CPSolver.Constraint.AllDifferent.DC.Fast, as: AllDifferent
alias CPSolver.Constraint
alias CPSolver.Model
alias CPSolver.IntVariable, as: Variable
domains =
[1..4, 5..8]
#List.duplicate(1..4, 4)
# [
#1, 1..2, 1..4, [1, 2, 4, 5], 6..8
#2, [-1, 0, 2], [-2, -1, 1], [-3, -2, 0]
#1..4, 1..4, 1..4, 1..4
#]
vars =
#[_x0, x1, x2, x3] =
Enum.map(Enum.with_index(domains, 0), fn {d, idx} ->
Variable.new(d, name: "x#{idx}")
end)
#Interface.fix(Enum.random(vars), 1)
model = Model.new(vars, [Constraint.new(AllDifferent, vars)])
{:ok, result} = CPSolver.solve(model)
result.statistics
Propagation
import CPSolver.Variable.View.Factory
import CPSolver.Propagator.AllDifferent.Utils
range = 1..5
## Queen positions
[x0, x1, x2, x3, x4] = q = Enum.map(range, fn i -> Variable.new(range, name: "x#{i}") end)
indexed_q = Enum.with_index(q, 1)
diagonal_down = Enum.map(indexed_q, fn {var, idx} -> linear(var, 1, -idx) end)
diagonal_up = Enum.map(indexed_q, fn {var, idx} -> linear(var, 1, idx) end)
propagators1 = Enum.map([q, diagonal_down, diagonal_up],
fn vars -> Propagator.new(Fast, vars) end
)
step_fun = fn propagators ->
IO.inspect(Enum.map(q, fn var -> Utils.domain_values(var) end), label: :domains_before_step)
Enum.flat_map(propagators |> Enum.with_index(1), fn {p, p_idx} ->
var_domains_before = Enum.map(p.args, fn var -> Utils.domain_values(var) end)
IO.inspect({"propagator #{p_idx}", p.state[:components], var_domains_before}, label: :domains_before_filtering)
%{state: state, changes: _changes} = Propagator.filter(p)
IO.inspect({"propagator #{p_idx}", state[:components],
Enum.map(p.args, fn var -> Utils.domain_values(var) end)},
label: :domains_after_filtering)
if state do
[Map.put(p, :state, state)]
else
IO.inspect({"propagator #{p_idx}", p.state.components}, label: :entailment)
[]
end
end)
|> tap(fn _ -> IO.inspect(Enum.map(q, fn var -> Utils.domain_values(var) end),
label: :domains_after_step)
end)
end
## Step 1
IO.puts("\nSTEP 1 - remove 1 from x0 - skipped\n")
#Interface.remove(x1, 1)
#propagators2=step_fun.(propagators1)
propagators2 = propagators1
## Step 2
IO.puts("\nSTEP2 - fix x0 to 2\n")
Interface.fix(x0, 2)
propagators3 = step_fun.(propagators2)
## Step 3
IO.inspect(forward_checking(diagonal_down), label: :fwc1)
IO.inspect(Enum.map(diagonal_down, fn var -> Utils.domain_values(var) end))
Interface.fix(x1, 4)
IO.inspect(forward_checking(diagonal_down), label: :fwc2)
IO.inspect(Enum.map(diagonal_down, fn var -> Utils.domain_values(var) end))
p2 = Enum.at(propagators3, 1)
#IO.inspect(p2.state.value_graph |> ValueGraph.show_graph())
propagators4 = step_fun.(propagators3)
# IO.inspect(
# (
# p = Enum.at(propagators3, 1)
# {p.state.value_graph |> ValueGraph.show_graph(),
# p.state.components
# }
# ),
# label: :propagator2)
#IO.puts("\nSTEP 3 - fix x1 to 4\n")
#propagators4 = step_fun.(propagators3)
## IO.inspect(length(propagators4), label: :propagators_after_step3)
## Step 4
##
## Pick up slack: run an extra filtering round on the same domain
## IO.puts("\nSTEP 4 - EXTRA ROUND")
propagators5 = step_fun.(propagators4)
#IO.inspect(length(propagators5))
Benchmarking
#Replbug.start("CPSolver.Propagator.AllDifferent.Zhang.reduce/_",
#silent: true, time: :timer.minutes(2), msgs: 1_000_000)
# :timer.sleep(50)
import CPSolver.Variable.View.Factory
solution_fun = fn(range, implementation) ->
## Queen positions
q = Enum.map(range, fn i -> Variable.new(range, name: "x#{i}") end)
indexed_q = Enum.with_index(q, 1)
diagonal_down = Enum.map(indexed_q, fn {var, idx} -> linear(var, 1, -idx) end)
diagonal_up = Enum.map(indexed_q, fn {var, idx} -> linear(var, 1, idx) end)
# Enum.each(Enum.with_index([5, 2, 3, 4, 1, 6]),
# fn {val, idx} ->
# Interface.fix(Enum.at(q, idx), val)
# end)
#Interface.fix(Enum.at(q, 0), 5)
#Interface.fix(Enum.at(q, 1), 3)
#Interface.fix(Enum.at(q, 2), 1)
constraints =
#Enum.shuffle(
[
Constraint.new(implementation, q),
Constraint.new(implementation, diagonal_down),
Constraint.new(implementation, diagonal_up),
]
#)
model = Model.new(q, constraints)
{:ok, res} = CPSolver.solve(model, space_threads: 8, search: {:first_fail, :indomain_min})
res.status == :all_solutions && res[:statistics] || throw(res.status)
end
solution_fun.(1..8, CPSolver.Constraint.AllDifferent.DC.Fast)
#Enum.map(res.solutions, fn s -> {CPSolver.Examples.Queens.check_solution(s), s} end)
#solution_fun.(1..8, CPSolver.Constraint.AllDifferent.DC)[:elapsed_time]
repeats = 100
dc_benchmark = Enum.map(1..repeats, fn _ ->
solution_fun.(1..8, CPSolver.Constraint.AllDifferent.DC.Fast)[:elapsed_time]
end)
|> Enum.sum()
|> Kernel.div(repeats)