Saving and Loading Solutions
Overview
When working with large solution spaces, it's often necessary to save results to disk for later analysis or to share with other tools. This example demonstrates how to:
- Save and load configuration enumerators
- Save and load sum-product trees
- Export solutions for use in Python
We'll use the Maximum Independent Set problem on the Petersen graph as our example.
using GenericTensorNetworks, Graphs
Create our problem instance
problem = GenericTensorNetwork(IndependentSet(Graphs.smallgraph(:petersen)))
GenericTensorNetwork{IndependentSet{SimpleGraph{Int64}, Int64, UnitWeight}, OMEinsum.DynamicNestedEinsum{Int64}, Int64}
- open vertices: Int64[]
- fixed vertices: Dict{Int64, Int64}()
- contraction time = 2^8.044, space = 2^4.0, read-write = 2^8.758
Saving Configuration Enumerators
First, let's enumerate all independent sets
all_independent_sets = solve(problem, ConfigsAll())[]
{0000100110, 1000000110, 0000000110, 0000101100, 1000001100, 0000001100, 0000100100, 1000000100, 0000000100, 0010100010, 1010000010, 0010000010, 0010101000, 1010001000, 0010001000, 0010100000, 1010000000, 0010000000, 0000100010, 1000000010, 0000000010, 0000101000, 1000001000, 0000001000, 0000100000, 1000000000, 0000000000, 0100100110, 0100000110, 0100100100, 0100000100, 0100100010, 0100000010, 0100100000, 0100000000, 0010111000, 0010011000, 0010110000, 0010010000, 0000111000, 0000011000, 0000110000, 0000010000, 0100110000, 0100010000, 1001001100, 0001001100, 1001000100, 0001000100, 1001001000, 0001001000, 1001000000, 0001000000, 0101000100, 0101000000, 0001011000, 0001010000, 0101010000, 1010000011, 0010000011, 1010000001, 0010000001, 1000000011, 0000000011, 1000000001, 0000000001, 0100000011, 0100000001, 0010010001, 0000010001, 0100010001, 1001000001, 0001000001, 0101000001, 0001010001, 0101010001}
The result is a ConfigEnumerator
instance containing all valid configurations. We can save this to disk and load it later:
Create a temporary file for demonstration
filename = tempname()
"/tmp/jl_9udqRcxabq"
Save configurations in binary format (most efficient)
save_configs(filename, all_independent_sets; format=:binary)
608
Load configurations from the saved file
loaded_sets = load_configs(filename; format=:binary, bitlength=10)
{0000100110, 1000000110, 0000000110, 0000101100, 1000001100, 0000001100, 0000100100, 1000000100, 0000000100, 0010100010, 1010000010, 0010000010, 0010101000, 1010001000, 0010001000, 0010100000, 1010000000, 0010000000, 0000100010, 1000000010, 0000000010, 0000101000, 1000001000, 0000001000, 0000100000, 1000000000, 0000000000, 0100100110, 0100000110, 0100100100, 0100000100, 0100100010, 0100000010, 0100100000, 0100000000, 0010111000, 0010011000, 0010110000, 0010010000, 0000111000, 0000011000, 0000110000, 0000010000, 0100110000, 0100010000, 1001001100, 0001001100, 1001000100, 0001000100, 1001001000, 0001001000, 1001000000, 0001000000, 0101000100, 0101000000, 0001011000, 0001010000, 0101010000, 1010000011, 0010000011, 1010000001, 0010000001, 1000000011, 0000000011, 1000000001, 0000000001, 0100000011, 0100000001, 0010010001, 0000010001, 0100010001, 1001000001, 0001000001, 0101000001, 0001010001, 0101010001}
When loading data in binary format, you must specify the bitlength
parameter, which represents the number of bits used for each configuration. In this example, the Petersen graph has 10 vertices, so we use bitlength=10
.
Saving Sum-Product Trees
For larger solution spaces, the SumProductTree
format is more memory-efficient. It stores solutions in a compressed tree structure:
Generate solutions using tree storage
all_independent_sets_tree = solve(problem, ConfigsAll(; tree_storage=true))[]
+ (count = 76.0)
├─ + (count = 75.0)
│ ├─ + (count = 74.0)
│ │ ├─ + (count = 73.0)
│ │ │ ├─ + (count = 71.0)
│ │ │ │ ├─ + (count = 70.0)
│ │ │ │ │ ⋮
│ │ │ │ │
│ │ │ │ └─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 2.0)
│ │ │ ├─ * (count = 2.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ * (count = 1.0)
│ │ ├─ * (count = 1.0)
│ │ │ ├─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ * (count = 1.0)
│ │ ├─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ OnehotVec{10, 2}(10, 1)
│ └─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ├─ * (count = 1.0)
│ │ │ ├─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ * (count = 1.0)
│ │ ├─ OnehotVec{10, 2}(10, 1)
│ │ └─ * (count = 1.0)
│ │ ⋮
│ │
│ └─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ├─ OnehotVec{10, 2}(4, 1)
│ │ └─ OnehotVec{10, 2}(4, 1)
│ └─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(6, 1)
│ └─ OnehotVec{10, 2}(10, 1)
└─ * (count = 1.0)
├─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ├─ * (count = 1.0)
│ │ │ ├─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ * (count = 1.0)
│ │ ├─ OnehotVec{10, 2}(4, 1)
│ │ └─ * (count = 1.0)
│ │ ⋮
│ │
│ └─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ├─ OnehotVec{10, 2}(2, 1)
│ │ └─ OnehotVec{10, 2}(10, 1)
│ └─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(4, 1)
│ └─ OnehotVec{10, 2}(6, 1)
└─ * (count = 1.0)
├─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(2, 1)
│ └─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(4, 1)
│ └─ OnehotVec{10, 2}(4, 1)
└─ * (count = 1.0)
├─ OnehotVec{10, 2}(6, 1)
└─ OnehotVec{10, 2}(10, 1)
Save the sum-product tree
save_sumproduct(filename, all_independent_sets_tree)
Load the sum-product tree
loaded_sets_tree = load_sumproduct(filename)
+ (count = 76.0)
├─ + (count = 75.0)
│ ├─ + (count = 74.0)
│ │ ├─ + (count = 73.0)
│ │ │ ├─ + (count = 71.0)
│ │ │ │ ├─ + (count = 70.0)
│ │ │ │ │ ⋮
│ │ │ │ │
│ │ │ │ └─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 2.0)
│ │ │ ├─ * (count = 2.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ * (count = 1.0)
│ │ ├─ * (count = 1.0)
│ │ │ ├─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ * (count = 1.0)
│ │ ├─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ OnehotVec{10, 2}(10, 1)
│ └─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ├─ * (count = 1.0)
│ │ │ ├─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ * (count = 1.0)
│ │ ├─ OnehotVec{10, 2}(10, 1)
│ │ └─ * (count = 1.0)
│ │ ⋮
│ │
│ └─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ├─ OnehotVec{10, 2}(4, 1)
│ │ └─ OnehotVec{10, 2}(4, 1)
│ └─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(6, 1)
│ └─ OnehotVec{10, 2}(10, 1)
└─ * (count = 1.0)
├─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ├─ * (count = 1.0)
│ │ │ ├─ * (count = 1.0)
│ │ │ │ ⋮
│ │ │ │
│ │ │ └─ * (count = 1.0)
│ │ │ ⋮
│ │ │
│ │ └─ * (count = 1.0)
│ │ ├─ OnehotVec{10, 2}(4, 1)
│ │ └─ * (count = 1.0)
│ │ ⋮
│ │
│ └─ * (count = 1.0)
│ ├─ * (count = 1.0)
│ │ ├─ OnehotVec{10, 2}(2, 1)
│ │ └─ OnehotVec{10, 2}(10, 1)
│ └─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(4, 1)
│ └─ OnehotVec{10, 2}(6, 1)
└─ * (count = 1.0)
├─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(2, 1)
│ └─ * (count = 1.0)
│ ├─ OnehotVec{10, 2}(4, 1)
│ └─ OnehotVec{10, 2}(4, 1)
└─ * (count = 1.0)
├─ OnehotVec{10, 2}(6, 1)
└─ OnehotVec{10, 2}(10, 1)
Interoperability with Python
The binary format can be loaded in Python for further analysis. Here's a Python function to load and unpack the solutions as a NumPy array:
import numpy as np
def loadfile(filename: str, bitlength: int):
"""
Load binary configuration data saved by GenericTensorNetworks.jl
Parameters:
-----------
filename : str
Path to the binary file
bitlength : int
Number of bits per configuration (typically number of vertices)
Returns:
--------
numpy.ndarray
2D array where each row is a configuration
"""
C = int(np.ceil(bitlength / 64))
arr = np.fromfile(filename, dtype="uint8")
# Transform from big endian to little endian
res = np.unpackbits(arr).reshape(-1, C, 8, 8)[:,::-1,::-1,:]
res = res.reshape(-1, C*64)[:, :(64*C-bitlength)-1:-1]
print(f"Number of solutions: {len(res)}")
return res # in big endian format
# Example usage:
solutions = loadfile(filename, 10)
Additional Resources
For more examples of working with solution spaces:
- See the Maximal Independent Set Problem section for examples of:
- Using
SizeMin
to find minimum set sizes - Using
CountingMin
to count minimum set sizes - Using
SingleConfigMin
to find one minimum solution - Using
ConfigsMin
to enumerate all minimum solutions
- Using
This page was generated using Literate.jl.