ANNOUNCE: planar-graph-1.0
I uploaded this [1] yesterday, posted the blog article [2] about it... but forgot to send a message to the lists! [1]: http://hackage.haskell.org/package/planar-graph [2]: http://ivanmiljenovic.wordpress.com/2012/04/27/announcing-planar-graph/ planar-graph is an implementation of, strangely enough, planar graphs (that is, a graph that contains an embedding on a surface, can be drawn with no edge crossings and has a specific ordering of edges). It handles graphs on planes and spheres, but I'm not sure about other surfaces (and there seems to be little demand for such). This probably won't be of many use to people, but as I described in the blog post, I've been using this as a test bed for graph library design (specifically usage of abstract node/edge identifiers, using half-edges and the serialisation/encoding setup). -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com
Good work, Ivan. Despite your numerous previous pointers, I still
haven't look at this API. I'm glad to see this release, it's great
motivation and I'll probably look through it this weekend.
Thanks for all the graph library work you do,
Thomas
On Fri, Apr 27, 2012 at 4:07 PM, Ivan Lazar Miljenovic
I uploaded this [1] yesterday, posted the blog article [2] about it... but forgot to send a message to the lists!
[1]: http://hackage.haskell.org/package/planar-graph [2]: http://ivanmiljenovic.wordpress.com/2012/04/27/announcing-planar-graph/
planar-graph is an implementation of, strangely enough, planar graphs (that is, a graph that contains an embedding on a surface, can be drawn with no edge crossings and has a specific ordering of edges). It handles graphs on planes and spheres, but I'm not sure about other surfaces (and there seems to be little demand for such).
This probably won't be of many use to people, but as I described in the blog post, I've been using this as a test bed for graph library design (specifically usage of abstract node/edge identifiers, using half-edges and the serialisation/encoding setup).
-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Hello! I'm sorry if this is a dumb question, I was just reading the API docs, but: what happens if one by one I add all edges of a non-planar graph using addEdge? Are there any sanity checks that would tell me "sorry, but your graph isn't planar", or would it just give me wrong answers? Cheers, =) -- Felipe.
On 28 April 2012 11:38, Felipe Almeida Lessa
Hello!
I'm sorry if this is a dumb question, I was just reading the API docs, but: what happens if one by one I add all edges of a non-planar graph using addEdge? Are there any sanity checks that would tell me "sorry, but your graph isn't planar", or would it just give me wrong answers?
Wrong answers. I'm assuming you have *some* intelligence :p The original plans were to have Maybe variants that would perform such sanity checks, but as I was going for performance (as my supervisor is of the opinion that if it isn't C it isn't worth considering for pure performance reasons) the default versions didn't include them, and it slipped my mind until you just reminded me :) I can add them in if anyone wants them: what it entails is to add the edge and then perform planarity testing [3]; this can get expensive if the graph is large (I did once work out an approach that involved just checking the new face[s], but I don't recall what it was or whether it was correct). [3]: http://en.wikipedia.org/wiki/Planarity_testing (My rationale for this library was to implement a graph-generating algorithm; I knew what the ordering was, so I didn't need any "will adding this keep it planar" checks.) -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com
participants (3)
-
Felipe Almeida Lessa -
Ivan Lazar Miljenovic -
Thomas DuBuisson