Implement Algebra.Graph.Undirected

[adicirstei]

Hi,

I have a dumb question. At first I thought that a SymmetricRelation being a Graph and a Graph being a Functor I just can map a function over it. I was wrong as the Graph was the the class not the data type.

Any advice on an efficient way on how to do this?

Thanks!

[snowleopard]

@adicirstei Hi there!

SymmetricRelation is an instance of the type class Graph but it cannot be made an instance of Functor because it is internally represented by Data.Set which requires the Ord a constraint.

We can define a function gmap :: Ord b => (a -> b) -> SymmetricRelation a -> SymmetricRelation b but it's not polymorphic enough to be used as Functor's fmap.

In fact, we have Relation.gmap:

https://github.com/snowleopard/alga/blob/master/src/Algebra/Graph/Relation.hs#L497-L510

So, we can easily add SymmetricRelation.gmap by wrapping and unwrapping the newtype. Will that work for you?

[snowleopard]

An alternative would be to add Algebra.Graph.Undirected that would be a simple wrapper around Graph data type defined in Algebra.Graph, which is a proper Functor.

Then we would be able to define the instance Functor UndirectedGraph.

[adicirstei]

What would involve doing UndirectedGraph ?

[snowleopard]

@adicirstei The simplest way forward is to define a newtype:

newtype UndirectedGraph a = UndirectedGraph { graph :: Graph a } deriving (Functor, ... )

Then add a custom Eq instance, and modify a couple of graph algorithms to correctly deal with undirected edges. Most of the API of this module would simply redirect to the inner graph.

[adicirstei]

Great! I wasn’t sure how you were seeing it. Adrian

…

On 20 Jun 2018, at 19:24, Andrey Mokhov ***@***.***> wrote: @adicirstei The simplest way forward is to define a newtype: newtype UndirectedGraph a = UndirectedGraph { graph :: Graph a } deriving (Functor, ... ) Then add a custom Eq instance, and modify a couple of graph algorithms to correctly deal with undirected edges. Most of the API of this module would simply redirect to the inner graph. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[snowleopard]

@adicirstei Would you like to give this a try? I think it would be nice to add Algebra.Graph.Undirected to the library.

[snowleopard]

If anyone would like to attempt this, we now have Symmetric.Relation whose API can be followed:

https://hackage.haskell.org/package/algebraic-graphs-0.4/docs/Algebra-Graph-Relation-Symmetric.html

[bolt12]

@adicirstei are you working on this issue? If not, I'd be glad to give this a try!

EDIT: @snowleopard would this replace this SymmetricRelation? Or would it be just an adapted API to work with the Graph data type?
Also, could you walk me trough how do you use ghci/cabal new-repl? I'm having trouble with some hidden package errors

[snowleopard]

@bolt12 No, this is independent from your symmetric relations work.

The implementation will be quite similar though: just add a newtype Algebra.Graph.Undirected.Graph wrapping the algebraic data type Graph and providing an API based on the one you implemented for symmetric relations.

[snowleopard]

Also, could you walk me trough how do you use ghci/cabal new-repl?

For me both ghci and stack ghci seem to work.

P.S.: I assigned this issue to you. Thanks for volunteering! :)

[bolt12]

@snowleopard No problem! I'm happy to help!

That's odd, I'll try and refork the repo!

[bolt12]

@snowleopard sorry to bloat this thread with this issue but can you figure out how to solve this?
I reforked the repo and ran ghci on the project root:

[snowleopard]

@bolt12 Not sure how to fix this at the moment. Let's fork this into a new issue.

[bolt12]

@snowleopard looking into this. I built the project and ghci runs fine! cabal new-repl on the other hand cannot gives the same error but for QuickCheck. Probably it's because i'm unexperienced with the new version of cabal. I'll stick with ghci

[bolt12]

@snowleopard one question: should I use the Symmetric file as base or the Graph one? What would be preferable? Also the Graph one has rewrite rules and other stuff that I don't quite understand, but since it's a newtype I dont think I need to worry about them.

EDIT: I'll base on one file for documentation inspiration and guidance mainly but I'll still follow the SymmetricRelation API! Probably there will be things that would be worth adding from the Graph that aren't in Symmetric like (===), induceJust (?)

[snowleopard]

@bolt12 Yes, in general please follow the API of Symmetric.Relation.

Don't worry about the rewrite rules for now.

[snowleopard]

I think we can close this now, since the latest version has:

http://hackage.haskell.org/package/algebraic-graphs-0.5/docs/Algebra-Graph-Undirected.html

Thanks @bolt12!

[bolt12]

Awesome! You're welcome, it was a pleasure working with you in this PR!

…

On Sat, 15 Feb 2020, 19:48 Andrey Mokhov, ***@***.***> wrote: Closed #83 <#83>. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#83?email_source=notifications&email_token=AE2SULL5EHS35I7BVD3VNETRDBBJTA5CNFSM4FF4OD32YY3PNVWWK3TUL52HS4DFWZEXG43VMVCXMZLOORHG65DJMZUWGYLUNFXW5KTDN5WW2ZLOORPWSZGOWVBZSZI#event-3041106277>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AE2SULP4TL4FLC7BZB3UO7DRDBBJTANCNFSM4FF4OD3Q> .