Optional methods for Graph type class

[snowleopard]

Optional methods for Graph type class

[ndmitchell]

If the type class changes as I suggest in #5 then most of these objections change in nature - so I suggest we resolve that before coming back to this.

[ndmitchell]

The GraphWithFastRemoveVertex seems a bit grim - you end up with N classes. And note that removeVertex isn't O(n) - it's only that if you use something with constant time construction for all operations, and only works if you start with a GraphMonad.

I think there is potential value in putting a small number of carefully chosen operations in the class, which can be implemented 100% generically, but for certain classes of graph are vastly more efficient. The other option is to say they are only implemented in a few choice data types, typically imported qualified, and people are expected to convert.

[snowleopard]

The GraphWithFastRemoveVertex seems a bit grim - you end up with N classes.
I think there is potential value in putting a small number of carefully chosen operations in the class

@ndmitchell Shall we list the candidates here? I'm starting to think that there are not that many of them. The removeVertex operation does seem to make sense for all inhabitants of the Graph type class, because it corresponds to the vertex method. But removeEdge on the other hand is already problematic, because some instances, like ToList would find it awkward to have it, even though they can implement it very efficiently as a no-op. Note, there is no explicit notion of edges in the type class itself.

Is there any other candidate to bring N above 1? :)

P.S.: For various newtype's like GraphFunctor the requirement to also handle removeVertex is actually a burden. Presumably, this will become a common theme: the larger the core, the more often one needs to handle cases that may be irrelevant for the task at hand.

[snowleopard]

After a lot of refactoring, we ended up with the API where each Graph instance defines a bunch of custom functions, such as isEmpty, hasVertex, vertices, removeVertex, and many others, which all have different complexity characteristics.

See: http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph.html

Making all of them part of the core type class seems to be an overkill.

I guess we can close this issue for now. If there is a proposal to create a more feature-rich type class, with complete graph manipulation API (say, as defined in Algebra.Graph), we can create a separate issue.