search

snowleopard / alga

Algebraic graphs
MIT License
715 stars 68 forks source link

Doubt about decorating a Graph #288

Closed ffaf1 closed 2 years ago

ffaf1 commented 2 years ago

Hello. My goal is pretty simple: I have a Graph a and I would like to decorate each graph with a unique label, to end up with — say —, Graph (Int, a).

If I were to do this on Trees I would use a traversable instance or similar, but I see Graph has no such instance. What is the correct way to approach this?

snowleopard commented 2 years ago

Indeed, there is currently no nice way to do it in the API. We used to provide a Traversable instance but that was pretty broken. For example, decorating a tree overlay (vertex 'a') (vertex 'a') would give you overlay (vertex (1,'a')) (vertex (2,'a')), which is most likely not what you want. This is why we dropped the instance.

I don't see anything better than just coming up with a unique labelling f :: a -> Int and then calling gmap f.

Is that acceptable for your use case?

ffaf1 commented 2 years ago

Thanks Andrey, so some sort of hash function; that would do.

I would like my IDs to be contiguous, but I guess that could be rectified by having getting the list of unique IDs, zipping it with [1..] and running gmap again.

snowleopard commented 2 years ago

Yes, although you don't have to go through the intermediate state with hashes. You could zip the deduplicated list of vertices with [1..], create a map from the resulting list of pairs, and pass that map's lookup function to gmap.

I admit it's pretty fiddly and it would be nice to have something in the API that would make this sort of transform easier to make.

ffaf1 commented 2 years ago

Ah, indeed that is smarter! Thanks again.

Il 08 aprile 2022 alle 04:19 Andrey Mokhov ha scritto:

Yes, although you don't have to go through the intermediate state with hashes. You could zip the deduplicated list of vertices with [1..], create a map from the resulting list of pairs, and pass that map's lookup function to gmap.

I admit it's pretty fiddly and it would be nice to have something in the API that would make this sort of transform easier to make.

-- Reply to this email directly or view it on GitHub: https://github.com/snowleopard/alga/issues/288#issuecomment-1092756681 You are receiving this because you modified the open/close state.

Message ID: @.***>