Separate path optimization of disconnected components in the network graph #53

Todorbsc · 2024-02-09T18:28:31Z

Closes #51

mofeing

Very well with the implementation. But keep in count the following things:

Hyperindices may appear
- For this case, it would be enough to consider them as all-to-all connections
Current implementation doesn't preserver output open indices
- Check out how you sum the EinExprs in the end
dfs maybe suits better in Utils.jl
There is another implementation in Graphs.jl that doesn't use recursion https://github.com/JuliaGraphs/Graphs.jl/blob/0c29f25a00967b575cf29b602f21fda8269a76f8/src/connectivity.jl#L13
- This way, we wouldn't need dfs and its code could be all inside the components function

mofeing · 2024-02-11T18:02:41Z

src/Optimizers/Greedy.jl

@@ -27,7 +27,7 @@ The implementation uses a binary heaptree to sort candidate pairwise tensor cont
    outer::Bool = false
 end

-function einexpr(config::Greedy, path::EinExpr{L}, sizedict::Dict{L}) where {L}
+function einexpr(config::Greedy, sizedict::Dict{L}, path::EinExpr{L}) where {L}


Why change the order?

Because of the multiple dispatching: this way, all optimizers' einexpr function are called through Optimizers.einexpr when the function call is like the one suggested in the issue #51:

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)

Although I am not really convinced about this fix, it makes possible to call the optimizers with each of the non-interconnected subgraphs at the level of abstraction of the class Optimizers avoiding the need to modify each specific optimizer.

Let me know what are your thoughts on this and whether there's another more-suitable way to implement this.

mofeing · 2024-02-11T18:03:04Z

src/Optimizers/Greedy.jl

@@ -70,4 +70,4 @@ function einexpr(config::Greedy, path::EinExpr{L}, sizedict::Dict{L}) where {L}
    return path
 end

-einexpr(config::Greedy, path::SizedEinExpr) = SizedEinExpr(einexpr(config, path.path, path.size), path.size)
+einexpr(config::Greedy, path::SizedEinExpr) = SizedEinExpr(einexpr(config, path.size, path.path), path.size)


Same as above: why change the order?

mofeing · 2024-02-11T18:48:17Z

src/EinExpr.jl

+    network = [args.head for args in path.args]
+    # create adjacency graph of the network
+    tengraph = zeros(Bool, length(network), length(network))
+    for i in 1:length(network)
+        for j in 1:length(network)
+            if !isempty(network[i] ∩ network[j]) && i ≠ j
+                tengraph[i,j] = true
+            end
+        end
+    end


Nice! But let's rewrite it like this:

Suggested change

network = [args.head for args in path.args]

# create adjacency graph of the network

tengraph = zeros(Bool, length(network), length(network))

for i in 1:length(network)

for j in 1:length(network)

if !isempty(network[i] ∩ network[j]) && i ≠ j

tengraph[i,j] = true

end

end

end

network = map(head, path.args)

# create adjacency matrix of the network

n = nargs(path)

adjmat = falses(n,n)

for (i,j) in combinations(1:n, 2)

if !isdisjoint(network[i], network[j])

adjmat[i,j] = true

adjmat[j,i] = true

end

end

mofeing · 2024-02-11T20:53:43Z

src/EinExpr.jl

+    # find disconneceted subgraphs
+    subgraphs = Vector{Vector{Int}}()
+    n = size(tengraph, 1)
+    visited = falses(n)
+    for v in 1:n
+        if !visited[v]
+            subgraph = Int[]
+            dfs(tengraph, v, visited, subgraph)
+            push!(subgraphs, subgraph)
+        end
+    end
+
+    # create subnetworks
+    indeppaths = [sum(EinExpr.([network[tns] for tns in subnet])) for subnet in subgraphs]
+
+    return indeppaths


Continuing with above

Suggested change

# find disconneceted subgraphs

subgraphs = Vector{Vector{Int}}()

n = size(tengraph, 1)

visited = falses(n)

for v in 1:n

if !visited[v]

subgraph = Int[]

dfs(tengraph, v, visited, subgraph)

push!(subgraphs, subgraph)

end

end

# create subnetworks

indeppaths = [sum(EinExpr.([network[tns] for tns in subnet])) for subnet in subgraphs]

return indeppaths

# find disconneceted subgraphs

subgraphs = Vector{Vector{Int}}()

visited = falses(n)

for vertex in Iterators.filter(v -> !visited[v], 1:n)

subgraph = Int[]

dfs(adjmat, vertex, visited, subgraph)

push!(subgraphs, subgraph)

end

# create subnetworks

indeppaths = [sum(EinExpr.([network[tns] for tns in subnet])) for subnet in subgraphs]

return indeppaths

jofrevalles · 2024-02-12T08:24:35Z

src/Optimizers/Optimizers.jl

@@ -3,7 +3,7 @@ abstract type Optimizer end
 function einexpr end

 einexpr(T::Type{<:Optimizer}, args...; kwargs...) = einexpr(T(; kwargs...), args...)
-einexpr(config::Optimizer, expr, sizedict) = einexpr(config, SizedEinExpr(expr, sizedict))
+einexpr(config::Optimizer, expr, sizedict) = sum(einexpr.((config,), [SizedEinExpr(exp, sizedict) for exp in [comp for comp in components(expr)]]))


Suggested change

einexpr(config::Optimizer, expr, sizedict) = sum(einexpr.((config,), [SizedEinExpr(exp, sizedict) for exp in [comp for comp in components(expr)]]))

einexpr(config::Optimizer, expr, sizedict) = sum(einexpr.((config,), map(exp -> SizedEinExpr(exp, sizedict), components(expr))))

Maybe it could be rewritten like this?

Yeah, I completely agree. I guess I am still getting used to Julia haha
Made the change! Thanks

Todorbsc · 2024-02-13T13:14:57Z

Very well with the implementation. But keep in count the following things:

Hyperindices may appear

For this case, it would be enough to consider them as all-to-all connections

Current implementation doesn't preserve output open indices

Check out how you sum the EinExprs in the end

~~dfs maybe suits better in Utils.jl~~

There is another implementation in Graphs.jl that doesn't use recursion https://github.com/JuliaGraphs/Graphs.jl/blob/0c29f25a00967b575cf29b602f21fda8269a76f8/src/connectivity.jl#L13

This way, we wouldn't need dfs and its code could be all inside the components function

I did the last two points. I have to check for the hyperindices and the output open indices cases.

Todorbsc · 2024-02-16T11:43:58Z

I found something related to the hyperindices that may be a bug: when calling hyperinds with the expression, each hyperindex is repeated a number of times equal to the number of edges of the hyperindex. Also, there are no hyperindices in the obtained expression after the optimization (here it is exemplified with Greedy but the list of hyperindices is empty for all optimizers).

Example with 1 hyperindex of 3 edges:

julia> using EinExprs

julia> network = [[:a, :b], [:b, :c], [:b, :d]]
3-element Vector{Vector{Symbol}}:
 [:a, :b]
 [:b, :c]
 [:b, :d]

julia> expr = sum(EinExpr.(network))
EinExpr{Symbol}([:a, :c, :d], EinExpr{Symbol}[EinExpr{Symbol}([:a, :b], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :c], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :d], EinExpr{Symbol}[])])

julia> optdata = Dict(key => 2 for key in unique(vcat(network...)))
Dict{Symbol, Int64} with 4 entries:
  :a => 2
  :b => 2
  :d => 2
  :c => 2

julia> greedy = einexpr(Greedy(), expr, optdata)
SizedEinExpr{Symbol}(EinExpr{Symbol}([:a, :c, :d], EinExpr{Symbol}[EinExpr{Symbol}([:a, :c, :d], EinExpr{Symbol}[EinExpr{Symbol}([:b, :d], EinExpr{Symbol}[]), EinExpr{Symbol}([:a, :b, :c], EinExpr{Symbol}[EinExpr{Symbol}([:a, :b], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :c], EinExpr{Symbol}[])])])]), Dict(:a => 2, :b => 2, :d => 2, :c => 2))

julia> hyperinds(expr)
3-element Vector{Symbol}:
 :b
 :b
 :b

julia> hyperinds(greedy)
Symbol[]

Example with 1 hyperindex of 4 edges:

julia> network = [[:a, :b], [:b, :c], [:b, :d], [:b, :e]]
4-element Vector{Vector{Symbol}}:
 [:a, :b]
 [:b, :c]
 [:b, :d]
 [:b, :e]

julia> expr = sum(EinExpr.(network))
EinExpr{Symbol}([:a, :c, :d, :e], EinExpr{Symbol}[EinExpr{Symbol}([:a, :b], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :c], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :d], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :e], EinExpr{Symbol}[])])

julia> optdata = Dict(key => 2 for key in unique(vcat(network...)))
Dict{Symbol, Int64} with 5 entries:
  :a => 2
  :b => 2
  :d => 2
  :e => 2
  :c => 2

julia> greedy = einexpr(Greedy(), expr, optdata)
SizedEinExpr{Symbol}(EinExpr{Symbol}([:a, :c, :d, :e], EinExpr{Symbol}[EinExpr{Symbol}([:a, :c, :d, :e], EinExpr{Symbol}[EinExpr{Symbol}([:b, :e], EinExpr{Symbol}[]), EinExpr{Symbol}([:a, :c, :d], EinExpr{Symbol}[EinExpr{Symbol}([:a, :b, :c], EinExpr{Symbol}[EinExpr{Symbol}([:a, :b], EinExpr{Symbol}[]), EinExpr{Symbol}([:b, :c], EinExpr{Symbol}[])]), EinExpr{Symbol}([:b, :d], EinExpr{Symbol}[])])])]), Dict(:a => 2, :b => 2, :d => 2, :e => 2, :c => 2))

julia> hyperinds(expr)
4-element Vector{Symbol}:
 :b
 :b
 :b
 :b

julia> hyperinds(greedy)
Symbol[]

Todorbsc added 4 commits February 9, 2024 19:23

Implement function to find path disconnected components

474427d

Fix einexpr function to respect Optimizers abstract class method

4484f5d

Separate optimization for each disconnected components in path

0700b48

Merge branch 'master' into fix/issue51_separe_disconn_graphs_opt

ba187ec

mofeing requested changes Feb 11, 2024

View reviewed changes

jofrevalles requested changes Feb 12, 2024

View reviewed changes

Todorbsc added 4 commits February 13, 2024 13:41

Fix code style

95af947

Fix code style

4a1993c

Fix code style

2fc3371

Replace dfs function by connected_components from Graphs package

48f18fc

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Separate path optimization of disconnected components in the network graph #53

Separate path optimization of disconnected components in the network graph #53

Todorbsc commented Feb 9, 2024 •

edited

mofeing left a comment

mofeing Feb 11, 2024

Todorbsc Feb 13, 2024 •

edited

mofeing Feb 11, 2024

mofeing Feb 11, 2024

Todorbsc Feb 13, 2024

mofeing Feb 11, 2024

Todorbsc Feb 13, 2024

jofrevalles Feb 12, 2024

Todorbsc Feb 13, 2024

Todorbsc commented Feb 13, 2024 •

edited

Todorbsc commented Feb 16, 2024 •

edited

-    network = [args.head for args in path.args]
-    # create adjacency graph of the network
-    tengraph = zeros(Bool, length(network), length(network))
-    for i in 1:length(network)
-        for j in 1:length(network)
-            if !isempty(network[i] ∩ network[j]) && i ≠ j
-                tengraph[i,j] = true
-            end
-        end
-    end
+    network = map(head, path.args)
+    # create adjacency matrix of the network
+    n = nargs(path)
+    adjmat = falses(n,n)
+    for (i,j) in combinations(1:n, 2)
+        if !isdisjoint(network[i], network[j])
+            adjmat[i,j] = true
+            adjmat[j,i] = true
+        end
+    end

	einexpr(config::Optimizer, expr, sizedict) = sum(einexpr.((config,), [SizedEinExpr(exp, sizedict) for exp in [comp for comp in components(expr)]]))
	einexpr(config::Optimizer, expr, sizedict) = sum(einexpr.((config,), map(exp -> SizedEinExpr(exp, sizedict), components(expr))))

Separate path optimization of disconnected components in the network graph #53

Are you sure you want to change the base?

Separate path optimization of disconnected components in the network graph #53

Conversation

Todorbsc commented Feb 9, 2024 • edited

mofeing left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Todorbsc Feb 13, 2024 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Todorbsc commented Feb 13, 2024 • edited

Todorbsc commented Feb 16, 2024 • edited

Todorbsc commented Feb 9, 2024 •

edited

Todorbsc Feb 13, 2024 •

edited

Todorbsc commented Feb 13, 2024 •

edited

Todorbsc commented Feb 16, 2024 •

edited