[aus.wanted] Hierarchical structure -> graphical representation

exnirad@brolga.cc.uq.oz.au (Nirad Sharma) (09/22/90)

I wish to translate a c representation of a hierarchical structure
i.e.	struct info {
		...attributes...
		struct info	*children, *sibling
		}

into PIC statements that will generate visually balanced trees
i.e.			o
		       /  \
		       o   o
		    /  |  \
		   o   o   o

It is not as simple as it looks to get *pleasing* output rather than the
rough-and-ready result of just dumping the branches recursively one by one.
(Note that the example sketched above is a very very simple example and that
 problem of appearance occurs as the trees get more complex. Draw some by hand
 to verify this.)

I am sure that this must have been done by someone already, maybe for computer
science departments printing notes to teach undergrads about hierarchies. If
not, I will have to bash something out (though deadlines are KILLING me!).

Thanks for any help.

Nirad Sharma  (exnirad@brolga.cc.uq.oz.au)
Continuing Education Unit
The University of Queensland
AUSTRALIA

matt@bacchus.esa.oz (Matt Atterbury) (09/24/90)

In article <1990Sep22.032404.20089@brolga.cc.uq.oz.au> exnirad@brolga.cc.uq.oz.au (Nirad Sharma) writes:

   I wish to translate a c representation of a hierarchical structure
   i.e. struct info {
           ...attributes...
           struct info  *children, *sibling
           }

   into PIC statements that will generate visually balanced trees
   i.e.           o
                 / \
                o   o
               /  |  \
              o   o   o


    I have a program that takes a file of format:

        tree ::= node
        node ::= name subtree
        subtree ::= <nothing> | '(' { node } ')'

    (well, one a bit more specific than that, but you get the idea).
    It doesn't handle digraphs, just trees (what is the `|` in your
    pic?). It doesn't produce PIC output, just ASCII chars.

    eg.
        A                                   A
        (                                  / \
            B                             /   \
            C                            B     C
            (               ->                / \
                D                            /   \
                E                           D     E
            )
        )

    It is for drawing JSD entity-action diagrams, but it should be
    reasonably easy to modify. It has a number of stages:
        parse input file to build internal representation
        layout text for each node using a heuristic
        position each node within the whole tree - (x,y) of T/L corners
        draw tree (using + - | ' ' for line drawing and positioning).
    I would expect that it wouldn't be too hard to hack for your
    purpose. The hard part is positioning each node. I believe my
    algorithm is correct (it has worked fine so far). Interested? I
    have posted in case anyone else is also interested, since this is
    a classical example of something that shouldn't have to be
    re-invented by everyone!
--
-------------------------------------------------------------------------------
Matt Atterbury [matt@bacchus.esa.oz]      Expert Solutions Australia, Melbourne
UUCP: ...!uunet!munnari!matt@bacchus.esa.oz               "klaatu barada nikto"
ARPA: matt%bacchus.esa.oz.AU@uunet.UU.NET  "life? don't talk to me about life!"