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> graph = random_regular_graph(70, 3)
ERROR: UndefVarError: `random_regular_graph` not defined
julia> problem = GenericTensorNetwork(IndependentSet(graph); optimizer=TreeSA());
ERROR: UndefVarError: `IndependentSet` not defined
julia> tree = solve(problem, ConfigsAll(; tree_storage=true))[]
ERROR: UndefVarError: `problem` not defined
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)
ERROR: UndefVarError: `generate_samples` not defined
With these samples, one can already compute useful properties like Hamming distance (see hamming_distribution
) distribution.
julia> using UnicodePlots
ERROR: ArgumentError: Package UnicodePlots not found in current path. - Run `import Pkg; Pkg.add("UnicodePlots")` to install the UnicodePlots package.
julia> lineplot(hamming_distribution(samples, samples))
ERROR: UndefVarError: `hamming_distribution` not defined
Here, the $x$-axis is the Hamming distance and the $y$-axis is the counting of pair-wise Hamming distances.