Weighted problems

Let us use the maximum independent set problem on Petersen graph as an example.

using GenericTensorNetworks, GenericTensorNetworks.ProblemReductions, Graphs

graph = Graphs.smallgraph(:petersen)
{10, 15} undirected simple Int64 graph

The following code constructs a weighted MIS problem instance.

problem = GenericTensorNetwork(IndependentSet(graph, collect(1:10)));
GenericTensorNetworks.weights(problem)
10-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

The tensor labels that associated with the weights can be accessed by

ProblemReductions.local_solution_spec(problem.problem)
10-element Vector{ProblemReductions.LocalSolutionSpec{Int64, Symbol}}:
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([1], :num_vertex, 1)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([2], :num_vertex, 2)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([3], :num_vertex, 3)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([4], :num_vertex, 4)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([5], :num_vertex, 5)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([6], :num_vertex, 6)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([7], :num_vertex, 7)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([8], :num_vertex, 8)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([9], :num_vertex, 9)
 ProblemReductions.LocalSolutionSpec{Int64, Symbol}([10], :num_vertex, 10)

Here, the weights keyword argument can be a vector for weighted graphs or UnitWeight() for unweighted graphs. Most solution space properties work for unweighted graphs also work for the weighted graphs. For example, the maximum independent set can be found as follows.

max_config_weighted = solve(problem, SingleConfigMax())[]
(24.0, ConfigSampler{10, 1, 1}(0100100110))ₜ

Let us visualize the solution.

rot15(a, b, i::Int) = cos(2i*π/5)*a + sin(2i*π/5)*b, cos(2i*π/5)*b - sin(2i*π/5)*a
locations = [[rot15(0.0, 60.0, i) for i=0:4]..., [rot15(0.0, 30, i) for i=0:4]...]
show_graph(graph, locations; format=:svg, vertex_colors=
          [iszero(max_config_weighted.c.data[i]) ? "white" : "red" for i=1:nv(graph)])

The only solution space property that can not be defined for general real-weighted (not including integer-weighted) graphs is the GraphPolynomial.

For the weighted MIS problem, a useful solution space property is the "energy spectrum", i.e. the largest several configurations and their weights. We can use the solution space property is SizeMax(10) to compute the largest 10 weights.

spectrum = solve(problem, SizeMax(10))[]
ExtendedTropical{10, Tropical{Float64}}(Tropical{Float64}[20.0ₜ, 20.0ₜ, 20.0ₜ, 21.0ₜ, 21.0ₜ, 22.0ₜ, 22.0ₜ, 22.0ₜ, 23.0ₜ, 24.0ₜ])

The return value has type ExtendedTropical, which contains one field orders.

spectrum.orders
10-element Vector{Tropical{Float64}}:
 20.0ₜ
 20.0ₜ
 20.0ₜ
 21.0ₜ
 21.0ₜ
 22.0ₜ
 22.0ₜ
 22.0ₜ
 23.0ₜ
 24.0ₜ

We can see the order is a vector of Tropical numbers. Similarly, we can get weighted independent sets with maximum 5 sizes as follows.

max5_configs = read_config(solve(problem, SingleConfigMax(5))[])
5-element Vector{StaticBitVector{10, 1}}:
 0101010001
 0010000011
 0000100110
 1010000011
 0100100110

The return value of solve has type ExtendedTropical, but this time the element type of orders has been changed to CountingTropical{Float64,ConfigSampler}. Let us visually check these configurations

show_configs(graph, locations, [max5_configs[j] for i=1:1, j=1:5]; padding_left=20)
Example block output

This page was generated using Literate.jl.