How powerful is mp?

How powerful is mp?

[Marco Kuhlmann]

    Dear list,

I am currently re-considering my policy regarding graphics, and
would like to have your advice.

Up to now, I am using the Functional MetaPost (FMP) front-end
to MP, which is quite nice if you want to draw trees according
to the generic algorithm proposed by Kennedy (see the paper at
http://citeseer.nj.nec.com/kennedy96drawing.html). Well, to be
honest: it is mostly therefore that I use FMP. :-)

Now my question: Do you think that one can actually write a
program in MP/ConTeXt directly that implements Kennedy's
algorithm? It should take a structural description of a tree as
input (XML seems to be a good choice for the format here) and
produce a drawing of the tree as output. The tree structure
should be placeable inside a ConTeXt document.

Using FMP, the necessary calculations are done in beforehand,
and MP already gets the exact measures (distances between
nodes, levels etc). This additional algorithmical level I have
considered as one of the major advantages of FMP. On the other
hand, it needs to be run separately.

    Cheers,
    Marco

-- 
Marco Kuhlmann                             marco.kuhlmann@gmx.net

Re: How powerful is mp?

[Taco Hoekwater]

Hi Marco,

I just read the article. I must say that I am not overly impressed with the presented algorithm, since it assumes all leaf labels are of uniform width, thereby simplifying the task at hand considerably.

Anyway, of course it can be done in plain mp (or even in tex itself). (nearly) everything that does not require a lot of memory can be done in either language. ;)

The mp toolkit that is called metaobj has rather nice support for various kinds of trees, but it wouldnt be hard to roll your own for this derived case either. The basic algorithm is fairly simple.

"Marco Kuhlmann" <marco.kuhlmann@gmx.net> wrote:
>     Dear list,
> 
> I am currently re-considering my policy regarding graphics, and
> would like to have your advice.
> 

-- 
groeten,

Taco

Re: How powerful is mp?

[Marco Kuhlmann]

    Hi Taco!

Taco Hoekwater wrote (2001-11-07 (16:56)):

> I just read the article. I must say that I am not overly
> impressed with the presented algorithm, since it assumes all
> leaf labels are of uniform width, thereby simplifying the task
> at hand considerably.

Yes, but it seems to be easy to generalise to different widths.
The FMP implementation does this.

> Anyway, of course it can be done in plain mp (or even in tex
> itself). (nearly) everything that does not require a lot of
> memory can be done in either language. ;)

Ah, I had hoped for this! :-) I do not have a lot of experience
in mp, and never saw any actual recursive algorithm implemented.

> The mp toolkit that is called metaobj has rather nice support
> for various kinds of trees, but it wouldnt be hard to roll
> your own for this derived case either. The basic algorithm is
> fairly simple.

Thanks, I definitely shall have a more thorough look on it.
Until now, I always thought that metaobj was just a wrapper for
mp commands with "object" but no "member functions".

    Cheers,
    Marco

-- 
Marco Kuhlmann                             marco.kuhlmann@gmx.net

Re: How powerful is mp?

[Hans Hagen]

At 12:30 PM 11/7/2001 +0000, you wrote:
>     Dear list,
>
>I am currently re-considering my policy regarding graphics, and
>would like to have your advice.
>
>Up to now, I am using the Functional MetaPost (FMP) front-end
>to MP, which is quite nice if you want to draw trees according
>to the generic algorithm proposed by Kennedy (see the paper at
>http://citeseer.nj.nec.com/kennedy96drawing.html). Well, to be
>honest: it is mostly therefore that I use FMP. :-)
>
>Now my question: Do you think that one can actually write a
>program in MP/ConTeXt directly that implements Kennedy's
>algorithm? It should take a structural description of a tree as
>input (XML seems to be a good choice for the format here) and
>produce a drawing of the tree as output. The tree structure
>should be placeable inside a ConTeXt document.
>
>Using FMP, the necessary calculations are done in beforehand,
>and MP already gets the exact measures (distances between
>nodes, levels etc). This additional algorithmical level I have
>considered as one of the major advantages of FMP. On the other
>hand, it needs to be run separately.

you want the simple binary trees graphics from the paper (incredible: after 
all these years people still post tex files with bitmaps)

i'm too stupid to read this kind of algorhitms so i would probably start 
from scratch -)

not too hard to do in xml i think [there is already an xml version of the 
context flowchart module]

Hans

-------------------------------------------------------------------------
                                   Hans Hagen | PRAGMA ADE | pragma@wxs.nl
                       Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
  tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------

Re: How powerful is mp?

[Marco Kuhlmann]

    Hi Hans!

Hans Hagen wrote (2001-11-07 (18:32)):

> you want the simple binary trees graphics from the paper
> (incredible: after all these years people still post tex files
> with bitmaps)

Not binary, n-ary trees. And what do you mean by the second
sentence? What TeX files, what bitmaps?

> i'm too stupid to read this kind of algorhitms so i would
> probably start from scratch -)

I'm too stupid to come up with a better algorithm, so I would
probably try to implement Kennedy's! :-)

> not too hard to do in xml i think [there is already an xml
> version of the context flowchart module]

Do you think that this would be a good starting point for me
then?

    Marco

-- 
Marco Kuhlmann                             marco.kuhlmann@gmx.net

Re: How powerful is mp?

[Taco Hoekwater]

"Marco Kuhlmann" <marco.kuhlmann@gmx.net> wrote:
>     Hi Hans!
>     
> Hans Hagen wrote (2001-11-07 (18:32)):
> 
> > you want the simple binary trees graphics from the paper
> > (incredible: after all these years people still post tex files
> > with bitmaps)
> 
> Not binary, n-ary trees. And what do you mean by the second
> sentence? What TeX files, what bitmaps?

The PDF of the paper is a TeX document processed with bitmap fonts.
Incredibly ugly thing.

> > i'm too stupid to read this kind of algorhitms so i would
> > probably start from scratch -)
> 
> I'm too stupid to come up with a better algorithm, so I would
> probably try to implement Kennedy's! :-)

Kennedy's implementation uses quadratic time. With all respect for the 
author himself, I think his article is not very exciting. 

He does indicate that the implementation can be changed to use linear
time, but doesn't actually show the code that would result from that. 
That would have been a lot more interesting that a couple of recursive functional programming procedures that are all virtually trivial.

Oh well.

> > not too hard to do in xml i think [there is already an xml
> > version of the context flowchart module]
> 
> Do you think that this would be a good starting point for me
> then?

I don't think so. The cleanest way to build trees is bottom up, which is quite different from the flowchart approach. 

-- 
groeten,

Taco

Re: How powerful is mp?

[Hans Hagen]

At 05:49 PM 11/7/2001 +0000, Marco Kuhlmann wrote:
>     Hi Hans!
>
>Hans Hagen wrote (2001-11-07 (18:32)):
>
> > you want the simple binary trees graphics from the paper
> > (incredible: after all these years people still post tex files
> > with bitmaps)
>
>Not binary, n-ary trees. And what do you mean by the second
>sentence? What TeX files, what bitmaps?

the article on the site you pointed too uses bitmap fonts

>Do you think that this would be a good starting point for me
>then?

it's a bit old code but it demos a bit how to do this

the idea is to let mp do the drawings, and pass info to tex so that tex can 
do the text; that way you can have all documents related things in the text 
(like hyperlinks and so)

Hans
-------------------------------------------------------------------------
                                   Hans Hagen | PRAGMA ADE | pragma@wxs.nl
                       Ridderstraat 27 | 8061 GH Hasselt | The Netherlands
  tel: +31 (0)38 477 53 69 | fax: +31 (0)38 477 53 74 | www.pragma-ade.com
-------------------------------------------------------------------------

Re: How powerful is mp?

[Marco Kuhlmann]

Taco Hoekwater wrote (2001-11-08 (09:33)):

> The PDF of the paper is a TeX document processed with bitmap
> fonts. Incredibly ugly thing.

The original of the paper is a ps-file. The pdf has been
created automatically by citeseer; they do this with every
article that they cache.

> Kennedy's implementation uses quadratic time. With all respect
> for the author himself, I think his article is not very
> exciting. 

I see. I'm afraid I was never really concerned about the
complexity, but just found the layout he proposes the best
among the tree-drawing algorithms that I know of. :-) Do you
happen to know an algorithm with better complexity?

> I don't think so. The cleanest way to build trees is bottom
> up, which is quite different from the flowchart approach. 

Okay. Could you point me to some tree-builder which does it
bottom up? I definitely want to have a nice tree-drawing
algorithm in ConTeXt, even if I have to implement it myself. :-)

    Marco

-- 
Marco Kuhlmann                             marco.kuhlmann@gmx.net

Re: How powerful is mp?

[Taco Hoekwater]

"Marco Kuhlmann" <marco.kuhlmann@gmx.net> wrote:
>
> Okay. Could you point me to some tree-builder which does it
> bottom up? I definitely want to have a nice tree-drawing
> algorithm in ConTeXt, even if I have to implement it myself. :-)

The Qobitree package for latex uses a pretty nice bottom-up algorithm. Not overly fast, but easy to read (stack-based). On Ctan, under latex/contrib/other.

-- 
groeten,

Taco

Re: How powerful is mp?

[Marco Kuhlmann]

    Hi Taco.

Thanks for the qobitree recommendation for a stack-based
tree-drawing algorithm. qobitree assumes that the trees have a
rectangular envelope, yuk...

Taco Hoekwater wrote (2001-11-08 (09:33)):

> Kennedy's implementation uses quadratic time. With all respect
> for the author himself, I think his article is not very
> exciting. 

So what sub-quadratic algorithms are there?

> He does indicate that the implementation can be changed to use
> linear time, but doesn't actually show the code that would
> result from that.  That would have been a lot more interesting
> that a couple of recursive functional programming procedures
> that are all virtually trivial.

One could also say: they show how straightforwardly the problem
can be formulated in a functional programming language. :-)
However, you are right that he should have shown the linear
version as well. I actually wonder if there is one; I spent
some time but couldn't figure it out. Gibbons has shown a
linear bound for binary trees, but for n-ary trees...

    Marco

-- 
Marco Kuhlmann                             marco.kuhlmann@gmx.net