References

solve(problem, property; usecuda=false, T=Float64)

Solving a certain property of a graph problem.

Positional Arguments

• problem is the graph problem with tensor network information,

• property is string specifying the task. Using the maximum independent set problem as an example, it can be one of

  • PartitionFunction() for computing the partition function,

  • SizeMax(k=Single) for finding maximum-$k$ set sizes,

  • SizeMin(k=Single) for finding minimum-$k$ set sizes,

  • CountingMax(k=Single) for counting configurations with maximum-$k$ sizes,

  • CountingMin(k=Single) for counting configurations with minimum-$k$ sizes,

  • CountingAll() for counting all configurations,

  • PartitionFunction() for counting all configurations,

  • GraphPolynomial(; method=:finitefield, kwargs...) for evaluating the graph polynomial,

  • SingleConfigMax(k=Single; bounded=false) for finding one maximum-$k$ configuration for each size,

  • SingleConfigMin(k=Single; bounded=false) for finding one minimum-$k$ configuration for each size,

  • ConfigsMax(k=Single; bounded=true, tree_storage=false) for enumerating configurations with maximum-$k$ sizes,

  • ConfigsMin(k=Single; bounded=true, tree_storage=false) for enumerating configurations with minimum-$k$ sizes,

  • ConfigsAll(; tree_storage=false) for enumerating all configurations,

Keyword arguments

• usecuda is a switch to use CUDA (if possible), user need to call statement using CUDA before turning on this switch.
• T is the "base" element type, sometimes can be used to reduce the memory cost.

struct GenericTensorNetwork{CFG, CT, LT}

GenericTensorNetwork(problem::GraphProblem; openvertices=(), fixedvertices=Dict(), optimizer=GreedyMethod())

The generic tensor network that generated from a GraphProblem.

Positional arguments

• problem is the graph problem.
• code is the tensor network contraction code.
• fixedvertices is a dictionary specifying the fixed dimensions.

GraphProblem

The abstract base type of graph problems.

struct IndependentSet{WT} <: GraphProblem

The independent set problem in graph theory.

Positional arguments

• graph is the problem graph.
• weights are associated with the vertices of the graph, default to UnitWeight().

Examples

julia> using GenericTensorNetworks, Graphs

julia> problem = IndependentSet(smallgraph(:petersen));

julia> net = GenericTensorNetwork(problem);

julia> solve(net, ConfigsMax())
0-dimensional Array{CountingTropical{Float64, ConfigEnumerator{10, 1, 1}}, 0}:
(4.0, {1010000011, 1001001100, 0100100110, 0101010001, 0010111000})ₜ

struct MaximalIS{WT<:Union{UnitWeight, Vector}} <: GraphProblem

The maximal independent set problem. In the constructor, weights are the weights of vertices.

Positional arguments

• graph is the problem graph.
• weights are associated with the vertices of the graph.

struct Matching{WT<:Union{UnitWeight, Vector}} <: GraphProblem

The Vertex matching problem.

Positional arguments

• graph is the problem graph.
• weights are associated with the edges of the graph.

struct Coloring{K, WT<:Union{UnitWeight, Vector}} <: GraphProblem

Coloring{K}(graph; weights=UnitWeight())

The Vertex Coloring problem.

Positional arguments

• graph is the problem graph.
• weights are associated with the edges of the graph, default to UnitWeight().

struct DominatingSet{WT<:Union{UnitWeight, Vector}} <: GraphProblem

DominatingSet(graph; weights=UnitWeight())

The dominating set problem.

Positional arguments

• graph is the problem graph.
• weights are associated with the vertices of the graph, default to UnitWeight().

struct SpinGlass{WT<:Union{UnitWeight, Vector}} <: GraphProblem

SpinGlass(n, cliques; weights=UnitWeight())
SpinGlass(graph::SimpleGraph, J=UnitWeight(), h=ZeroWeight())

The spin-glass problem.

Positional arguments

• n is the number of spins.
• cliques is a vector of cliques, each being a vector of vertices (integers). For simple graph, it is a vector of edges.
• weights are associated with the cliques.

struct MaxCut{WT1<:Union{UnitWeight, Vector}, WT2<:Union{ZeroWeight, Vector}} <: GraphProblem

The cutting problem.

Positional arguments

• graph is the problem graph.
• edge_weights are associated with the edges of the graph.
• vertex_weights are associated with the vertices of the graph.

struct PaintShop{LT} <: GraphProblem

The binary paint shop problem.

Positional arguments

• sequence is a vector of symbols, each symbol is associated with a color.
• isfirst is a vector of boolean numbers, indicating whether the symbol is the first appearance in the sequence.

Examples

One can encode the paint shop problem abaccb as the following

julia> syms = collect("abaccb");

julia> pb = GenericTensorNetwork(PaintShop(syms));

julia> solve(pb, SizeMin())[]
2.0ₜ

julia> solve(pb, ConfigsMin())[].c.data
2-element Vector{StaticBitVector{3, 1}}:
 100
 011

In our definition, we find the maximum number of unchanged color in this sequence, i.e. (n-1) - (minimum number of color changes) In the output of maximum configurations, the two configurations are defined on 5 bonds i.e. pairs of (i, i+1), 0 means color changed, while 1 means color not changed. If we denote two "colors" as r and b, then the optimal painting is rbbbrr or brrrbb, both change the colors twice.

struct Satisfiability{T, WT<:Union{UnitWeight, Vector}} <: GraphProblem

The satisfiability problem.

Positional arguments

• cnf is a conjunctive normal form (CNF) for specifying the satisfiability problems.
• weights are associated with clauses.

Examples

julia> @bools x y z a b c

julia> c1 = x ∨ ¬y
x ∨ ¬y

julia> c2 = c ∨ (¬a ∨ b)
c ∨ ¬a ∨ b

julia> c3 = (z ∨ ¬a) ∨ y
z ∨ ¬a ∨ y

julia> c4 = (c ∨ z) ∨ ¬b
c ∨ z ∨ ¬b

julia> cnf = (c1 ∧ c4) ∧ (c2 ∧ c3)
(x ∨ ¬y) ∧ (c ∨ z ∨ ¬b) ∧ (c ∨ ¬a ∨ b) ∧ (z ∨ ¬a ∨ y)

julia> gp = GenericTensorNetwork(Satisfiability(cnf));

julia> solve(gp, SizeMax())[]
4.0ₜ

struct SetCovering{ET, WT<:Union{UnitWeight, Vector}} <: GraphProblem

The set covering problem.

Positional arguments

• sets is a vector of vectors, each set is associated with a weight specified in weights.
• weights are associated with sets.

Examples

julia> sets = [[1, 2, 5], [1, 3], [2, 4], [3, 6], [2, 3, 6]];  # each set is a vertex

julia> gp = GenericTensorNetwork(SetCovering(sets));

julia> res = solve(gp, ConfigsMin())[]
(3.0, {10110, 10101})ₜ

struct SetPacking{ET, WT<:Union{UnitWeight, Vector}} <: GraphProblem

The set packing problem, a generalization of independent set problem to hypergraphs.

Positional arguments

• sets is a vector of vectors, each set is associated with a weight specified in weights.
• weights are associated with sets.

Examples

julia> sets = [[1, 2, 5], [1, 3], [2, 4], [3, 6], [2, 3, 6]];  # each set is a vertex

julia> gp = GenericTensorNetwork(SetPacking(sets));

julia> res = solve(gp, ConfigsMax())[]
(2.0, {00110, 10010, 01100})ₜ

struct OpenPitMining{ET} <: GraphProblem

The open pit mining problem. This problem can be solved in polynomial time with the pseudoflow algorithm.

Positional arguments

• rewards is a matrix of rewards.
• blocks are the locations of the blocks.

Example

julia> rewards =  [-4  -7  -7  -17  -7  -26;
         0  39  -7   -7  -4    0;
         0   0   1    8   0    0;
         0   0   0    0   0    0;
         0   0   0    0   0    0;
         0   0   0    0   0    0];

julia> gp = GenericTensorNetwork(OpenPitMining(rewards));

julia> res = solve(gp, SingleConfigMax())[]
(21.0, ConfigSampler{12, 1, 1}(111000100000))ₜ

julia> is_valid_mining(rewards, res.c.data)
true

julia> print_mining(rewards, res.c.data)
     -4      -7      -7     -17      -7     -26 
      ◼      39      -7      -7      -4       ◼ 
      ◼       ◼       1       8       ◼       ◼ 
      ◼       ◼       ◼       ◼       ◼       ◼ 
      ◼       ◼       ◼       ◼       ◼       ◼ 
      ◼       ◼       ◼       ◼       ◼       ◼

You will the the mining is printed as green in an colored REPL.

generate_tensors(func, problem::GenericTensorNetwork)

Generate a vector of tensors as the inputs of the tensor network contraction code problem.code. func is a function to customize the tensors. func(symbol) returns a vector of elements, the length of which is same as the number of flavors.

Example

The following code gives your the maximum independent set size

julia> using Graphs, GenericTensorNetworks

julia> gp = GenericTensorNetwork(IndependentSet(smallgraph(:petersen)));

julia> getixsv(gp.code)
25-element Vector{Vector{Int64}}:
 [1]
 [2]
 [3]
 [4]
 [5]
 [6]
 [7]
 [8]
 [9]
 [10]
 ⋮
 [3, 8]
 [4, 5]
 [4, 9]
 [5, 10]
 [6, 8]
 [6, 9]
 [7, 9]
 [7, 10]
 [8, 10]

julia> gp.code(GenericTensorNetworks.generate_tensors(Tropical(1.0), gp)...)
0-dimensional Array{Tropical{Float64}, 0}:
4.0ₜ

labels(problem::GraphProblem) -> Vector
labels(problem::GenericTensorNetwork) -> Vector

The labels of a graph problem is defined as the degrees of freedoms in the graph problem. e.g. for the maximum independent set problems, they are the indices of vertices: 1, 2, 3..., while for the max cut problem, they are the edges.

energy_terms(problem::GraphProblem) -> Vector
energy_terms(problem::GenericTensorNetwork) -> Vector

The energy terms of a graph problem is defined as the tensor labels that carrying local energies (or weights) in the graph problem.

flavors(::Type{<:GraphProblem}) -> Vector
flavors(::Type{<:GenericTensorNetwork}) -> Vector

It returns a vector of integers as the flavors of a degree of freedom. Its size is the same as the degree of freedom on a single vertex/edge.

get_weights(problem::GraphProblem[, i::Int]) -> Vector
get_weights(problem::GenericTensorNetwork[, i::Int]) -> Vector

The weights for the problem or the weights for the degree of freedom specified by the i-th term if a second argument is provided. Weights are associated with energy_terms in the graph problem. In graph polynomial, integer weights can be the exponents.

chweights(problem::GraphProblem, weights) -> GraphProblem
chweights(problem::GenericTensorNetwork, weights) -> GenericTensorNetwork

Change the weights for the problem and return a new problem instance. Weights are associated with energy_terms in the graph problem. In graph polynomial, integer weights can be the exponents.

nflavor(::Type{<:GraphProblem}) -> Int
nflavor(::Type{<:GenericTensorNetwork}) -> Int
nflavor(::GT) where GT<:GraphProblem -> Int
nflavor(::GenericTensorNetwork{GT}) where GT<:GraphProblem -> Int

Bond size is equal to the number of flavors.

fixedvertices(tnet::GenericTensorNetwork) -> Dict

Returns the fixed vertices in the graph problem, which is a dictionary specifying the fixed dimensions.

is_independent_set(g::SimpleGraph, config)

Return true if config (a vector of boolean numbers as the mask of vertices) is an independent set of graph g.

is_maximal_independent_set(g::SimpleGraph, config)

Return true if config (a vector of boolean numbers as the mask of vertices) is a maximal independent set of graph g.

is_dominating_set(g::SimpleGraph, config)

Return true if config (a vector of boolean numbers as the mask of vertices) is a dominating set of graph g.

is_vertex_coloring(graph::SimpleGraph, config)

Returns true if the coloring specified by config is a valid one, i.e. does not violate the contraints of vertices of an edges having different colors.

is_matching(graph::SimpleGraph, config)

Returns true if config is a valid matching on graph, and false if a vertex is double matched. config is a vector of boolean variables, which has one to one correspondence with edges(graph).

is_set_covering(sets::AbstractVector, config)

Return true if config (a vector of boolean numbers as the mask of sets) is a set covering of sets.

is_set_packing(sets::AbstractVector, config)

Return true if config (a vector of boolean numbers as the mask of sets) is a set packing of sets.

cut_size(g::SimpleGraph, config; edge_weights=UnitWeight(), vertex_weights=ZeroWeight())

Compute the cut size for the vertex configuration config (an iterator).

spinglass_energy(g::SimpleGraph, config; J, h=ZeroWeight())
spinglass_energy(cliques::AbstractVector{Vector{Int}}, config; weights=UnitWeight())
spinglass_energy(sg::SpinGlass, config)

Compute the spin glass state energy for the vertex configuration config. In the configuration, the spin ↑ is mapped to configuration 0, while spin ↓ is mapped to configuration 1. Let $G=(V,E)$ be the input graph, the hamiltonian is

\[H = \sum_{ij \in E} J_{ij} s_i s_j + \sum_{i \in V} h_i s_i,\]

where $s_i \in \{-1, 1\}$ stands for spin ↓ and spin ↑.

In the hypergraph case, the hamiltonian is

\[H = \sum_{c \in C} w_c \prod_{i \in c} s_i,\]

where $C$ is the set of cliques, and $w_c$ is the weight of the clique $c$.

num_paint_shop_color_switch(sequence::AbstractVector, coloring)

Returns the number of color switches.

paint_shop_coloring_from_config(p::PaintShop, config)

Returns a valid painting from the paint shop configuration (given by the configuration solvers). The config is a sequence of 0 and 1, where 0 means painting the first appearence of a car in blue, 1 otherwise.

mis_compactify!(tropicaltensor; potential=nothing)

Compactify tropical tensor for maximum independent set problem. It will eliminate some entries by setting them to zero, by the criteria that removing these entry does not change the MIS size of its parent graph (reference to be added).

Arguments

• tropicaltensor::AbstractArray{T}: the tropical tensor

Keyword arguments

• potential=nothing: the maximum possible MIS contribution from each open vertex

CNF{T}
CNF(clauses)

Boolean expression in conjunctive normal form. clauses is a vector of CNFClause, if and only if all clauses are satisfied, this CNF is satisfied.

Example

julia> @bools x y z

julia> cnf = (x ∨ y) ∧ (¬y ∨ z)
(x ∨ y) ∧ (¬y ∨ z)

julia> satisfiable(cnf, Dict([:x=>true, :y=>false, :z=>true]))
true

julia> satisfiable(cnf, Dict([:x=>false, :y=>false, :z=>true]))
false

CNFClause{T}
CNFClause(vars)

A clause in CNF, its value is the logical or of vars, where vars is a vector of BoolVar.

BoolVar{T}
BoolVar(name, neg)

Boolean variable for constructing CNF clauses.

satisfiable(cnf::CNF, config::AbstractDict)

Returns true if an assignment of variables satisfies a CNF.

@bools(syms::Symbol...)

Create some boolean variables of type BoolVar in current scope that can be used in create a CNF.

Example

julia> @bools x y z

julia> (x ∨ y) ∧ (¬y ∨ z)
(x ∨ y) ∧ (¬y ∨ z)

∨(vars...)

Logical or applied on BoolVar and CNFClause. Returns a CNFClause.

¬(var::BoolVar)

Negation of a boolean variables of type BoolVar.

∧(vars...)

Logical and applied on CNFClause and CNF. Returns a new CNF.

is_valid_mining(rewards::AbstractMatrix, config)

Return true if config (a boolean mask for the feasible region) is a valid mining of rewards.

print_mining(rewards::AbstractMatrix, config)

Printing the mining solution in a colored REPL.

struct PartitionFunction{T} <: GenericTensorNetworks.AbstractProperty

• beta

Compute the partition function for the target problem.

• The corresponding tensor element type is T.

SizeMax{K} <: AbstractProperty
SizeMax(k::Int)

The maximum-K set sizes. e.g. the largest size of the IndependentSet problem is also know as the independence number.

• The corresponding tensor element type are max-plus tropical number Tropical if K is Single and ExtendedTropical if K is an integer.
• It is compatible with weighted graph problems.
• BLAS (on CPU) and GPU are supported only if K is Single,

SizeMin{K} <: AbstractProperty
SizeMin(k::Int)

The minimum-K set sizes. e.g. the smallest size ofthe MaximalIS problem is also known as the independent domination number.

• The corresponding tensor element type are inverted max-plus tropical number Tropical if K is Single and inverted ExtendedTropical K is an integer.

The inverted Tropical number emulates the min-plus tropical number.

• It is compatible with weighted graph problems.
• BLAS (on CPU) and GPU are supported only if K is Single,

CountingAll <: AbstractProperty
CountingAll()

Counting the total number of sets. e.g. for the IndependentSet problem, it counts the independent sets.

• The corresponding tensor element type is Base.Real.
• The weights on graph does not have effect.
• BLAS (GPU and CPU) and GPU are supported,

CountingMax{K} <: AbstractProperty
CountingMax(K=Single)

Counting the number of sets with largest-K size. e.g. for IndependentSet problem, it counts independent sets of size $\alpha(G), \alpha(G)-1, \ldots, \alpha(G)-K+1$.

• The corresponding tensor element type is CountingTropical if K is Single, and TruncatedPoly{K} if K is an integer.
• Weighted graph problems is only supported if K is Single.
• GPU is supported,

CountingMin{K} <: AbstractProperty
CountingMin(K=Single)

Counting the number of sets with smallest-K size.

• The corresponding tensor element type is inverted CountingTropical if K is Single, and TruncatedPoly{K} if K is an integer.
• Weighted graph problems is only supported if K is Single.
• GPU is supported,

GraphPolynomial{METHOD} <: AbstractProperty
GraphPolynomial(; method=:finitefield, kwargs...)

Compute the graph polynomial, e.g. for IndependentSet problem, it is the independence polynomial. The METHOD type parameter can be one of the following symbols

Method Argument

• :finitefield, uses finite field algebra to fit the polynomial.
  • The corresponding tensor element type is Mods.Mod,
  • It does not have round-off error,
  • GPU is supported,
  • It accepts keyword arguments maxorder (optional, e.g. the MIS size in the IndependentSet problem).
• :polynomial and :laurent, use (Laurent) polynomial numbers to solve the polynomial directly.
  • The corresponding tensor element types are Polynomial and LaurentPolynomial.
  • It might have small round-off error depending on the data type for storing the counting.
  • It has memory overhead that linear to the graph size.
• :fft, use fast fourier transformation to fit the polynomial.
  • The corresponding tensor element type is Base.Complex.
  • It has (controllable) round-off error.
  • BLAS and GPU are supported.
  • It accepts keyword arguments maxorder (optional) and r, if r > 1, one has better precision for coefficients of large order, if r < 1, one has better precision for coefficients of small order.
• :fitting, fit the polynomial directly.
  • The corresponding tensor element type is floating point numbers like Base.Float64.
  • It has round-off error.
  • BLAS and GPU are supported, it is the fastest among all methods.

Graph polynomials are not defined for weighted graph problems.

SingleConfigMax{K, BOUNDED} <: AbstractProperty
SingleConfigMax(k::Int; bounded=false)

Finding single solution for largest-K sizes, e.g. for IndependentSet problem, it is one of the maximum independent sets.

• The corresponding data type is CountingTropical{Float64,<:ConfigSampler} if BOUNDED is false, Tropical otherwise.
• Weighted graph problems is supported.
• GPU is supported,

Keyword Arguments

• bounded, if it is true, use bounding trick (or boolean gradients) to reduce the working memory to store intermediate configurations.

SingleConfigMin{K, BOUNDED} <: AbstractProperty
SingleConfigMin(k::Int; bounded=false)

Finding single solution with smallest-K size.

• The corresponding data type is inverted CountingTropical{Float64,<:ConfigSampler} if BOUNDED is false, inverted Tropical otherwise.
• Weighted graph problems is supported.
• GPU is supported,

Keyword Arguments

• bounded, if it is true, use bounding trick (or boolean gradients) to reduce the working memory to store intermediate configurations.

ConfigsAll{TREESTORAGE} <:AbstractProperty
ConfigsAll(; tree_storage=false)

Find all valid configurations, e.g. for IndependentSet problem, it is finding all independent sets.

• The corresponding data type is ConfigEnumerator.
• Weights do not take effect.

Keyword Arguments

• tree_storage, if it is true, it uses more memory efficient tree-structure to store the configurations.

ConfigsMax{K, BOUNDED, TREESTORAGE} <:AbstractProperty
ConfigsMax(K=Single; bounded=true, tree_storage=true)

Find configurations with largest-K sizes, e.g. for IndependentSet problem, it is finding all independent sets of sizes $\alpha(G), \alpha(G)-1, \ldots, \alpha(G)-K+1$.

• The corresponding data type is CountingTropical{Float64,<:ConfigEnumerator} if K is Single and TruncatedPoly{K,<:ConfigEnumerator} if K is an integer.
• Weighted graph problems is only supported if K is Single.

Keyword Arguments

• bounded, if it is true, use bounding trick (or boolean gradients) to reduce the working memory to store intermediate configurations.
• tree_storage, if it is true, it uses more memory efficient tree-structure to store the configurations.

ConfigsMin{K, BOUNDED, TREESTORAGE} <:AbstractProperty
ConfigsMin(K=Single; bounded=true, tree_storage=false)

Find configurations with smallest-K sizes.

• The corresponding data type is inverted CountingTropical{Float64,<:ConfigEnumerator} if K is Single and inverted TruncatedPoly{K,<:ConfigEnumerator} if K is an integer.
• Weighted graph problems is only supported if K is Single.

Keyword Arguments

• bounded, if it is true, use bounding trick (or boolean gradients) to reduce the working memory to store intermediate configurations.
• tree_storage, if it is true, it uses more memory efficient tree-structure to store the configurations.

is_commutative_semiring(a::T, b::T, c::T) where T

Check if elements a, b and c satisfied the commutative semiring requirements.

\[\begin{align*} (a \oplus b) \oplus c = a \oplus (b \oplus c) & \hspace{5em}\triangleright\text{commutative monoid $\oplus$ with identity $\mathbb{0}$}\\ a \oplus \mathbb{0} = \mathbb{0} \oplus a = a &\\ a \oplus b = b \oplus a &\\ &\\ (a \odot b) \odot c = a \odot (b \odot c) & \hspace{5em}\triangleright \text{commutative monoid $\odot$ with identity $\mathbb{1}$}\\ a \odot \mathbb{1} = \mathbb{1} \odot a = a &\\ a \odot b = b \odot a &\\ &\\ a \odot (b\oplus c) = a\odot b \oplus a\odot c & \hspace{5em}\triangleright \text{left and right distributive}\\ (a\oplus b) \odot c = a\odot c \oplus b\odot c &\\ &\\ a \odot \mathbb{0} = \mathbb{0} \odot a = \mathbb{0} \end{align*}\]

TropicalMaxPlus{T} = Tropical{T} <: AbstractSemiring

TropicalMaxPlus is a semiring algebra, can be described by

• Tropical (TropicalMaxPlus), (ℝ, max, +, -Inf, 0).

It maps

• + to max in regular algebra,
• * to + in regular algebra,
• 1 to 0 in regular algebra,
• 0 to -Inf in regular algebra (for integer content types, this is chosen as a small integer).

Example

julia> TropicalMaxPlus(1.0) + TropicalMaxPlus(3.0)
3.0ₜ

julia> TropicalMaxPlus(1.0) * TropicalMaxPlus(3.0)
4.0ₜ

julia> one(TropicalMaxPlusF64)
0.0ₜ

julia> zero(TropicalMaxPlusF64)
-Infₜ

CountingTropical{T,CT} <: Number

Counting tropical number type is also a semiring algebra. It is tropical algebra with one extra field for counting, it is introduced in arXiv:2008.06888.

Example

julia> CountingTropical(1.0, 5.0) + CountingTropical(3.0, 2.0)
(3.0, 2.0)ₜ

julia> CountingTropical(1.0, 5.0) * CountingTropical(3.0, 2.0)
(4.0, 10.0)ₜ

julia> one(CountingTropicalF64)
(0.0, 1.0)ₜ

julia> zero(CountingTropicalF64)
(-Inf, 0.0)ₜ

ExtendedTropical{K,TO} <: Number
ExtendedTropical{K}(orders)

Extended Tropical numbers with largest K orders keeped, or the TruncatedPoly without coefficients, TO is the element type of orders, usually Tropical numbers. This algebra maps

• + to finding largest K values of union of two sets.
• * to finding largest K values of sum combination of two sets.
• 0 to set [-Inf, -Inf, ..., -Inf, -Inf]
• 1 to set [-Inf, -Inf, ..., -Inf, 0]

Fields

• orders is a vector of Tropical (CountingTropical) numbers as the largest-K solution sizes (solutions).

Examples

julia> x = ExtendedTropical{3}(Tropical.([1.0, 2, 3]))
ExtendedTropical{3, Tropical{Float64}}(Tropical{Float64}[1.0ₜ, 2.0ₜ, 3.0ₜ])

julia> y = ExtendedTropical{3}(Tropical.([-Inf, 2, 5]))
ExtendedTropical{3, Tropical{Float64}}(Tropical{Float64}[-Infₜ, 2.0ₜ, 5.0ₜ])

julia> x * y
ExtendedTropical{3, Tropical{Float64}}(Tropical{Float64}[6.0ₜ, 7.0ₜ, 8.0ₜ])

julia> x + y
ExtendedTropical{3, Tropical{Float64}}(Tropical{Float64}[2.0ₜ, 3.0ₜ, 5.0ₜ])

julia> one(x)
ExtendedTropical{3, Tropical{Float64}}(Tropical{Float64}[-Infₜ, -Infₜ, 0.0ₜ])

julia> zero(x)
ExtendedTropical{3, Tropical{Float64}}(Tropical{Float64}[-Infₜ, -Infₜ, -Infₜ])

Mod{m}(v) creates a modular number in mod m with value mod(v,m).

TruncatedPoly{K,T,TO} <: Number
TruncatedPoly(coeffs::Tuple, maxorder)

Polynomial truncated to largest K orders. T is the coefficients type and TO is the orders type.

Fields

• coeffs is the largest-K coefficients of a polynomial. In GenericTensorNetworks, it can be the counting or enumeration of solutions.
• maxorder is the order of a polynomial.

Examples

julia> TruncatedPoly((1,2,3), 6)
x^4 + 2*x^5 + 3*x^6

julia> TruncatedPoly((1,2,3), 6) * TruncatedPoly((5,2,1), 3)
20*x^7 + 8*x^8 + 3*x^9

julia> TruncatedPoly((1,2,3), 6) + TruncatedPoly((5,2,1), 3)
x^4 + 2*x^5 + 3*x^6

Max2Poly{T,TO} = TruncatedPoly{2,T,TO}
Max2Poly(a, b, maxorder)

A shorthand of TruncatedPoly{2}.

ConfigEnumerator{N,S,C} <: AbstractSetNumber

Set algebra for enumerating configurations, where N is the length of configurations, C is the size of storage in unit of UInt64, S is the bit width to store a single element in a configuration, i.e. log2(# of flavors), for bitstrings, it is 1`.

Fields

• data is a vector of StaticElementVector as the solution set.

Examples

julia> a = ConfigEnumerator([StaticBitVector([1,1,1,0,0]), StaticBitVector([1,0,0,0,1])])
{11100, 10001}

julia> b = ConfigEnumerator([StaticBitVector([0,0,0,0,0]), StaticBitVector([1,0,1,0,1])])
{00000, 10101}

julia> a + b
{11100, 10001, 00000, 10101}

julia> one(a)
{00000}

julia> zero(a)
{}

SumProductTree{ET} <: AbstractSetNumber

Configuration enumerator encoded in a tree, it is the most natural representation given by a sum-product network and is often more memory efficient than putting the configurations in a vector. One can use generate_samples to sample configurations from this tree structure efficiently.

Fields

• tag is one of ZERO, ONE, LEAF, SUM, PROD.
• data is the element stored in a LEAF node.
• left and right are two operands of a SUM or PROD node.

Examples

julia> s = SumProductTree(bv"00111")
00111


julia> q = SumProductTree(bv"10000")
10000


julia> x = s + q
+ (count = 2.0)
├─ 00111
└─ 10000


julia> y = x * x
* (count = 4.0)
├─ + (count = 2.0)
│  ├─ 00111
│  └─ 10000
└─ + (count = 2.0)
   ├─ 00111
   └─ 10000


julia> collect(y)
4-element Vector{StaticBitVector{5, 1}}:
 00111
 10111
 10111
 10000

julia> zero(s)
∅



julia> one(s)
00000

ConfigSampler{N,S,C} <: AbstractSetNumber
ConfigSampler(elements::StaticElementVector)

The algebra for sampling one configuration, where N is the length of configurations, C is the size of storage in unit of UInt64, S is the bit width to store a single element in a configuration, i.e. log2(# of flavors), for bitstrings, it is 1`.

Fields

• data is a StaticElementVector as the sampled solution.

Examples

julia> ConfigSampler(StaticBitVector([1,1,1,0,0]))
ConfigSampler{5, 1, 1}(11100)

julia> ConfigSampler(StaticBitVector([1,1,1,0,0])) + ConfigSampler(StaticBitVector([1,0,1,0,0]))
ConfigSampler{5, 1, 1}(10100)

julia> ConfigSampler(StaticBitVector([1,1,1,0,0])) * ConfigSampler(StaticBitVector([0,0,0,0,1]))
ConfigSampler{5, 1, 1}(11101)

julia> one(ConfigSampler{5, 1, 1})
ConfigSampler{5, 1, 1}(00000)

julia> zero(ConfigSampler{5, 1, 1})
ConfigSampler{5, 1, 1}(11111)

read_size(x)

Read the size information from the generic element.

read_count(x)

Read the counting information from the generic element.

read_config(x; keeptree=false)

Read the configuration information from the generic element, if keeptree=true, the tree structure will not be flattened.

read_size_count(x)

Read the size and counting information from the generic element.

read_size_config(x; keeptree=false)

Read the size and configuration information from the generic element. If keeptree=true, the tree structure will not be flattened.

StaticBitVector{N,C} = StaticElementVector{N,1,C}
StaticBitVector(x::AbstractVector)

Examples

julia> sb = StaticBitVector([1,0,0,1,1])
10011

julia> sb[3]
0x0000000000000000

julia> collect(Int, sb)
5-element Vector{Int64}:
 1
 0
 0
 1
 1

StaticElementVector{N,S,C}
StaticElementVector(nflavor::Int, x::AbstractVector)

N is the length of vector, C is the size of storage in unit of UInt64, S is the stride defined as the log2(# of flavors). When the number of flavors is 2, it is a StaticBitVector.

Fields

• data is a tuple of UInt64 for storing the configuration of static elements.

Examples

julia> ev = StaticElementVector(3, [1,2,0,1,2])
12012

julia> ev[2]
0x0000000000000002

julia> collect(Int, ev)
5-element Vector{Int64}:
 1
 2
 0
 1
 2

OnehotVec{N,NF}
OnehotVec{N,NF}(loc, val)

Onehot vector type, N is the number of vector length, NF is the number of flavors.

save_configs(filename, data::ConfigEnumerator; format=:binary)

Save configurations data to file filename. The format is :binary or :text.

load_configs(filename; format=:binary, bitlength=nothing, nflavors=2)

Load configurations from file filename. The format is :binary or :text. If the format is :binary, the bitstring length bitlength must be specified, nflavors specifies the degree of freedom.

save_sumproduct(filename, t::SumProductTree)

Serialize a sum-product tree into a file.

load_sumproduct(filename)

Deserialize a sum-product tree from a file.

Constructing a static bit vector.

onehotv(::Type{<:StaticElementVector}, i, v)
onehotv(::Type{<:StaticBitVector, i)

Returns a static element vector, with the value at location i being v (1 if not specified).

generate_samples(t::SumProductTree, nsamples::Int)

Direct sampling configurations from a SumProductTree instance.

Examples

julia> using Graphs

julia> g= smallgraph(:petersen)
{10, 15} undirected simple Int64 graph

julia> t = solve(GenericTensorNetwork(IndependentSet(g)), ConfigsAll(; tree_storage=true))[];

julia> samples = generate_samples(t, 1000);

julia> all(s->is_independent_set(g, s), samples)
true

hamming_distribution(S, T)

Compute the distribution of pair-wise Hamming distances, which is defined as:

\[c(k) := \sum_{\sigma\in S, \tau\in T} \delta({\rm dist}(\sigma, \tau), k)\]

where $\delta$ is a function that returns 1 if two arguments are equivalent, 0 otherwise, ${\rm dist}$ is the Hamming distance function.

Returns the counting as a vector.

optimize_code(eincode, size_dict, optimizer = GreedyMethod(), simplifier=nothing, permute=true) -> optimized_eincode

Optimize the einsum contraction code and reduce the time/space complexity of tensor network contraction. Returns a NestedEinsum instance. Input arguments are

• eincode is an einsum contraction code instance, one of DynamicEinCode, StaticEinCode or NestedEinsum.
• size is a dictionary of "edge label=>edge size" that contains the size information, one can use uniformsize(eincode, 2) to create a uniform size.
• optimizer is a CodeOptimizer instance, should be one of GreedyMethod, KaHyParBipartite, SABipartite or TreeSA. Check their docstrings for details.
• simplifier is one of MergeVectors or MergeGreedy.
• optimize the permutation if permute is true.

Examples

julia> using OMEinsum

julia> code = ein"ij, jk, kl, il->"
ij, jk, kl, il -> 

julia> optimize_code(code, uniformsize(code, 2), TreeSA())
SlicedEinsum{Char, NestedEinsum{DynamicEinCode{Char}}}(Char[], ki, ki -> 
├─ jk, ij -> ki
│  ├─ jk
│  └─ ij
└─ kl, il -> ki
   ├─ kl
   └─ il
)

getixsv(code)

Get labels of input tensors for EinCode, NestedEinsum and some other einsum like objects. Returns a vector of vectors.

julia> getixsv(ein"(ij,jk),k->i")
3-element Vector{Vector{Char}}:
 ['i', 'j']
 ['j', 'k']
 ['k']

getiy(code)

Get labels of the output tensor for EinCode, NestedEinsum and some other einsum like objects. Returns a vector.

julia> getiyv(ein"(ij,jk),k->i")
1-element Vector{Char}:
 'i': ASCII/Unicode U+0069 (category Ll: Letter, lowercase)

contraction_complexity(eincode, size_dict) -> ContractionComplexity

Returns the time, space and read-write complexity of the einsum contraction. The returned object contains 3 fields:

• time complexity tc defined as log2(number of element-wise multiplications).
• space complexity sc defined as log2(size of the maximum intermediate tensor).
• read-write complexity rwc defined as log2(the number of read-write operations).

estimate_memory(
    problem::GenericTensorNetwork,
    property::GenericTensorNetworks.AbstractProperty;
    T
) -> Any

Memory estimation in number of bytes to compute certain property of a problem. T is the base type.

ein"ij,jk -> ik"(A,B)

String macro interface which understands numpy.einsum's notation. Translates strings into StaticEinCode-structs that can be called to evaluate an einsum. To control evaluation order, use parentheses - instead of an EinCode, a NestedEinsum is returned which evaluates the expression according to parens. The valid character ranges for index-labels are a-z and α-ω.

example

julia> a, b, c = rand(10,10), rand(10,10), rand(10,1);

julia> ein"ij,jk,kl -> il"(a,b,c) ≈ ein"(ij,jk),kl -> il"(a,b,c) ≈ a * b * c
true

GreedyMethod{MT}
GreedyMethod(; method=MinSpaceOut(), nrepeat=10)

The fast but poor greedy optimizer. Input arguments are

• method is MinSpaceDiff() or MinSpaceOut.
  • MinSpaceOut choose one of the contraction that produces a minimum output tensor size,
  • MinSpaceDiff choose one of the contraction that decrease the space most.
• nrepeat is the number of repeatition, returns the best contraction order.

TreeSA{RT,IT,GM}
TreeSA(; sc_target=20, βs=collect(0.01:0.05:15), ntrials=10, niters=50,
    sc_weight=1.0, rw_weight=0.2, initializer=:greedy, greedy_config=GreedyMethod(; nrepeat=1))

Optimize the einsum contraction pattern using the simulated annealing on tensor expression tree.

• sc_target is the target space complexity,
• ntrials, βs and niters are annealing parameters, doing ntrials indepedent annealings, each has inverse tempteratures specified by βs, in each temperature, do niters updates of the tree.
• sc_weight is the relative importance factor of space complexity in the loss compared with the time complexity.
• rw_weight is the relative importance factor of memory read and write in the loss compared with the time complexity.
• initializer specifies how to determine the initial configuration, it can be :greedy or :random. If it is using :greedy method to generate the initial configuration, it also uses two extra arguments greedy_method and greedy_nrepeat.
• nslices is the number of sliced legs, default is 0.
• fixed_slices is a vector of sliced legs, default is [].

References

• Recursive Multi-Tensor Contraction for XEB Verification of Quantum Circuits

SABipartite{RT,BT}
SABipartite(; sc_target=25, ntrials=50, βs=0.1:0.2:15.0, niters=1000
    max_group_size=40, greedy_config=GreedyMethod(), initializer=:random)

Optimize the einsum code contraction order using the Simulated Annealing bipartition + Greedy approach. This program first recursively cuts the tensors into several groups using simulated annealing, with maximum group size specifed by max_group_size and maximum space complexity specified by sc_target, Then finds the contraction order inside each group with the greedy search algorithm. Other arguments are

• size_dict, a dictionary that specifies leg dimensions,
• sc_target is the target space complexity, defined as log2(number of elements in the largest tensor),
• max_group_size is the maximum size that allowed to used greedy search,
• βs is a list of inverse temperature 1/T,
• niters is the number of iteration in each temperature,
• ntrials is the number of repetition (with different random seeds),
• greedy_config configures the greedy method,
• initializer, the partition configuration initializer, one can choose :random or :greedy (slow but better).

References

• Hyper-optimized tensor network contraction

KaHyParBipartite{RT,IT,GM}
KaHyParBipartite(; sc_target, imbalances=collect(0.0:0.005:0.8),
    max_group_size=40, greedy_config=GreedyMethod())

Optimize the einsum code contraction order using the KaHyPar + Greedy approach. This program first recursively cuts the tensors into several groups using KaHyPar, with maximum group size specifed by max_group_size and maximum space complexity specified by sc_target, Then finds the contraction order inside each group with the greedy search algorithm. Other arguments are

• sc_target is the target space complexity, defined as log2(number of elements in the largest tensor),
• imbalances is a KaHyPar parameter that controls the group sizes in hierarchical bipartition,
• max_group_size is the maximum size that allowed to used greedy search,
• greedy_config is a greedy optimizer.

References

• Hyper-optimized tensor network contraction
• Simulating the Sycamore quantum supremacy circuits

MergeVectors <: CodeSimplifier
MergeVectors()

Contraction code simplifier (in order to reduce the time of calling optimizers) that merges vectors to closest tensors.

MergeGreedy <: CodeSimplifier
MergeGreedy(; threshhold=-1e-12)

Contraction code simplifier (in order to reduce the time of calling optimizers) that merges tensors greedily if the space complexity of merged tensors is reduced (difference smaller than the threshhold).

show_graph([f, ]graph::AbstractGraph;
    kwargs...
    )

Show a graph in VSCode, Pluto or Jupyter notebook, or save it to a file.

Positional arguments

• f is a function that returns extra Luxor plotting statements.
• graph is a graph instance.
• locs is a vector of tuples for specifying the vertex locations, or a AbstractLayout instance.

Keyword arguments

• config is a GraphDisplayConfig instance.

• vertex_colors is a vector of color strings for specifying vertex fill colors.

• vertex_sizes is a vector of real numbers for specifying vertex sizes.

• vertex_shapes is a vector of strings for specifying vertex shapes, the string should be "circle" or "box".

• vertex_stroke_colors is a vector of color strings for specifying vertex stroke colors.

• vertex_text_colors is a vector of color strings for specifying vertex text colors.

• edge_colors is a vector of color strings for specifying edge colors.

• texts is a vector of strings for labeling vertices.

• padding_left::Int = 10, the padding on the left side of the drawing

• padding_right::Int = 10, the padding on the right side of the drawing

• padding_top::Int = 10, the padding on the top side of the drawing

• padding_bottom::Int = 10, the padding on the bottom side of the drawing

• format is the output format, which can be :svg, :png or :pdf.

• filename is a string as the output filename.

Example

julia> using Graphs, LuxorGraphPlot

julia> show_graph(smallgraph(:petersen); format=:png, vertex_colors=rand(["blue", "red"], 10));

show_configs(gp::GraphProblem, locs, configs::AbstractMatrix; kwargs...)
show_configs(graph::SimpleGraph, locs, configs::AbstractMatrix; nflavor=2, kwargs...)

Show a gallery of configurations on a graph.

show_einsum(ein::AbstractEinsum;
    tensor_locs=nothing,
    label_locs=nothing,  # dict
    spring::Bool=true,
    optimal_distance=25.0,

    tensor_size=15,
    tensor_color="black",
    tensor_text_color="white",
    annotate_tensors=false,

    label_size=7,
    label_color="black",
    open_label_color="black",
    annotate_labels=true,
    kwargs...
    )

Positional arguments

• ein is an Einsum contraction code (provided by package OMEinsum).

Keyword arguments

• locs is a tuple of tensor_locs (vector) and label_locs (dict).

• spring is switch to use spring method to optimize the location.

• optimal_distance is a optimal distance parameter for spring optimizer.

• tensor_color is a string to specify the color of tensor nodes.

• tensor_size is a real number to specify the size of tensor nodes.

• tensor_text_color is a color strings to specify tensor text color.

• annotate_tensors is a boolean switch for annotate different tensors by integers.

• label_size is a real number to specify label text node size.

• label_color is a color strings to specify label text color.

• open_label_color is a color strings to specify open label text color.

• annotate_labels is a boolean switch for annotate different labels.

• format is the output format, which can be :svg, :png or :pdf.

• filename is a string as the output filename.

• fontsize::Float64 = 12.0, the font size

• fontface::String = "", the font face, leave empty to follow system

• vertex_text_color = "black", the default text color

• vertex_stroke_color = "black", the default stroke color for vertices

• vertex_color = "transparent", the default default fill color for vertices

• vertex_size::Float64 = 10.0, the default vertex size

• vertex_shape::Symbol = :circle, the default vertex shape, which can be :circle, :box or :dot

• vertex_line_width::Float64 = 1, the default vertex stroke line width

• vertex_line_style::String = "solid", the line style of vertex stroke, which can be one of ["solid", "dotted", "dot", "dotdashed", "longdashed", "shortdashed", "dash", "dashed", "dotdotdashed", "dotdotdotdashed"]

• edge_color = "black", the default edge color

• edge_line_width::Float64 = 1, the default line width

• edge_style::String = "solid", the line style of edges, which can be one of ["solid", "dotted", "dot", "dotdashed", "longdashed", "shortdashed", "dash", "dashed", "dotdotdashed", "dotdotdotdashed"]

show_landscape(is_neighbor, configurations::TruncatedPoly;
    layer_distance=200,
    config=GraphDisplayConfig(; edge_color="gray", vertex_stroke_color="transparent", vertex_size=5),
    layout_method=:spring,
    optimal_distance=30.0,
    colors=fill("green", K),
    kwargs...)

Show the energy landscape of configurations.

Arguments

• is_neighbor: a function to determine if two configurations are neighbors.
• configurations: a TruncatedPoly object, which is the default output of the solve function with ConfigsMax property as the argument.

Keyword arguments

• layer_distance: the distance between layers.
• config: a LuxorGraphPlot.GraphDisplayConfig object.
• layout_method: the layout method, either :spring, :stress or :spectral
• optimal_distance: the optimal distance for the layout.
• colors: a vector of colors for each layer.
• kwargs...: other keyword arguments passed to show_graph.

GraphDisplayConfig

The configuration for graph display.

Keyword arguments

• locs is a vector of tuples for specifying the vertex locations.

• edges is a vector of tuples for specifying the edges.

• fontsize::Float64 = 12.0, the font size

• fontface::String = "", the font face, leave empty to follow system

• vertex_text_color = "black", the default text color

• vertex_stroke_color = "black", the default stroke color for vertices

• vertex_color = "transparent", the default default fill color for vertices

• vertex_size::Float64 = 10.0, the default vertex size

• vertex_shape::Symbol = :circle, the default vertex shape, which can be :circle, :box or :dot

• vertex_line_width::Float64 = 1, the default vertex stroke line width

• vertex_line_style::String = "solid", the line style of vertex stroke, which can be one of ["solid", "dotted", "dot", "dotdashed", "longdashed", "shortdashed", "dash", "dashed", "dotdotdashed", "dotdotdotdashed"]

• edge_color = "black", the default edge color

• edge_line_width::Float64 = 1, the default line width

• edge_style::String = "solid", the line style of edges, which can be one of ["solid", "dotted", "dot", "dotdashed", "longdashed", "shortdashed", "dash", "dashed", "dotdotdashed", "dotdotdotdashed"]

AbstractLayout

Abstract type for layout algorithms.

SpringLayout <: AbstractLayout

A layout algorithm based on a spring model.

Fields

• optimal_distance::Float64: the optimal distance between vertices
• maxiter::Int: the maximum number of iterations
• α0::Float64: the initial moving speed
• meta::Dict{Symbol, Any}: graph dependent meta information, including
  • initial_locs: initial vertex locations
  • mask: boolean mask for which vertices to relocate

StressLayout <: AbstractLayout

A layout algorithm based on stress majorization.

Fields

• optimal_distance::Float64: the optimal distance between vertices
• maxiter::Int: the maximum number of iterations
• rtol::Float64: the absolute tolerance
• initial_locs: initial vertex locations
• mask: boolean mask for which vertices to relocate
• meta::Dict{Symbol, Any}: graph dependent meta information, including
  • initial_locs: initial vertex locations
  • mask: boolean mask for which vertices to relocate

SpectralLayout <: AbstractLayout

A layout algorithm based on spectral graph theory.

Fields

• optimal_distance::Float64: the optimal distance between vertices
• dimension::Int: the number of dimensions

Layered <: AbstractLayout

Layered version of a parent layout algorithm.

Fields

• parent::LT: the parent layout algorithm
• zlocs::Vector{T}: the z-axis locations
• aspect_ratio::Float64: the aspect ratio of the z-axis

LayeredSpringLayout(; zlocs, optimal_distance, aspect_ration=0.2)

Create a layered spring layout.

Keyword Arguments

• zlocs: the z-axis locations
• optimal_distance::Float64: the optimal distance between vertices
• aspect_ration::Float64: the aspect ratio of the z-axis
• α0::Float64: the initial moving speed
• maxiter::Int: the maximum number of iterations

LayeredStressLayout(; zlocs, optimal_distance, aspect_ration=0.2)

Create a layered stress layout.

Keyword Arguments

• zlocs: the z-axis locations
• optimal_distance::Float64: the optimal distance between vertices
• aspect_ration::Float64: the aspect ratio of the z-axis
• maxiter::Int: the maximum number of iterations
• rtol::Float64: the absolute tolerance

render_locs(graph, layout::Layout)

Render the vertex locations for a graph from an AbstractLayout instance.

Arguments

• graph::AbstractGraph: the graph to render
• layout::AbstractLayout: the layout algorithm

diagonal_coupled_graph(mask::AbstractMatrix{Bool})

Create a masked diagonal coupled square lattice graph from a specified mask.

square_lattice_graph(mask::AbstractMatrix{Bool})

Create a masked square lattice graph.

unit_disk_graph(locs::AbstractVector, unit::Real)

Create a unit disk graph with locations specified by locs and unit distance unit.

line_graph(g::SimpleGraph)

Returns the line graph of g. The line graph is generated by mapping an edge to a vertex and two edges sharing a common vertex will be connected.

random_diagonal_coupled_graph(m::Int, n::Int, ρ::Real)

Create a $m\times n$ random masked diagonal coupled square lattice graph, with number of vertices equal to $\lfloor m \times n\times \rho \rceil$.

random_square_lattice_graph(m::Int, n::Int, ρ::Real)

Create a random masked square lattice graph, with number of vertices fixed to $\lfloor mn\rho \rceil$.

multiprocess_run(func, inputs::AbstractVector)

Execute function func on inputs with multiple processing.

Example

Suppose we have a file run.jl with the following contents

using GenericTensorNetworks.SimpleMultiprocessing

results = multiprocess_run(x->x^2, randn(8))

In an terminal, you may run the script with 4 processes by typing

$ julia -p4 run.jl
      From worker 2:	[ Info: running argument -0.17544008350172655 on device 2
      From worker 5:	[ Info: running argument 0.34578117779452555 on device 5
      From worker 3:	[ Info: running argument 2.0312551239727705 on device 3
      From worker 4:	[ Info: running argument -0.7319353419291961 on device 4
      From worker 2:	[ Info: running argument 0.013132180639054629 on device 2
      From worker 3:	[ Info: running argument 0.9960101782201602 on device 3
      From worker 4:	[ Info: running argument -0.5613942832743966 on device 4
      From worker 5:	[ Info: running argument 0.39460402723831134 on device 5