Packages
fixpoint
0.18.2
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
test/variables/value_graph_test.exs
defmodule CPSolverTest.Utils.ValueGraph do
use ExUnit.Case
describe "Value Graph" do
alias CPSolver.ValueGraph
alias CPSolver.IntVariable, as: Variable
alias CPSolver.Variable.Interface
import CPSolver.Test.Helpers
test "build" do
num_variables = 4
domain = 1..5
variables = Enum.map(1..num_variables, fn idx -> Variable.new(domain, name: "x#{idx}") end)
%{value_graph: graph, left_partition: _left_partition} = ValueGraph.build(variables)
assert ValueGraph.get_variable_count(graph) == num_variables
## 4 variables and 5 values
assert BitGraph.num_vertices(graph) == 9
## No adjacency table allocation
refute get_in(graph, [:adjacency, :bit_vector])
## Ignore fixed variables
variables = Enum.map([1, 1..2, [1, 2, 4, 5], 6], fn d -> Variable.new(d) end)
%{value_graph: graph, left_partition: left_partition} = ValueGraph.build(variables,
ignore_fixed_variables: true)
assert 1 in left_partition
assert 2 in left_partition
# fixed variables are excluded
refute 0 in left_partition
refute 3 in left_partition
# Value graph does not have fixed variables and fixed values not shared with other variables
refute Enum.any?([0, 3, {:value, 1}, {:value, 6}],
fn vertex ->
BitGraph.get_vertex(graph, vertex)
end)
end
test "default neighbor finder" do
num_variables = 4
domain = 1..5
variables = Enum.map(1..num_variables, fn idx -> Variable.new(domain, name: "x#{idx}") end)
%{value_graph: graph, left_partition: _left_partition} = ValueGraph.build(variables)
## For 'variable' vertices, all neighbors are 'out' vertices {:value, domain_value}.
## The domain of variable represented by 'variable' vertex is covered by it's neighbors.
assert Enum.all?(0..(num_variables - 1), fn var_idx ->
variable_vertex = var_idx
BitGraph.out_degree(graph, variable_vertex) == Range.size(domain) &&
BitGraph.in_degree(graph, variable_vertex) == 0 &&
BitGraph.out_neighbors(graph, variable_vertex) ==
MapSet.new(domain, fn val -> {:value, val} end) &&
Enum.empty?(
BitGraph.in_neighbors(graph, variable_vertex)
)
end)
## For 'value' vertices, all neighbors are 'in' vertices `variable_index`
## The number of neighbors corresponds to the number of variables currently having the value
## in their domain
assert Enum.all?(domain, fn value ->
value_vertex = {:value, value}
BitGraph.in_degree(graph, value_vertex) == num_variables &&
BitGraph.out_degree(graph, value_vertex) == 0 &&
BitGraph.in_neighbors(graph, value_vertex) ==
MapSet.new(0..num_variables - 1) &&
Enum.empty?(
BitGraph.out_neighbors(graph, value_vertex)
)
end)
## Remove value from the domain of variable
some_value = Enum.random(domain)
some_variable_index = Enum.random(0..(num_variables - 1))
Interface.remove(Enum.at(variables, some_variable_index), some_value)
## The 'value' vertex is removed from neighbors of the 'variable' vertex
assert BitGraph.out_neighbors(graph, some_variable_index) ==
MapSet.new(List.delete(Range.to_list(domain), some_value), fn val ->
{:value, val}
end)
# ... and vice versa
assert BitGraph.in_neighbors(graph, {:value, some_value}) ==
MapSet.new(
List.delete(Range.to_list(0..(num_variables - 1)), some_variable_index)
)
## ... nothing changes otherwise
assert Enum.empty?(
BitGraph.out_neighbors(graph, {:value, some_value})
)
assert Enum.empty?(
BitGraph.in_neighbors(graph, some_variable_index)
)
end
test "'matching' neighbor_finder" do
domain = 1..5
num_variables = 4
variables = Enum.map(1..num_variables, fn idx -> Variable.new(domain, name: "x#{idx}") end)
%{value_graph: graph, left_partition: left_partition} = ValueGraph.build(variables)
matching =
BitGraph.bipartite_matching(graph, left_partition: left_partition)
assert MapSet.size(matching.free) == 1
## Matching is valid
# 4 variables in the matching map
assert map_size(matching.matching) == 4
# 4 values in reverse matching map
assert map_size(Map.new(matching.matching, fn {var, value} -> {value, var} end)) == 4
## Remove all edges to free node
{:value, free_node_value} = free_vertex = MapSet.to_list(matching.free) |> hd()
## free node is in the graph before edge removals
assert BitGraph.get_vertex(graph, free_vertex)
graph = Enum.reduce(0..num_variables-1, graph, fn var_idx, graph_acc ->
ValueGraph.delete_edge(graph_acc, var_idx, BitGraph.V.get_vertex_index(graph, free_vertex), variables)
end)
## Free node is no longer in the graph
refute BitGraph.get_vertex(graph, free_vertex)
## Free node value is no longer in variable's domains
refute Enum.any?(variables, fn var ->
Interface.contains?(var, free_node_value)
end)
matching2 =
BitGraph.Algorithm.bipartite_matching(graph, left_partition: left_partition,
process_mode: :preprocess)
## No free nodes
assert Enum.empty?(matching2.free)
## Matching is valid
# 4 variables in the matching map
assert map_size(matching2.matching) == 4
matching_neighbor_finder =
ValueGraph.matching_neighbor_finder(graph, variables, matching2.matching, matching2.free)
matching_graph = BitGraph.set_neighbor_finder(graph, matching_neighbor_finder)
assert Enum.all?(matching2.matching, fn {var_vertex, value_vertex} ->
iterables_equal?(BitGraph.V.out_neighbors(matching_graph, value_vertex), [var_vertex])
&& iterables_equal?(BitGraph.V.in_neighbors(matching_graph, var_vertex), [value_vertex])
&& iterables_equal?(BitGraph.V.out_neighbors(matching_graph, var_vertex),
Map.values(matching2.matching) -- [value_vertex])
&& iterables_equal?(BitGraph.V.in_neighbors(matching_graph, value_vertex),
Map.keys(matching2.matching) -- [var_vertex])
end)
## Original graph has edges from variables to values
## hence, not strongly connected
refute BitGraph.strongly_connected?(graph)
## With matching edges oriented from values to variables,
## the graph becomes a cycle.
matching_neighbor_finder =
ValueGraph.matching_neighbor_finder(graph, variables, matching2.matching, matching2.free)
assert BitGraph.strongly_connected?(graph,
neighbor_finder: matching_neighbor_finder
)
end
test "matching neighbor finder with fixed variables" do
domain = 1..3
variables = Enum.map(domain, fn idx -> Variable.new(domain, name: "x#{idx}") end)
%{value_graph: value_graph, left_partition: variable_vertices} = ValueGraph.build(variables)
%{matching: matching, free: free_nodes}
= BitGraph.Algorithm.bipartite_matching(value_graph, left_partition: variable_vertices,
process_mode: :preprocess)
var_index = 0
## Fix a variable...
:fixed = Interface.fix(Enum.at(variables, var_index), 1)
fixed_variable_vertex_index = ValueGraph.variable_vertex_index(var_index)
matched_value_vertex_index = Map.get(matching, fixed_variable_vertex_index)
reduced_matching = Map.delete(matching, fixed_variable_vertex_index)
## Create a 'matching' graph with reduced matching
neighbor_finder = ValueGraph.matching_neighbor_finder(value_graph, variables, reduced_matching, free_nodes)
matching_graph = BitGraph.update_opts(value_graph, neighbor_finder: neighbor_finder)
## 'Variable' vertices that are not part of (reduced) matching are isolated
assert BitGraph.degree(matching_graph, var_index) == 0
## The 'fixed value' vertex is still connected to 'non-fixed' variable vertices
assert BitGraph.V.in_degree(matching_graph, matched_value_vertex_index) == 2
## No out-neighbors for the 'fixed value' vertex.
assert BitGraph.out_degree(matching_graph, matched_value_vertex_index) == 0
refute fixed_variable_vertex_index in
(BitGraph.V.in_neighbors(matching_graph, matched_value_vertex_index) |> Iter.Iterable.to_list())
end
end
end