Exhaustive optimizer hangs indefinitely if self-loops (i.e. traces) are present

[lkdvos]

I was running some benchmarks on random networks, and ran into the following issue:

ex_problem = sum([EinExpr([1, 1]), EinExpr([2, 3]), EinExpr([3, 4])])
sized_ex_problem = SizedEinExpr(ex_problem, Dict(i => 2 for i in 1:4))
einexpr(Exhaustive(; outer=true), sized_ex_problem) # works
einexpr(Exhaustive(; outer=false), sized_ex_problem) # hangs

The problem here being that even though I would want the algorithm to not consider outer products in general, the network does consist of actual disconnected components, and needs an outer product to connect these. In particular, this does not increase the complexity of the algorithm to $O(n!)$ (I think), because I just want to handle the sub-components separately, without considering outer products within them.

In any case, I feel like there should probably be at least some error being thrown, instead of just being stuck in an infinite loop somewhere.

[mofeing]

The bug seems to be due to self-loops in the TN (i.e. traces). If we remove them, everything works correctly:

using TensorOperations: TensorOperations, optimaltree
using EinExprs

alg = Exhaustive(; strategy=:breadth)

einex = EinExpr{Int64}([-1, -2, -3, -4, -5, -6, -7, -8, -9], EinExpr{Int64}[EinExpr{Int64}([12, -1, 20], EinExpr{Int64}[]), EinExpr{Int64}([18], EinExpr{Int64}[]), EinExpr{Int64}([6, 3, 8, 17], EinExpr{Int64}[]), EinExpr{Int64}([24, 22, 16], EinExpr{Int64}[]), EinExpr{Int64}([11, 1, 9], EinExpr{Int64}[]), EinExpr{Int64}([6, 5], EinExpr{Int64}[]), EinExpr{Int64}([7], EinExpr{Int64}[]), EinExpr{Int64}([11, 7], EinExpr{Int64}[]), EinExpr{Int64}([13, -5, 2], EinExpr{Int64}[]), EinExpr{Int64}([-8, 15], EinExpr{Int64}[]), EinExpr{Int64}([16, 21, 9], EinExpr{Int64}[]), EinExpr{Int64}([25, -9, 10, 10], EinExpr{Int64}[]), EinExpr{Int64}([15, -7, 4], EinExpr{Int64}[]), EinExpr{Int64}([26, 24, 13], EinExpr{Int64}[]), EinExpr{Int64}([-6, 18, 2, 1], EinExpr{Int64}[]), EinExpr{Int64}([-4, 21, 25], EinExpr{Int64}[]), EinExpr{Int64}([20, 4, 19, 22], EinExpr{Int64}[]), EinExpr{Int64}([14, 23, 8, 14], EinExpr{Int64}[]), EinExpr{Int64}([17, 26, -2, 19], EinExpr{Int64}[]), EinExpr{Int64}([3, -3, 23, 5], EinExpr{Int64}[]), EinExpr{Int64}([12], EinExpr{Int64}[])])
sizedict = Dict{Int,Int}(i => 2 for i in inds(einex))

network = map(leaves(einex)) do leave
    leave.head
end

n = length(network)
adjmat = falses(n, n)
for i in 1:n, j in 1:n
    if i != j
        adjmat[i, j] = !isdisjoint(network[i], network[j])
    end
end

TensorOperations.connectedcomponents(adjmat) # only 1 component

TensorOperations.optimaltree(network, sizedict) # works well

sexpr = SizedEinExpr(einex, sizedict)
# einexpr(alg, sexpr) # HANGS

filter!(!=(10), einex.args[12].head)
filter!(!=(14), einex.args[18].head)
sexpr = SizedEinExpr(einex, sizedict)
einexpr(alg, sexpr) # works well

[mofeing]

Fixed in ebb683d