[Haskell-cafe] ANNOUNCE: planar-graph-1.0

[Ivan Lazar Miljenovic]

On 28 April 2012 11:38, Felipe Almeida Lessa <felipe.lessa at gmail.com> wrote:
> 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 at gmail.com
http://IvanMiljenovic.wordpress.com