Relational graph composition

[snowleopard]

The following relational graph composition operation is useful for various reachability algorithms but I can't figure out an efficient implementation.

Let z = compose x y. Then:

• Ez = Ey ∘ Ex, i.e. we compose edge sets using the relational composition ∘. In other words, an edge (a,c) belongs to z only if there are edges (a,b) and (b,c) in x and y, respectively.
• Vz contains all non-isolated vertices from both graphs.

This is a very natural composition operator and ideally I'd like to get the linear size complexity, i.e. the size of the resulting expression |z| should be O(|x|+|y|). However, I suspect that this may be impossible, so something like O((|x|+|y|)*log(|x|+|y|)) would be interesting too.

Also note that this (roughly) corresponds to the multiplication of the underlying connectivity matrices.

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

@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.

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