Ease optimization by separately optimizing disconnected graph components

[mofeing]

Currently, optimizers think all the TN graph is connected. Although rare, there are cases in which disconnected components coexist in the same TN.

The optimizers should be able to run on them without any problem (maybe there are some edge-cases, but I wouldn't care about them until someone finds them) but their optimization should run smoother if optimization is run separately on each component, and then finally sum together.

We should have something like TensorOperations.connectedcomponents but implemented as sumtraces; i.e. like a transformation of an EinExpr.

[mofeing]

@lkdvos I've moved the discussion about disconnected components to here.

[lkdvos]

Great!

[lkdvos]

Let me quickly mention that it's not only an enhancement, it still just hangs: (this might be a good case to just add to the tests, it's easy to check that it produces the correct result :))

using EinExprs # master branch (134d7f07bbdfdd950df54a1680fcb0174a68ed38)
network = [[:a, :b], [:b, :c], [:A, :B], [:B, :C]]
expr = sum(EinExpr.(network))
optdata = Dict(key => 2 for key in unique(vcat(network...)))
einexpr(Exhaustive(), expr, optdata) # hangs

[Todorbsc]

network = [[:a, :b], [:b, :c], [:A, :B], [:B, :C]]
expr = sum(EinExpr.(network))
optdata = Dict(key => 2 for key in unique(vcat(network...)))
einexpr(Exhaustive(), expr, optdata) # hangs

This only happens with Exhaustive() optimizer, right?

Using Naive():

julia> expr_naive = einexpr(EinExprs.Naive(), expr, optdata)
EinExpr{Symbol}([:a, :c, :A, :C], EinExpr{Symbol}[EinExpr{Symbol}([:a, :c, :A, :B], EinExpr{Symbol}[EinExpr{Symbol}([:a, :c], EinExpr{Symbol}[EinExpr{Symbol}([:a, :b], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :c], EinExpr{Symbol}[])]), EinExpr{Symbol}([:A, :B], EinExpr{Symbol}[])]), EinExpr{Symbol}([:B, :C], EinExpr{Symbol}[])])

Using Greedy():

julia> expr_greedy = einexpr(Greedy(), expr, optdata)
EinExpr{Symbol}([:a, :c, :A, :C], EinExpr{Symbol}[EinExpr{Symbol}([:A, :B], EinExpr{Symbol}[]), EinExpr{Symbol}([:B, :C], EinExpr{Symbol}[]), EinExpr{Symbol}([:a, :c], EinExpr{Symbol}[EinExpr{Symbol}([:a, :b], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :c], EinExpr{Symbol}[])])])

[mofeing]

As far as we know, it only hangs in Exhaustive, but all optimizers should benefit.