how to draw a jerarchical tree in ASCII ??

elgatofelix · 2010-12-13 00:47:18

Hi guys, I've been stuck in a small project of mine about organizational diagrams.
The idea is to produce a tiny domain specific language to describe a hierarchy of
entities in a organization. Like manager, offices, departaments, etc
So far the language part is already implemented parsing the input and creating
the hierarchy of this type

type unidad = {
    name : string;
    mutable parent : unidad option;
    mutable children : unidad list;
   }

the implementation language is Ocaml, the style of the hierarchy is procedural so we can treat
it as a C struct like this (I'm not experienced in C, maybe this struct definition is invalid...)

struct unidad {
   char* name;
   struct unidad* parent;
   struct unidad** children;
}

the second phase is to draw some form of representation. Initially it was supposed this representation
be in ASCII. Here is an example of output (sorry the stupid example):

                   father
                  |
         --------------------------------------
         |              |                     |
        son            girl                  boy       
         |              |                     |
      -------        ---------                |
      |     |        |       |                |
     dog   cat      doll  bob-spongeball    puppet
                     |
                -------------
               |     |      |
             kitty spider  homer

So far I'm short of ideas how to do this. I've tried in paper travelling from bottom nodes,
and mark every node as an offset (against an absolute columnt i don't know... see).
Say i reach to the last level and start with kitty, probe the parent, doll and mark it's
offset as 0, now mark it's children, kitty -1, spider 0 and homer 1, and now I know that
we need to go up... and then my head explodes...

Is there anyone who could enlighten me, designing an algorithm to draw this hierarchy ?

tavianator · 2010-12-13 01:25:47

The key is to calculate the width of each node in a post-order traversal, like this (in pseudocode):

fuction calculateWidths(unidad tree) {
  tree.width = -1;
  foreach (child in tree) {
    calculateWidths(child);
    tree.width += child.width + 1; /* 1 character space between children */
  }
  tree.width = max(tree.width, strlen(tree.name));
}

Now each node knows exactly how much horizontal space is needed to print it and all of its children. The rest is just formatting.

Last edited by tavianator (2010-12-13 01:26:42)

elgatofelix · 2010-12-13 02:56:13

tavianator wrote:

The key is to calculate the width of each node in a post-order traversal, like this (in pseudocode):
fuction calculateWidths(unidad tree) {
  tree.width = -1;
  foreach (child in tree) {
    calculateWidths(child);
    tree.width += child.width + 1; /* 1 character space between children */
  }
  tree.width = max(tree.width, strlen(tree.name));
}
Now each node knows exactly how much horizontal space is needed to print it and all of its children. The rest is just formatting.

yes, with that i know the size of the box, but then how to draw the hierarchy,
Binary trees are easy, this tree can have multiple children.
Maybe tomorrow gonna formulate a better example to show the problem in its magnitude

tavianator · 2010-12-13 03:17:21

Just draw it with a breadth-first traversal, centring each name in a block of node.width characters, with a newline after every level.

elgatofelix · 2010-12-14 13:57:51

This a better example that I can't see how I can resolve by simple breadt-first traverse.

PD: It is not mentioned above but the data structure constains links to members of the same level
computed when the hierarchy is completelty built,
pointing left to right obviating a standard bread-first algorithtm, just get the leftmost-nodes in every level and get
the same functionality

Anyways, even with the simplicity of this structure, I can't figure out how to draw the tree

                                  x
          __________________|_________________
          |      |   |   |        |          |
          x      x   x   x        x          x
     _____|____  |  _|_  |  ______|______  __|__
     |    | | |  |  | |  |  | | | | | | |  | | |
     x    x x x  x  x x  x  x x x x x x x  x x x
_____|___ |     _|_   |
| | | | | |     | |   |
x x x x x x     x x   x

Tillotson · 2010-12-15 00:00:10

Use depth-first to calculate offsets
Easiest way is to add a field to structure "int sumLen"

if node is a leaf node->sumLen = strlen(node->name)
if node is branch node->sumLen = max(total sumLen of children, strlen(node->name))

To print use breath-first, you'll need to know the total left offset of parent before printing children.
Is Ocaml popular in Chile, how did you come to use it?

juster · 2010-12-16 23:42:44

You can do this recursively without iterating over the tree twice. I am learning Ocaml and thought this was a cool problem. Here is my solution: https://gist.github.com/744186

There are probably off-by-one bugs with the string "rendering". If the node's name is wider than the width of its child nodes it will raise an exception. This could be easily fixed.

I tried to isolate the node rendering down to what I thought made sense, a rectangle of text. This is represented as a string list. Each node in the tree can be rendered as a rectangle of text and then the only problem is when we must paste them together, side by side. It is fairly straightforward to expand one with lines of spaces in order to match the number of lines of the other.

We recurse in DFS order to render the tree from the bottom up. The leaf is easy to render as a name and little bar (|). The parent node pastes all its children together side-by-side and appends itself to the top along with a little "swing bar" which goes over the child nodes' bars (|).

elgatofelix · 2010-12-27 20:23:10

Tillotson wrote:

Is Ocaml popular in Chile, how did you come to use it?

nah, I don't think so.

I am not that experienced guy to know the interests of people
into the languages field. I mean, I went to a 'good' university here and
sucked a lot because school was real easy that I had time to drink, being in
another planet... and stuff like that, but when the exigence
demanded to be constant I just couldn't handle it. Besides, topics
like economy or 'engineering' coming next year at that time scared
me more because I was really INTO my thing about computers. So I
dropped university with a really nice depression and got more
obsessed with knowledge (I have found this true, when you are sad
your mind is shouting more and more, beging for ideas to make sense of
your interests). This is how slowly my picture about the technical
side of the field has sharpened -languages more that anything else-...

I got interested in Turing as the man at that time, read one or
two papers of him and some revisions about his ideas, just to note
that it pervades computing (at that time I was a little paranoid) and
people actually keeps trying that path from different angles.
I've always been obsessed with programming-languages since I have a notion
of computation. So reading about Turing naturally took me to the theorical
side with references to some functional-or-like-that, lisp-or-like-that,
ml... you know.

As far of young people here, I don't believe their interests are
that independent to learn and explore Ocaml (even functional
programming is like voodo) because it's obvious when I try to talk to
teachers about the actual 'esoteric' paradigm I'm
fascinated with they don't want to involve.

Popular here would be C, php, social-shit,
networking as both consummers and theorists. That's my narrow vision
when this ideas haunt me at times.

So my idea is that they just do and think whatever their curricula
builds them in their heads. Yeah, it is a miserable
thought, I don't know, I just let my fixation with things like
this (languages) be my education -the real one- but I'm scared, I'm 24 and
I fear that when I finish university in this 2nd-or-3rd intent I'll get
jobs that make me neurotic and more miserable, typical web or repairing
houses jobs, thinking why I can't produce something interesting to sell.

I've found myself mentioning this discourse several times when talking to
people with my communication skills and irritability as an impediment.
Do you think I'm pedantic?, I mean when assisting to a shrink last year
we got to this theme and she attacked me -psichological tactic I think-
to the point it was patetic, me declaring 'I know nothing' but at the
same time it is clear that exploring things by your own gives you a
boost, an identity and a sense of being where you really want.

Arch Linux

#1 2010-12-13 00:47:18

how to draw a jerarchical tree in ASCII ??

#2 2010-12-13 01:25:47

Re: how to draw a jerarchical tree in ASCII ??

#3 2010-12-13 02:56:13

Re: how to draw a jerarchical tree in ASCII ??

#4 2010-12-13 03:17:21

Re: how to draw a jerarchical tree in ASCII ??

#5 2010-12-14 13:57:51

Re: how to draw a jerarchical tree in ASCII ??

#6 2010-12-15 00:00:10

Re: how to draw a jerarchical tree in ASCII ??

#7 2010-12-16 23:42:44

Re: how to draw a jerarchical tree in ASCII ??

#8 2010-12-27 20:23:10

Re: how to draw a jerarchical tree in ASCII ??

Board footer