Relational graph composition

[snowleopard]

Relational graph composition

[snowleopard]

@anfelor Yes!

In fact, this graph composition will also allow us to implement an instance of Dioid for labelled graphs, much like this is usually done with matrices whose elements are dioids. We will use |*| = compose.

[anfelor]

In the labelled graph setting, would the relational composition use the multiplication of our dioid
e. g. (a [ l ]> b) * (b [ k ]> c) = a [ l * k ]> c?

[snowleopard]

#148 provides an implementation of relational composition of algebraic graphs. Note that it is not as good as I hoped for: the size of the resulting expression is O(m1+m2), where m1 and m2 are the number of edges in the given graphs. Note however that the number of edges in the resulting graph may be quadratic, i.e. O(m1*m2), hence the algebraic representation is still very compact.

The implementation is quite short, the main trick is using biclique:

compose :: Ord a => Graph a -> Graph a -> Graph a
compose x y = overlays
    [ biclique xs ys
    | v <- Set.toList (AM.vertexSet mx `Set.union` AM.vertexSet my)
    , let xs = Set.toList (AM.postSet v mx), not (null xs)
    , let ys = Set.toList (AM.postSet v my), not (null ys) ]
  where
    mx = toAdjacencyMap (transpose x)
    my = toAdjacencyMap y

In combination with graph sparsification, this is quite powerful. I will write a blog post to explain how to combine sparsify and compose in an interesting way.