Packages
fixpoint
0.19.1
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/examples/graph_coloring.ex
defmodule CPSolver.Examples.GraphColoring do
alias CPSolver.Constraint.NotEqual
alias CPSolver.IntVariable
alias CPSolver.Model
def solve(instance, solver_opts \\ [])
def solve(instance, solver_opts) when is_binary(instance) do
instance
|> model()
|> solve(solver_opts)
end
def solve(data, solver_opts) do
{:ok, _solver} =
CPSolver.solve_async(model(data), solver_opts)
|> tap(fn _ -> Process.sleep(100) end)
end
def model(data) when is_binary(data) do
parse_instance(data)
|> model()
end
def model(data) when is_map(data) do
color_vars = Enum.map(1..data.vertices, fn _idx -> IntVariable.new(1..data.max_color) end)
edge_color_constraints =
Enum.map(data.edges, fn [v1, v2] ->
NotEqual.new(Enum.at(color_vars, v1), Enum.at(color_vars, v2))
end)
Model.new(color_vars, edge_color_constraints)
end
defp parse_instance(instance) do
[header | edge_lines] = File.read!(instance) |> String.split("\n", trim: true)
[v, _e, max_color] = header |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1)
edges =
Enum.map(edge_lines, fn e -> String.split(e, " ") |> Enum.map(&String.to_integer/1) end)
%{vertices: v, edges: edges, max_color: max_color}
end
def check_solution(colors, instance) when is_list(colors) do
graph = parse_instance(instance)
Enum.all?(graph.edges, fn [v1, v2] -> Enum.at(colors, v1) != Enum.at(colors, v2) end)
end
end