Overlap Maps is not an iterator

[jpfairbanks]

@kris-brown, the maximum common c-set code is too slow for practical use, and I was trying to hunt down the problem with @p-stokes. It looks like this function was intended to be an iterator, but is actually realizing the whole collection.

https://github.com/AlgebraicJulia/Catlab.jl/blob/58e407be7e3a6186d53805c38a82c6b851a75d9a/src/categorical_algebra/CSets.jl#L1749

Shouldn't this code be something like

function overlap_maps(Xs::Vector{T}) where T<:ACSet
  !isempty(Xs) || error("Vector must not be empty")
  Xs = Xs[sortperm(total_parts.(Xs))] # put the smallest X first
  res = OrderedDict()
  overlapstream = map(hom.(SubobjectIterator(Xs[1])) do subobj
    abs_subobj = abstract_attributes(dom(subobj)) ⋅ subobj
    Y = dom(abs_subobj)
    # don't repeat work if already computed syms/maps for something iso to Y
    seen = false
    for (Y′, Y′maps) in collect(res)
      σ = isomorphism(Y′, Y)
      if !isnothing(σ)
        push!(Y′maps[1], σ ⋅ abs_subobj)
        seen = true
        break
      end
    end
    if seen continue end 
    # Compute the automorphisms so that we can remove spurious symmetries
    syms = isomorphisms(Y, Y)
    # Get monic maps from Y into each of the objects. The first comes for free
    maps = Vector{ACSetTransformation}[[abs_subobj]]
    for X in Xs[2:end]
      fs = homomorphisms(Y, X; monic=true)
      real_fs = Set() # quotient fs via automorphisms of Y
      for f in fs 
        if all(rf->all(σ -> force(σ⋅f) != force(rf),  syms), real_fs)  
          push!(real_fs, f)
        end
      end
      if isempty(real_fs)
        break # this subobject of Xs[1] does not have common overlap w/ all Xs
      else
        push!(maps,collect(real_fs))
      end
    end
    if length(maps) == length(Xs)
      return Y => maps
    end
  end
  return overlapstream
end

This will cause overlap_maps to instantly return a generator of the overlaps (as a sequence of pairs) rather than as an OrderedDict. Then when the MCA code iterates over that collection, it won't have to fully realize the collection before processing it?

[kris-brown]

There are subtle reasons why it's more complicated to turn this into an iterator (related to the fact that there can be distinct subobjects with isomorphic domains, so there's not a one-to-one correspondence of outputs of Subobjectiterator and the overlap iterator) but this is being addressed in https://github.com/AlgebraicJulia/Catlab.jl/pull/821

[epatters]

Resolved by #821.