Feature query on overlaying graphs with labels

[theohonohan]

Feature query on overlaying graphs with labels

[snowleopard]

@theohonohan Thank you, I didn't expect the overlay composition may be useful for computing metrics such as betweenness centrality! I think I understand your idea on an intuitive level, but I'd be interested to see some more details.

There are a few different ways of attaching labels to vertices. What about the following direct approach?

-- Here t is the type of labels. 
type LabelledGraph t a = (Graph a, Map a t)

overlayWith :: (t -> t -> t) -> LabelledGraph t a -> LabelledGraph t a -> LabelledGraph t a
overlayWith f (g1, l1) (g2, l2) = (overlay g1 g2, Map.unionWith f l1 l2)

At the moment Alga does not provide any out-of-the-box approaches to dealing with labelled vertices, because I'm not sure whether there is one which is clearly the best to merit its inclusion into the API. The above seems to be relatively easy to add on top of Alga, and I presume there may be others, e.g. one could use the labelling function a -> t instead of the map Map a t.

Does the above work for you?

P.S.: By the way, from your description it looks like you do not need edge labels. Note that adding support for edge labels seems to be a more complicated issue: #17.

[theohonohan]

Hello,

Thanks for the response. For the geographic application I have in mind for the code, I do need to be able to label edges. I had a quick look at the issue #17 (and will revisit it later) but concretely I think something as simple as this would work for my application:

-- Edge and node labels are both of type Double.
-- Graph edges are represented by entries in a Map indexed by (Integer, Integer).
type Graph = (Map (Integer, Integer) Double, Map Integer Double)

overlaySummingNodeValues :: Graph -> Graph -> Graph
overlaySummingNodeValues (e1, n1) (e2, n2) = (Map.union e1 e2, Map.unionWith (+) n1 n2)

The comonad idea is to use the comonad's extend method to 'stuff' a copy of the whole graph into each of the nodes. Since the code needs to sum over every route for every node in the graph, each of those graphs would then be extended a second time, this time stuffing each node with (the union/overlay) of routes back to the enclosing node. Then overlay gets called twice (as the comonadic 'extract') to produce the end result. Maybe this is all a bit silly and trendy -- after all the summation calculation is just a hylomorphism.

This blog post discusses somewhat similar operations: http://blog.higher-order.com/blog/2016/04/02/a-comonad-of-graph-decompositions/

[snowleopard]

Thanks @theohonohan! I enjoyed both the blog post and the paper you linked to previously. I'll experiment with adding comonads to Alga.

Your simple graph type will probably work, although it suffers from the usual problem with standard graph representations: you can create non-graphs with edges pointing to non-existent vertices.

In your overlaySummingNodeValues function, I suppose you meant to use Map.unionWith for edges too?

[theohonohan]

Hi,

My code doodle might have been disconcertingly concrete. In the streetmap application I have in mind, vertices represent points in space and edges are straight line connections. In other words, it's a physical mesh embedded in a metric space. Each edge needs to be labelled with its length, but once labelled, the length won't change, hence i ignored it (not inspected) when overlaying.

BTW, obviously an operation like a labeling a whole clique of edges with the same value is a million miles from what I'm considering.

Of course my code is not entirely safe, and I appreciate the potential of a rigorous graph construction with Alga, which is why I'm interested in the library. The ad-hoc approach you suggested (using a map to store node labels) could also fail at runtime if a node was unlabelled, which suggests to me that vertex types probably shouldn't be exposed by the library lest they be used as pointers!

I wonder if lenses would be useful in wrapping all this up in an abstraction? It seems reasonable to want to be able to access the set of node or edge labels as a functor, and lenses could provide an interface to read/write that kind of "view" of the data.

Anyway, thanks for a constructive discussion so far. Very helpful and encouraging.

[snowleopard]

In other words, it's a physical mesh embedded in a metric space.

Aha, it appears that one doesn't even need to store the edge labels in this case, because they are implicitly determined by their endpoints! It's probably a useful subclass of graphs to consider: graphs that can be characterised by the pair (Graph a, (a, a) -> b) where the edge labelling function (a, a) -> b is total.

I wonder if lenses would be useful in wrapping all this up in an abstraction? It seems reasonable to want to be able to access the set of node or edge labels as a functor, and lenses could provide an interface to read/write that kind of "view" of the data.

Yes, this is an interesting direction to explore.

One can access the set of vertices as a Functor (the Graph datatype has the Functor instance), but not edges. I recently came across this graph library: https://github.com/DAHeath/ord-graph. It does use lenses for accessing both vertices and edges, so perhaps this is what you have in mind?

Anyway, thanks for a constructive discussion so far. Very helpful and encouraging.

Thank you too!