Edge Labelled Graph Monoid operation in use?

[jmatsushita]

Hi there,

I was wondering if I'm overlooking something: is the <> operation of an edge for a Labelled Graph ever used? Or is it only used for it's mempty value to "recover" Overlay? In which case, isn't something like Default or Pointed for e more accurate? It seems that haskellers don't like either because they don't have laws though, so I don't know if it makes sense.

Cheers,

Jun

[snowleopard]

@jmatsushita Hello! I think this talk explains why we need <+> for edge labels:

https://skillsmatter.com/skillscasts/12361-labelled-algebraic-graphs

Have you watched this? I'm afraid right now it's the only good explanation of edge-labelled algebraic graphs. If it's still unclear why we need <+>, please don't hesitate to ask further questions.

[noughtmare]

I get "Sorry, This video does not exist." when trying to view that video.

I'm currently trying to write a NFA/DFA library so I want to decorate the edges of my graph with token classes that are defined as follows:

data Token = Token String (Char -> Bool) 

instance Show Token where
  showsPrec _ (Token a _) = showString a

instance Eq Token where
  Token a _ == Token b _ = a == b

instance Semigroup Token

instance Monoid Token where
  mempty = emptyTok

emptyTok = Token "empty" (const False)

I really do not think that I should implement <> because it could either be conjunctive or disjunctive:

instance Semigroup Token where
  Token s1 f1 <> Token s2 f2 = Token (s1 ++ " or " ++ s2) (\x -> f1 x || f2 x)

Or conjunctive:

instance Semigroup Token where
  Token s1 f1 <> Token s2 f2 = Token (s1 ++ " and " ++ s2) (\x -> f1 x && f2 x)

Oh wait, I just realized that if I want mempty to be emptyTok then the semigroup needs to be disjunctive.

[adithyaov]

I get "Sorry, This video does not exist." when trying to view that video.

@noughtmare That is weird. I am able to watch the video. I wonder if the problem is with the ISP.

[adithyaov]

I was wondering if I'm overlooking something: is the <> operation of an edge for a Labelled Graph ever used?

@jmatsushita Could you please elaborate on this statement. <+> is an alias for <>. One use case: Describing generic algorithms on graphs. The algorithms work based on the Semiring used.

Please refer to #219 and #225 . The PR's are still incomplete but that's a simple use case.

[noughtmare]

I now realize that it might be because I do not have a proprietary content decryption module installed on my computers. Is there any DRM-free way of viewing this video?

On November 3, 2019 6:23:54 PM GMT+01:00, Adithya Kumar [email protected] wrote:

I get "Sorry, This video does not exist." when trying to view that video.

@noughtmare That is weird. I am able to watch the video.

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/snowleopard/alga/issues/240#issuecomment-549159439

[snowleopard]

I get "Sorry, This video does not exist." when trying to view that video.

@noughtmare Actually, I also get this now. This is strange because I can watch other videos from the same event. I've emailed the organisers to find out what happened.

[snowleopard]

In the meanwhile, I put the slides here:

https://www.staff.ncl.ac.uk/andrey.mokhov/labelled-algebraic-graphs-slides.pdf

See part 3.

[goldnd]

I get a 403 error trying to access the slides.

[snowleopard]

@goldnd The slides link works fine for me. Anyway, I attached the PDF to this comment.

labelled-algebraic-graphs-slides.pdf

As for the video recording, I'm afraid Skills Matter went into administration, so it's unclear whether the video will ever become available again :(

[snowleopard]

Hi all, Skills Matter videos are finally back, and so is the video we were looking for 🎉

https://skillsmatter.com/skillscasts/12361-labelled-algebraic-graphs

[jmatsushita]

I'm looking at this now with a bit more familiarity with alga and I realise that my question doesn't make a lot of sense, except if you understand it in this way (which could also still not make a lot of sense): Is the semiring structure of Label related to the semiring-ish structure of Graph, tying it back to my question, is mempty/zero some arbitrary choice of label value, or is it a choice that somehow relates to the semiring-ish laws for Graphs.

Another way to say this is, the edge type can represent the ways in which vertices are connected, which can include a particular value which means they are not connected (a.k.a overlaid). How does the structure of edge types/labels relate to the structure of Graphs?

[snowleopard]

tying it back to my question, is mempty/zero some arbitrary choice of label value, or is it a choice that somehow relates to the semiring-ish laws for Graphs.

@jmatsushita No, it's not an arbitrary choice, more like an inevitable one :)

Semirings generalise the notion of connectivity and, as you remark, they provide a way to describe the lack of any connectivity, which is the zero of the semiring. In algebraic graphs, the lack of connectivity corresponds to graph overlay. Therefore, labelling a connection between two vertices with zero must mean the same thing as overlaying these vertices.

Let me show you another interesting relation between unlabelled algebraic graphs and semiring-labelled graphs.

Consider the following law:

• Parallel composition: a -<x>- b <> a -<y>- b = a -<x+y>- b where + is the semiring's addition and <> is algebraic graphs's overlay.

This law matches with the meaning of + in semirings: indeed, addition corresponds to the parallel composition of connectivities (this is not me inventing things, this is standard when using semirings to model connectivity).

Now let's see what happens if x=0 and y=1.

a -<x>- b  <>  a -<y>- b = a -<x+y>- b
a -<0>- b  <>  a -<1>- b = a -<0+1>- b
a <> b     <>  a -<1>- b = a -<1>- b

What shall a -<1>- b mean? Well, if a -<0>- b means overlay, then it's quite natural to say that connected vertices should correspond to the connect operator. Then, the above leads to one of the standard properties of algebraic graphs: a <> b <> connect a b = connect a b, that is, endpoints a and b of a connect a b are contained in the result.

P.S.: I'm working on a paper that will hopefully describe all these ideas in a clearer way.