search

snowleopard / alga

Algebraic graphs
MIT License
715 stars 68 forks source link

Track preSet for labelled adjmaps #311

Closed isovector closed 4 months ago

isovector commented 6 months ago

This PR changes the representation of labelled adjacencymaps in order to give preSet the same complexity as postSet. I couldn't wrap my mind around the necessary types to get closure working, but all other tests pass.

snowleopard commented 6 months ago

Hey @isovector, apologies for taking so long.

This seems like a very heavy-handed approach to me. This change affects every user of Labelled.AdjacencyMap, whether they need an efficient preSet or not. I think the number of applications where both preSet and postSet need to be efficient is pretty small. What's yours?

Could you just store two Labelled.AdjacencyMaps instead? It's not much worse in terms of performance and memory usage compared to the suggested implementation (but much simpler!).

(I think this PR is similar to suggesting that Data.Map is implemented by a bidirectional map because some applications want an efficient reverse mapping!)