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]
      [0, 2], 
      #[-3, -1], 
      [-5, -4, 0], 
      #[5, 6, 7]
    ]

        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)

     matching_rec = %{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)


remove_type1_state = %{value_graph: graph} = zhang_state = Zhang.remove_type1_edges(graph, free_nodes, matching, remove_edge_fun)

IO.inspect(matching_rec, label: :raw_matching)
IO.inspect(BitGraph.Algorithm.Matching.Kuhn.postprocess(graph, matching_rec), label: :vertex_matching)
IO.inspect(remove_type1_state.components, label: :type1)


#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)

alias CPSolver.Model
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Constraint
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.reverse(
      [
        Constraint.new(implementation, diagonal_down),
        Constraint.new(implementation, q),
        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)