I can no longer edit my post, but I just noticed that the arrow is different from relational composition. The semiring in my post is still interesting for graphs though, especially for reachability.