Should Graph / AdjacencyMap have StarSemiring instances

[dalaing]

I was reading this before I got a chance to properly look at alga, and was pretty happy to see the StarSemiring class in Algebra.Graph.Label.

Would there be interest in adding instances of that for Algebra.Graph.Labelled and Algebra.Graph.Labelled.AdjacencyMap? I might be able to squirrel some time away to work on that.

(I'm also staring at the hint at the end of that post about using eliminants to speed up shortest path calculations between two points, and am keen to play around with that at some point).

[dalaing]

Hmm. I've looked at this a little, and it seems like the post I linked is able to implement one because of the representation that they have chosen for matrices, and that is quite different.

I can see that there might be the ability to do something like storing a value to add to the self loops:

data AdjacencyMap e a = AM {
    -- | The /adjacency map/ of an edge-labelled graph: each vertex is
    -- associated with a map from its direct successors to the corresponding
    -- edge labels.
    adjacencyMap :: Map a (Map a e)
  , selfLoopAddition :: e  
  }

so that you can define:

one = AdjacencyMap mempty one

but I don't know how much that would complicate everything else.

I'll ponder some more.

[snowleopard]

Could you clarify how you plan to make use of the StarSemiring Graph instance? If it is just for computing the closure, then you can simply use the closure function. Or are you planning to label edges of some other graph with graphs? :)

[dalaing]

Hmm, on reflection I think I just like the idea of expressing graphs using the Semigroup / Monoid / Semiring / StarSemiring / Dioid heirarchy, where everything is lawful.

It might be too much of a breaking change to shift away from the not-quite-a-ring Num instance though. Maybe I should shift all of my pondering over to the eliminant stuff :)

[snowleopard]

We could probably have an instance like this:

• zero = empty
• <+> = overlay
• <.> = compose
• one = identity -- where identity :: Graph a contains all vertices of the type a, each with a self-loop

I agree that such an instance is nice, because it makes the whole star semiring story complete, but I just don't see any practical use for it yet. But maybe there is! :)