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::ConstraintSatisfactionProblem; openvertices=(), fixedvertices=Dict(), optimizer=GreedyMethod())

The generic tensor network that generated from a ConstraintSatisfactionProblem.

Positional arguments

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

ConstraintSatisfactionProblem{T} <: AbstractProblem

The abstract base type of constraint satisfaction problems. T is the type of the local size of the constraints.

Required interfaces

• hard_constraints, the specification of the hard constraints. Once the hard constraints are violated, the size goes to infinity.

• is_satisfied, check if the hard constraints are satisfied.

• local_solution_spec, the specification of the size terms as soft constraints, which is associated with weights.

• weights: The weights of the soft constraints.

• set_weights: Change the weights for the problem and return a new problem instance.

• solution_size, the size of the problem given a configuration.

• energy_mode, the definition of the energy function, which can be LargerSizeIsBetter or SmallerSizeIsBetter.

struct IndependentSet{GT<:Graphs.AbstractGraph, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

IndependentSet(graph::AbstractGraph, weights::AbstractVector=UnitWeight(nv(graph))) -> IndependentSet

Independent Set is a subset of vertices in a undirected graph such that all the vertices in the set are not connected by edges (or called not adjacent). The maximum IndependentSet problem is to find the independent set with maximum number of vertices, which is a NP-complete problem. Let $G=(V, E)$ be a graph, and $w_v$ be the weight of vertex $v$. The energy based model of the independent set problem is:

\[H(G, \mathbf{n}) = - \sum_{v \in V} w_v n_v + \sum_{(u, v) \in E} n_u n_v\]

where $n_v$ is the number of vertices in the independent set, i.e. $n_v = 1$ if $v$ is in the independent set, and $n_v = 0$ otherwise. The larger the size of the independent set, the lower the energy.

Fields

• graph::AbstractGraph: The problem graph.
• weights::AbstractVector: Weights associated with the vertices of the graph. Defaults to UnitWeight(nv(graph)).

Example

In the following example, we define an independent set problem on a graph with four vertices. To define an IndependentSet problem, we need to specify the graph and possibily the weights associated with vertices. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights.

julia> using ProblemReductions, Graphs

julia> graph = SimpleGraph(Graphs.SimpleEdge.([(1, 2), (1, 3), (3, 4), (2, 3)]))
{4, 4} undirected simple Int64 graph

julia> IS = IndependentSet(graph)
IndependentSet{SimpleGraph{Int64}, Int64, UnitWeight}(SimpleGraph{Int64}(4, [[2, 3], [1, 3], [1, 2, 4], [3]]), [1, 1, 1, 1])

julia> num_variables(IS)  # degrees of freedom
4

julia> flavors(IS)  # flavors of the vertices
(0, 1)

julia> solution_size(IS, [1, 0, 0, 1]) # Positive sample: -(size) of an independent set
SolutionSize{Int64}(2, true)

julia> solution_size(IS, [0, 1, 1, 0]) # Negative sample: 0
SolutionSize{Int64}(2, false)

julia> findbest(IS, BruteForce())  # solve the problem with brute force
2-element Vector{Vector{Int64}}:
 [1, 0, 0, 1]
 [0, 1, 0, 1]

struct MaximalIS{T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

Maximal independent set is a problem that very similar to the IndependentSet problem. The difference is that the solution space of a maximal indepdent set problem does not include the independent sets that can be extended by adding one more vertex.

Fields

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

Example

In the following example, we define a maximal independent set problem on a graph with four vertices. To define a MaximalIS problem, we need to specify the graph and possibily the weights associated with vertices. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights in the following development.

julia> using ProblemReductions, Graphs

julia> graph = SimpleGraph(Graphs.SimpleEdge.([(1, 2), (1, 3), (3, 4), (2, 3), (1, 4)]))
{4, 5} undirected simple Int64 graph

julia> problem = MaximalIS(graph)
MaximalIS{Int64, UnitWeight}(SimpleGraph{Int64}(5, [[2, 3, 4], [1, 3], [1, 2, 4], [1, 3]]), [1, 1, 1, 1])

julia> num_variables(problem)  # degrees of freedom
4

julia> flavors(problem)
(0, 1)

julia> solution_size(problem, [0, 1, 0, 0])  # unlike the independent set, this configuration is not a valid solution
SolutionSize{Int64}(1, false)

julia> findbest(problem, BruteForce())
1-element Vector{Vector{Int64}}:
 [0, 1, 0, 1]

struct Matching{T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

The Vertex matching problem.

Positional arguments

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

struct Coloring{K, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

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

The Vertex Coloring (Coloring) problem is defined on a simple graph. Given k kinds of colors, we need to determine whether we can color all vertices on the graph such that no two adjacent vertices share the same color.

Fields

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

Example

To initialize a Coloring problem, we need to first define a graph and decide the number of colors.

julia> using ProblemReductions, Graphs

julia> g = smallgraph(:petersen) # define a simple graph, petersen as example
{10, 15} undirected simple Int64 graph

julia> coloring = Coloring{3}(g)  # 3 colors
Coloring{3, Int64, UnitWeight}(SimpleGraph{Int64}(15, [[2, 5, 6], [1, 3, 7], [2, 4, 8], [3, 5, 9], [1, 4, 10], [1, 8, 9], [2, 9, 10], [3, 6, 10], [4, 6, 7], [5, 7, 8]]), [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

julia> variables(coloring)
1:10

julia> flavors(coloring)
(0, 1, 2)

julia> is_vertex_coloring(coloring.graph,[1,2,3,1,3,2,1,2,3,1]) #random assignment
false

struct DominatingSet{GT<:Graphs.AbstractGraph, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

DominatingSet(graph::AbstractGraph, weights::AbstractVector=UnitWeight(ne(graph))) -> DominatingSet

Dominaing Set is a subset of vertices in a undirected graph such that all the vertices in the set are either in the dominating set or in its first-order neighborhood. The DominatingSet problem is to find the dominating set with minimum number of vertices.

Fields

• graph is the problem graph.
• weights::AbstractVector: Weights associated with the vertices of the graph. Defaults to UnitWeight(nv(graph)).

Example

In the following example, we define a dominating set problem on a path graph with five vertices. To define a DominatingSet problem, we need to specify the graph and possibily the weights associated with vertices. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights in the following development.

julia> using ProblemReductions, Graphs

julia> graph = path_graph(5)
{5, 4} undirected simple Int64 graph

julia> DS = DominatingSet(graph)
DominatingSet{SimpleGraph{Int64}, Int64, UnitWeight}(SimpleGraph{Int64}(4, [[2], [1, 3], [2, 4], [3, 5], [4]]), [1, 1, 1, 1, 1])

julia> variables(DS)  # degrees of freedom
1:5

julia> flavors(DS)  # flavors of the vertices
(0, 1)

julia> solution_size(DS, [0, 1, 0, 1, 0]) # Positive sample: (size) of a dominating set
SolutionSize{Int64}(2, true)

julia> solution_size(DS, [0, 1, 1, 0, 0]) # Negative sample: number of vertices
SolutionSize{Int64}(2, false)

julia> findbest(DS, BruteForce())  # solve the problem with brute force
3-element Vector{Vector{Int64}}:
 [1, 0, 0, 1, 0]
 [0, 1, 0, 1, 0]
 [0, 1, 0, 0, 1]

struct SpinGlass{GT<:Graphs.AbstractGraph, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

SpinGlass(graph::AbstractGraph, weights::AbstractVector)
SpinGlass(graph::SimpleGraph, J, h=zeros(nv(graph)))

Spin Glass is a type of disordered magnetic system that exhibits a glassy behavior. The Hamiltonian of the system on a simple graph $G=(V, E)$ is given by

\[H(G, \sigma) = \sum_{(i,j) \in E} J_{ij} \sigma_i \sigma_j + \sum_{i \in V} h_i \sigma_i\]

where $J_{ij} \in \mathbb{R}$ is the coupling strength between spins $i$ and $j$, $h_i \in \mathbb{R}$ is the external field on spin $i$, and $\sigma_i \in \{-1, 1\}$ is the spin variable.

This definition naturally extends to the case of a HyperGraph:

\[H(G, \sigma) = \sum_{e \in E} J_{e} \prod_k\sigma_k + \sum_{i \in V} h_i \sigma_i,\]

where $J_e$ is the coupling strength associated with hyperedge $e$, and the product is over all spins in the hyperedge.

Fields

• graph is a graph object.
• J are the coupling strengths associated with the edges.
• h are the external fields associated with the vertices.

Example

In the following example, we define a spin glass problem on a 4-vertex graph with given coupling strengths on edges and external fields on vertices.

julia> using ProblemReductions, ProblemReductions.Graphs

julia> graph = SimpleGraph(Graphs.SimpleEdge.([(1, 2), (1, 3), (3, 4), (2, 3)]))
{4, 4} undirected simple Int64 graph

julia> J = [1, -1, 1, -1]  # coupling strength
4-element Vector{Int64}:
  1
 -1
  1
 -1

julia> h = [1, -1, -1, 1]  # external field
4-element Vector{Int64}:
  1
 -1
 -1
  1

julia> spinglass = SpinGlass(graph, J, h)  # Define a spin glass problem
SpinGlass{SimpleGraph{Int64}, Int64, Vector{Int64}}(SimpleGraph{Int64}(4, [[2, 3], [1, 3], [1, 2, 4], [3]]), [1, -1, 1, -1], [1, -1, -1, 1])

julia> num_variables(spinglass)  # degrees of freedom
4

julia> flavors(spinglass)  # flavors of the spins
(1, -1)

julia> solution_size(spinglass, [-1, 1, 1, -1])  # size of a configuration
SolutionSize{Int64}(-2, true)

julia> findbest(spinglass, BruteForce())  # solve the problem with brute force
1-element Vector{Vector{Int64}}:
 [-1, 1, -1, -1]

struct MaxCut{T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

Max Cut problem is defined on weighted graphs. The goal is to find a partition of the vertices into two sets such that the sum of the weights of the edges between the two sets is maximized.

Positional arguments

• graph is the problem graph.
• weights are associated with the edges of the graph. We have ensure that the weights are in the same order as the edges in edges(graph).

Example

In the following example, we solve a Max Cut problem on a complete graph with 3 vertices and edge weights [1,2,3].

julia> using ProblemReductions, Graphs

julia> g = complete_graph(3)
{3, 3} undirected simple Int64 graph

julia> maxcut = MaxCut(g,[1,2,3]) # specify the weights of the edges
MaxCut{Int64, Vector{Int64}}(SimpleGraph{Int64}(3, [[2, 3], [1, 3], [1, 2]]), [1, 2, 3])

julia> mc = set_weights(maxcut, [2,1,3]) # set the weights and get a new instance
MaxCut{Int64, Vector{Int64}}(SimpleGraph{Int64}(3, [[2, 3], [1, 3], [1, 2]]), [2, 1, 3])


julia> num_variables(maxcut) # return the number of vertices
3

julia> flavors(maxcut) # return the flavors of the vertices
(0, 1)

julia> solution_size(maxcut, [0,1,0]) # return the size of the configuration
SolutionSize{Int64}(4, true)

julia> findbest(maxcut, BruteForce()) # find the best configuration
2-element Vector{Vector{Int64}}:
 [1, 1, 0]
 [0, 0, 1]

struct PaintShop{LT} <: ConstraintSatisfactionProblem{Int64}

The binary paint shop problem is defined as follows: we are given a $2m$ length sequence containing $m$ cars, where each car appears twice. Each car need to be colored red in one occurrence, and blue in the other. We need to choose which occurrence for each car to color with which color — the goal is to minimize the number of times we need to change the current color.

Fields

• 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.

Example

In the following example, we define a paint shop problem with 6 cars.

julia> using ProblemReductions

julia> problem = PaintShop(["a","b","a","c","c","b"])
PaintShop{String}(["a", "b", "a", "c", "c", "b"], Bool[1, 1, 0, 1, 0, 0])

julia> num_variables(problem)
3

julia> flavors(problem)
(0, 1)

julia> solution_size(problem, [0, 1, 0])
SolutionSize{Int64}(4, true)

julia> findbest(problem, BruteForce())
2-element Vector{Vector{Int64}}:
 [1, 0, 0]
 [0, 1, 1]

struct Satisfiability{S, T, WT<:(AbstractArray{T})} <: ProblemReductions.AbstractSatisfiabilityProblem{S, T}

Satisfiability (also called SAT) problem is to find the boolean assignment that satisfies a Conjunctive Normal Form (CNF). A tipical CNF would look like:

\[\left(l_{11} \vee \ldots \vee l_{1 n_1}\right) \wedge \ldots \wedge\left(l_{m 1} \vee \ldots \vee l_{m n_m}\right)\]

where literals are joint by $\vee$ to for $m$ clauses and clauses are joint by $\wedge$ to form a CNF.

We should note that all the SAT problem problem can be reduced to the 3-SAT problem and it can be proved that 3-SAT is NP-complete.

Fields

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

Example

In the following example, we define a satisfiability problem with two clauses.

julia> using ProblemReductions

julia> bv1, bv2, bv3 = BoolVar.(["x", "y", "z"])
3-element Vector{BoolVar{String}}:
 x
 y
 z

julia> clause1 = CNFClause([bv1, bv2, bv3])
x ∨ y ∨ z

julia> clause2 = CNFClause([BoolVar("w"), bv1, BoolVar("x", true)])
w ∨ x ∨ ¬x

julia> cnf_test = CNF([clause1, clause2])
(x ∨ y ∨ z) ∧ (w ∨ x ∨ ¬x)

julia> sat_test = Satisfiability(cnf_test)
Satisfiability{String, Int64, UnitWeight}(["x", "y", "z", "w"], [1, 1], (x ∨ y ∨ z) ∧ (w ∨ x ∨ ¬x))

struct SetCovering{ET, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

The Set Covering problem is defined as follow: given a universe of elements and a collection of subsets of the universe, each set is associated with a weight. The goal is to find a subset of sets that covers all the elements with the minimum total weight.

Positional arguments

• elements is a vector of elements in the universe.
• sets is a vector of vectors, a collection of subsets of universe , each set is associated with a weight specified in weights.
• weights are associated with sets.

Example

In the following example, we solve a Set Covering problem with 3 subsets and weights [1,2,3].

julia> using ProblemReductions

julia> subsets = [[1, 2, 3], [2, 4], [1, 4]]
3-element Vector{Vector{Int64}}:
 [1, 2, 3]
 [2, 4]
 [1, 4]

julia> weights = [1, 2, 3]
3-element Vector{Int64}:
 1
 2
 3

julia> setcovering = SetCovering(subsets, weights)
SetCovering{Int64, Int64, Vector{Int64}}([1, 2, 3, 4], [[1, 2, 3], [2, 4], [1, 4]], [1, 2, 3])

julia> num_variables(setcovering)  # degrees of freedom
3

julia> solution_size(setcovering, [1, 0, 1])  # size of a configuration
SolutionSize{Int64}(4, true)

julia> solution_size(setcovering, [0, 1, 1])
SolutionSize{Int64}(5, false)

julia> sc = set_weights(setcovering, [1, 2, 3])  # set the weights of the subsets
SetCovering{Int64, Int64, Vector{Int64}}([1, 2, 3, 4], [[1, 2, 3], [2, 4], [1, 4]], [1, 2, 3])

struct SetPacking{ET, T, WT<:AbstractArray{T, 1}} <: ConstraintSatisfactionProblem{T}

SetPacking(elements::AbstractVector, sets::AbstractVector, weights::AbstractVector=UnitWeight(length(sets))) -> SetPacking

A packing is a set of sets where each set is pairwise disjoint from each other. The maximum (weighted) packing problem is to find the maximum packing for a given union and a set of subsets.

Fields

• elements is a vector of elements in the universe.
• sets is a vector of vectors, each set is associated with a weight specified in weights.
• weights are associated with sets. Defaults to UnitWeight(length(sets)).

Example

In the following example, we define a set packing problem with five subsets. To define a SetPacking problem, we need to specify the set of subsets and possibily the weights associated with these subsets. The weights are set as unit by default in the current version and might be generalized to arbitrary positive weights in the following development. Besides, the elements would be automatically counted by the construction function.

julia> using ProblemReductions

julia> sets = [[1, 2, 5], [1, 3], [2, 4], [3, 6], [2, 3, 6]]
5-element Vector{Vector{Int64}}:
 [1, 2, 5]
 [1, 3]
 [2, 4]
 [3, 6]
 [2, 3, 6]

julia> SP = SetPacking(sets)
SetPacking{Int64, Int64, UnitWeight}([1, 2, 5, 3, 4, 6], [[1, 2, 5], [1, 3], [2, 4], [3, 6], [2, 3, 6]], [1, 1, 1, 1, 1])

julia> num_variables(SP)  # degrees of freedom
5

julia> flavors(SP)  # flavors of the subsets
(0, 1)

julia> solution_size(SP, [1, 0, 0, 1, 0]) # Positive sample: -(size) of a packing
SolutionSize{Int64}(2, true)

julia> solution_size(SP, [1, 0, 1, 1, 0]) # Negative sample: 0
SolutionSize{Int64}(3, false)

julia> findbest(SP, BruteForce())  # solve the problem with brute force
3-element Vector{Vector{Int64}}:
 [0, 1, 1, 0, 0]
 [1, 0, 0, 1, 0]
 [0, 0, 1, 1, 0]

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]
 [1, 5]
 [1, 6]
 [2, 3]
 [2, 7]
 [3, 4]
 [3, 8]
 [4, 5]
 [4, 9]
 [5, 10]
 ⋮
 [2]
 [3]
 [4]
 [5]
 [6]
 [7]
 [8]
 [9]
 [10]

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

flavors(::Type{<:AbstractProblem}) -> Vector

Returns a vector of integers as the flavors (domain) of a degree of freedom.

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.

weights(problem::ConstraintSatisfactionProblem) -> Vector

The weights of the constraints in the problem.

set_weights(problem::ConstraintSatisfactionProblem, weights) -> ConstraintSatisfactionProblem

Change the weights for the problem and return a new problem instance.

is_weighted(problem::ConstraintSatisfactionProblem) -> Bool

Check if the problem is weighted. Returns true if the problem has non-unit weights.

num_flavors(::Type{<:AbstractProblem}) -> Int
num_flavors(::GT) where GT<:AbstractProblem -> Int

Returns the number of flavors (domain) of a degree of freedom.

num_flavors(::GenericTensorNetwork{GT}) where GT<:ConstraintSatisfactionProblem -> 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.

hard_constraints(problem::AbstractProblem) -> Vector{HardConstraint}

The hard constraints of the problem.

is_satisfied(::Type{<:ConstraintSatisfactionProblem}, constraint::HardConstraint, config) -> Bool

Check if the constraint is satisfied by the configuration config.

local_solution_spec(problem::AbstractProblem) -> Vector{LocalSolutionSpec}

The constraints related to the size of the problem. Each term is associated with weights.

solution_size(problem::AbstractProblem, config) -> SolutionSize

Size of the problem given the configuration config.

energy_mode(problem::AbstractProblem) -> EnergyMode

The definition of the energy function, which can be LargerSizeIsBetter or SmallerSizeIsBetter. If will be used in the energy based modeling of the target problem.

LargerSizeIsBetter <: EnergyMode

The energy is defined as the negative size of the solution, which is the larger size the lower energy.

SmallerSizeIsBetter <: EnergyMode

The energy is defined as the size of the solution, which is the smaller size the lower energy.

energy(problem::AbstractProblem, config) -> Number

The energy of the problem given the configuration config. Please check the energy_mode for the definition of the energy function.

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(c::SetCovering, config)

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

is_set_packing(sp::SetPacking, config)

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

cut_size(g::AbstractGraph, config; weights=UnitWeight(ne(g)))

Return the size of the cut of the graph g with configuration config. The configuration is a vector of boolean numbers as the group indices of vertices. Edges between vertices in different groups are counted as a cut.

num_paint_shop_color_switch(sequence::AbstractVector, coloring)

Returns the number of color switches.

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

Under development

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(expr, config::AbstractDict{T}) where T

Check if the boolean expression expr is satisfied by the configuration config.

@bools(syms::Symbol...)

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

Example

Under Development

∨(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.

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

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 Constraint Satisfaction 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 constraint satisfaction problems.
• BLAS (on CPU) and GPU are supported only if K is Single,

CountingAll <: AbstractProperty
CountingAll()

Counting the total number of sets exactly without overflow. e.g. for the IndependentSet problem, it counts the independent sets. Note that PartitionFunction(0.0) also does the counting. It is more efficient, but uses floating point numbers, which does not have arbitrary precision.

• The corresponding tensor element type is BigInt.
• 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 constraint satisfaction 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 constraint satisfaction 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 constraint satisfaction 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 constraint satisfaction 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 constraint satisfaction 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 constraint satisfaction problem 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 constraint satisfaction problem 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, num_flavors=2)

Load configurations from file filename. The format is :binary or :text. If the format is :binary, the bitstring length bitlength must be specified, num_flavors 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, ExactTreewidth, 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(; α = 0.0, temperature = 0.0, nrepeat=10)

The fast but poor greedy optimizer. Input arguments are

* `α` is the parameter for the loss function, for pairwise interaction, L = size(out) - α * (size(in1) + size(in2))
* `temperature` is the parameter for sampling, if it is zero, the minimum loss is selected; for non-zero, the loss is selected by the Boltzmann distribution, given by p ~ exp(-loss/temperature).
* `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),
• sub_optimizer, the optimizer for the bipartited sub graphs, one can choose GreedyMethod() or TreeSA(),
• 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).

struct HyperGraph <: Graphs.AbstractGraph{Int64}

A hypergraph is a generalization of a graph in which an edge can connect any number of vertices.

Fields

• n::Int: the number of vertices
• edges::Vector{Vector{Int}}: a vector of vectors of integers, where each vector represents a hyperedge connecting the vertices with the corresponding indices.

struct UnitDiskGraph{D, T} <: Graphs.AbstractGraph{Int64}

A unit disk graph is a graph in which the vertices are points in a plane and two vertices are connected by an edge if and only if the Euclidean distance between them is at most a given radius.

Fields

• locations::Vector{NTuple{D, T}}: the locations of the vertices
• radius::Float64: the radius of the unit disk

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::ConstraintSatisfactionProblem, locs, configs::AbstractMatrix; kwargs...)
show_configs(graph::SimpleGraph, locs, configs::AbstractMatrix; num_flavors=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.

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