headers
Ivan Lazar Miljenovic | 28 Apr 2012 01:07
Picon
Gravatar

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 <at> gmail.com
http://IvanMiljenovic.wordpress.com
Permalink | Reply |
headers
Thomas DuBuisson | 28 Apr 2012 01:13
Picon
Gravatar

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

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
<ivan.miljenovic <at> gmail.com> wrote:
> 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 <at> gmail.com
> http://IvanMiljenovic.wordpress.com
(Continue reading)

Permalink | Reply |
headers
Christian Höner zu Siederdissen | 28 Apr 2012 03:34
Picon
Picon
Favicon

Re: ANNOUNCE: planar-graph-1.0

Hi,

one minor correction:
> This probably won't be of many use to people
for bioinformatics I'd disagree ;-) I'll take a look at your library.

(for example, RNA /secondary/ structure forms a planar graph)

Gruss,
Christian

* Ivan Lazar Miljenovic <ivan.miljenovic <at> gmail.com> [28.04.2012 01:08]:
> 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).
> 
> --
(Continue reading)

Permalink | Reply |
headers
Ivan Lazar Miljenovic | 28 Apr 2012 03:55
Picon
Gravatar

Re: ANNOUNCE: planar-graph-1.0

On 28 April 2012 11:34, Christian Höner zu Siederdissen
<choener <at> tbi.univie.ac.at> wrote:
> Hi,
>
> one minor correction:
>> This probably won't be of many use to people
> for bioinformatics I'd disagree ;-) I'll take a look at your library.
>
> (for example, RNA /secondary/ structure forms a planar graph)

I stand corrected!

--

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic <at> gmail.com
http://IvanMiljenovic.wordpress.com

_______________________________________________
Haskell mailing list
Haskell <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Permalink | Reply |
headers
Felipe Almeida Lessa | 28 Apr 2012 03:38
Picon
Gravatar

Re: ANNOUNCE: planar-graph-1.0

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.
Permalink | Reply |
headers
Ivan Lazar Miljenovic | 28 Apr 2012 03:53
Picon
Gravatar

Re: ANNOUNCE: planar-graph-1.0

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
(Continue reading)

Permalink | Reply |

Gmane