Random independent set with GenericTensorNetworks.jl

Specific Domains Graphs
1

Hi @1115, I’m looking at the GenericTensorNetworks.jl package, and I a question regarding finding a single maximum independent set Independent set problem · GenericTensorNetworks.jl, is the solution sampled uniformly at random from the possible solutions? Some tests seem to indicate no but I want to ask to make sure. If the answer is no, is there an efficient way to randomly sample a single maximum independent set?

2

I can confirm that the configuration is not uniformly sampled. If you want to get a set of uniform sampled configurations in the low energy landscape, the following page has relevant information:

1 Like
3

Thanks, I tried it out but got an error with the following MWE:

using Graphs, GenericTensorNetworks

graph = SimpleGraph()
Graphs.add_vertices!(graph, 7)
for e in [(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(3,5),(4,6),(5,7),(6,7)]
    Graphs.add_edge!(graph, e...)
end

tensor_prob = GenericTensorNetwork(IndependentSet(graph); optimizer=TreeSA())
tensor_tree = solve(tensor_prob, ConfigsMax(; tree_storage=true))[]
generate_samples(tensor_tree, 1)

Here is the error:

ERROR: MethodError: no method matching generate_samples(::CountingTropical{Float64, SumProductTree{OnehotVec{7, 2}}}, ::Int64)
The function `generate_samples` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  generate_samples(::SumProductTree{ET}, ::Int64) where ET
   @ GenericTensorNetworks ~/.julia/packages/GenericTensorNetworks/0ojFL/src/arithematics.jl:734
4

Repost the answer on GitHub:

julia> generate_samples(tensor_tree.c, 1)
1-element Vector{StaticBitVector{7, 1}}:
 1000110

The generate_samples must be applied on a SumProductTree instance.

1 Like
5

Thank you, I marked it as solved.