Feature query on overlaying graphs with labels

[theohonohan]

Hello,

This is a followup to a question I asked on Twitter. I'm working on some code to calculate "betweenness centrality", with a view to applying it to streetmap graphs. I'm not sure if Alga is an appropriate choice for this task, but maybe my query will sort this out. I'm at the design stage.

To clarify what I'm talking about, there is a concise expression of the formula for betweenness centrality in the Wikipedia page. https://en.wikipedia.org/wiki/Betweenness_centrality

The end product is a graph with a floating point value associated with each vertex. I guess my key question is whether you envisage providing Alga with something like the unionsWith function from Data.Map. I'm imagining it would be called something like overlayWith and the supplied function would be used in a revised mergeVertex function to combine the values associated with the two vertices.

As far as I can see Alga doesn't seem to currently provide any tools for dealing with graphs with a value associated to each vertex, i.e. "labels". If it were to do so I assume that Data.Map would be one possible model for the interface. But I don't know if this is practical, or in any way on your roadmap.

I'm impressed by the elegance of your monoidal "overlay" approach to combining graphs, so I'd like to use it, with or without Alga. It solves the problem of folding all the routes together in the betweenness centrality calculation (represent each route as a graph, then overlay the whole lot while summing values at each vertex).

(As mentioned on Twitter, comonads might also come into this, but I'm not sure that they are really necessary. As the calculation involves a summation over shortest paths between every pair of vertices (resulting in an updated copy of the original graph) it seems like it could fit the comonad model. That's maybe not relevant to this Alga query, though graph algorithms expressed with comonads seems to be a fresh topic.)

[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!