Improve documentation for edge-labelled graphs (maybe write a paper?)

[Kesanov]

trafficstars

The current API of labeled graphs does not seem to capture the notion of disconnected components well.

For example for Graph Bool String, both False / True and True / False can denote the lack of and the existence of an edge, respectively.

Therefore algorithms like shortestPath would require extra parameter noEdge : label -> Bool.

[snowleopard]

We expect the type of edge labels to be at least a monoid, and the identity element of this monoid corresponds to the non-edge. You can therefore implement noEdge:

noEdge :: (Monoid e, Eq e) => e -> Bool
noEdge e = (e == mempty)

There is a recent talk that should clarify this:

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

Admittedly, this needs to be documented much better. I haven't yet managed to write this up.

[Kesanov]

I tried to watch the video but it cannot be played because of "privacy issues".

Another question I have is how do you express a - b - c, because if connect behaves like join then in Connect True a (Connect True b c) a should be connected both to b and c.

5. 3. 2019 3:33 AM, 3:33 AM, Andrey Mokhov [email protected] napsal/a:

We expect the type of edge labels to be at least a monoid, and the identity element of this monoid corresponds to the non-edge. You can therefore implement noEdge:

noEdge :: (Monoid e, Eq e) => e -> Bool
noEdge e = (e == mempty)

There is a recent talk that should clarify this:

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

Admittedly, this needs to be documented much better. I haven't yet managed to write this up.

-- You are receiving this because you authored the thread. Reply to this email directly or view it on GitHub: https://github.com/snowleopard/alga/issues/175#issuecomment-469511298

[snowleopard]

I tried to watch the video but it cannot be played because of "privacy issues".

@Josef-Vonasek Strange, I just tried and it worked fine for me. It does require you to login though, e.g. using the GitHub account.

Another question I have is how do you express a - b - c, because if connect behaves like join then in Connect True a (Connect True b c) a should be connected both to b and c.

If we take the Boolean monoid with mempty = False and (<>) = (||), then your a - b - c example can be represented as Connect False (Connect True a b) (Connect True b c).

[adithyaov]

(maybe write a paper?)

@snowleopard Quite intriguing! Let me know if I can help :-)

[snowleopard]

@adithyaov If your acyclic graphs project succeeds, it may lead to some publishable results. Going through existing literature and writing an overview of existing approaches would be a good start.

[snowleopard]

Just adding a note about another issue with the documentation: right now it's not clear that in most cases we require the type of edges to be a commutative and idempotent monoid. For arbitrary monoids like Sum a few common properties will be violated, e.g. x + x == x, isSubgraphOf x x == True, etc. #221.