Sum product representation for configurations

SumProductTree can use polynomial memory to store exponential number of configurations. It is a sum-product expression tree to store ConfigEnumerator in a lazy style, where configurations can be extracted by depth first searching the tree with the Base.collect method. Although it is space efficient, it is in general not easy to extract information from it due to the exponential large configuration space. Directed sampling is one of its most important operations, with which one can get some statistic properties from it with an intermediate effort. For example, if we want to check some property of an intermediate scale graph, one can type

julia> using GenericTensorNetworks
julia> graph = random_regular_graph(70, 3){70, 105} undirected simple Int64 graph
julia> problem = GenericTensorNetwork(IndependentSet(graph); optimizer=TreeSA());
julia> tree = solve(problem, ConfigsAll(; tree_storage=true))[]+ (count = 1.6277744928945e13)
├─ + (count = 1.2388115543739e13)
│  ├─ + (count = 8.484308199241e12)
│  │  ├─ * (count = 2.702951328349e12)
│  │  │  ├─ OnehotVec{70, 2}(16, 1)
│  │  │  └─ + (count = 2.702951328349e12)
│  │  │     ├─ * (count = 8.84024819228e11)
│  │  │     │  ⋮
│  │  │     │
│  │  │     └─ + (count = 1.818926509121e12)
│  │  │        ⋮
│  │  │
│  │  └─ + (count = 5.781356870892e12)
│  │     ├─ * (count = 1.891727485686e12)
│  │     │  ├─ OnehotVec{70, 2}(26, 1)
│  │     │  └─ + (count = 1.891727485686e12)
│  │     │     ⋮
│  │     │
│  │     └─ + (count = 3.889629385206e12)
│  │        ├─ * (count = 7.652615006e10)
│  │        │  ⋮
│  │        │
│  │        └─ + (count = 3.813103235146e12)
│  │           ⋮
│  │
│  └─ * (count = 3.903807344498e12)
│     ├─ OnehotVec{70, 2}(35, 1)
│     └─ + (count = 3.903807344498e12)
│        ├─ * (count = 1.238192803073e12)
│        │  ├─ OnehotVec{70, 2}(16, 1)
│        │  └─ + (count = 1.238192803073e12)
│        │     ⋮
│        │
│        └─ + (count = 2.665614541425e12)
│           ├─ * (count = 7.70762900579e11)
│           │  ⋮
│           │
│           └─ + (count = 1.894851640846e12)
│              ⋮
│
└─ * (count = 3.889629385206e12)
   ├─ OnehotVec{70, 2}(66, 1)
   └─ * (count = 3.889629385206e12)
      ├─ * (count = 1.0)
      │  ├─ OnehotVec{70, 2}(66, 1)
      │  └─ OnehotVec{70, 2}(66, 1)
      └─ * (count = 3.889629385206e12)
         ├─ OnehotVec{70, 2}(66, 1)
         └─ + (count = 3.889629385206e12)
            ├─ * (count = 7.652615006e10)
            │  ⋮
            │
            └─ + (count = 3.813103235146e12)
               ⋮

If one wants to store these configurations, he will need a hard disk of size 256 TB! However, this sum-product binary tree structure supports efficient and unbiased direct sampling.

julia> samples = generate_samples(tree, 1000)1000-element Vector{StaticBitVector{70, 2}}:
 1101000010100001000000000100010000000001010000000010000011000000001000
 0000011000011101001000100110010000010010001000000000110000000001000000
 1010011000011001100010000100010000000000010001001000001010001011000000
 0100011010000011100001010100010000010001100000010000011000100001000000
 0000010010000101000000110101010000010000000000000000001011000100100000
 0010110000000011000110010101010000000000000000000001001000101000000000
 1000010000001001000001000100001000010110010000000010100000010000001100
 1001100010001011000000000110101100001001000000001010001100010000000000
 0001100001001011010011010100101001000000001000010000001101010000000000
 0100000011000011101100000100100001000000010010010100000000010010000000
 ⋮
 1000000001000100001100001000000100010001010011100000000100000000010000
 1000000100010000000100000000000000001110100001000001001010001000010101
 0100010000100010000110100000000000001000101010001000000000100111010000
 1010000000100000000110110000001000000110100100010000100010100010110000
 0000010010000010101000000001000000000000001001001100010100000100011100
 0001000001000000010111001000101001000100101100000000000100000000010000
 0001000000000010000001111000101100010001100010110000010101000000110001
 1000010101000100100100001001000001000001010000101100011000000000010100
 0011000010000000010100000000000100000100101011101000000010000000010100

With these samples, one can already compute useful properties like Hamming distance (see hamming_distribution) distribution. The following code visualizes this distribution with CairoMakie.

using CairoMakie
dist = hamming_distribution(samples, samples)
# bar plot
fig = Figure()
ax = Axis(fig[1, 1]; xlabel="Hamming distance", ylabel="Frequency")
barplot!(ax, 0:length(dist)-1, dist)
fig