1HTML::Tree::AboutTrees(U3s)er Contributed Perl DocumentatHiToMnL::Tree::AboutTrees(3)
2
3
4

NAME

6       HTML::Tree::AboutTrees -- article on tree-shaped data structures in
7       Perl
8

SYNOPSIS

10         # This an article, not a module.
11

DESCRIPTION

13       The following article by Sean M. Burke first appeared in The Perl
14       Journal #18 and is copyright 2000 The Perl Journal. It appears courtesy
15       of Jon Orwant and The Perl Journal.  This document may be distributed
16       under the same terms as Perl itself.
17

Trees

19       -- Sean M. Burke
20
21           "AaaAAAaauugh!  Watch out for that tree!"
22             -- George of the Jungle theme
23
24       Perl's facility with references, combined with its automatic management
25       of memory allocation, makes it straightforward to write programs that
26       store data in structures of arbitrary form and complexity.
27
28       But I've noticed that many programmers, especially those who started
29       out with more restrictive languages, seem at home with complex but
30       uniform data structures -- N-dimensional arrays, or more struct-like
31       things like hashes-of-arrays(-of-hashes(-of-hashes), etc.) -- but
32       they're often uneasy with building more freeform, less tabular
33       structures, like tree-shaped data structures.
34
35       But trees are easy to build and manage in Perl, as I'll demonstrate by
36       showing off how the HTML::Element class manages elements in an HTML
37       document tree, and by walking you through a from-scratch implementation
38       of game trees.  But first we need to nail down what we mean by a
39       "tree".
40
41   Socratic Dialogues: "What is a Tree?"
42       My first brush with tree-shaped structures was in linguistics classes,
43       where tree diagrams are used to describe the syntax underlying natural
44       language sentences.  After learning my way around those trees, I
45       started to wonder -- are what I'm used to calling "trees" the same as
46       what programmers call "trees"?  So I asked lots of helpful and patient
47       programmers how they would define a tree.  Many replied with a answer
48       in jargon that they could not really explain (understandable, since
49       explaining things, especially defining things, is harder than people
50       think):
51
52           -- So what is a "tree", a tree-shaped data structure?
53
54           -- A tree is a special case of an acyclic directed graph!
55
56           -- What's a "graph"?
57
58           -- Um... lines... and... you draw it... with... arcs! nodes!  um...
59
60       The most helpful were folks who couldn't explain directly, but with
61       whom I could get into a rather Socratic dialog (where I asked the half-
62       dim half-earnest questions), often with much doodling of
63       illustrations...
64
65       Question: so what's a tree?
66
67       Answer: A tree is a collection of nodes that are linked together in a,
68       well, tree-like way!  Like this [drawing on a napkin]:
69
70            A
71           / \
72          B   C
73            / | \
74           D  E  F
75
76       Q: So what do these letters represent?
77
78       A: Each is a different node, a bunch of data.  Maybe C is a bunch of
79       data that stores a number, maybe a hash table, maybe nothing at all
80       besides the fact that it links to D, E, and F (which are other nodes).
81
82       Q: So what're the lines between the nodes?
83
84       A: Links.  Also called "arcs".  They just symbolize the fact that each
85       node holds a list of nodes it links to.
86
87       Q: So what if I draw nodes and links, like this...
88
89            B -- E
90           / \  / \
91          A   C
92           \ /
93            E
94
95       Is that still a tree?
96
97       A: No, not at all.  There's a lot of un-treelike things about that.
98       First off, E has a link coming off of it going into nowhere.  You can't
99       have a link to nothing -- you can only link to another node.  Second
100       off, I don't know what that sideways link between B and E means...
101
102       Q: Okay, let's work our way up from something simpler.  Is this a
103       tree...?
104
105           A
106
107       A: Yes, I suppose.  It's a tree of just one node.
108
109       Q: And how about...
110
111          A
112
113          B
114
115       A: No, you can't just have nodes floating there, unattached.
116
117       Q: Okay, I'll link A and B.  How's this?
118
119          A
120          |
121          B
122
123       A: Yup, that's a tree.  There's a node A, and a node B, and they're
124       linked.
125
126       Q: How is that tree any different from this one...?
127
128          B
129          |
130          A
131
132       A: Well, in both cases A and B are linked.  But it's in a different
133       direction.
134
135       Q: Direction?  What does the direction mean?
136
137       A: Well, it depends what the tree represents.  If it represents a
138       categorization, like this:
139
140                 citrus
141              /    |    \
142          orange  lemon  kumquat ...
143
144       then you mean to say that oranges, lemons, kumquats, etc., are a kind
145       of citrus.  But if you drew it upside down, you'd be saying, falsely,
146       that citrus is a kind of kumquat, a kind of lemon, and a kind of
147       orange.  If the tree represented cause-and-effect (or at least what
148       situations could follow others), or represented what's a part of what,
149       you wouldn't want to get those backwards, either.  So with the nodes
150       you draw together on paper, one has to be over the other, so you can
151       tell which way the relationship in the tree works.
152
153       Q:  So are these two trees the same?
154
155            A          A
156           / \        / \
157          B   C      B   \
158                          C
159
160       A: Yes, although by convention we often try to line up things in the
161       same generation, like it is in the diagram on the left.
162
163       Q: "generation"?  This is a family tree?
164
165       A: No, not unless it's a family tree for just yeast cells or something
166       else that reproduces asexually.  But for sake of having lots of terms
167       to use, we just pretend that links in the tree represent the "is a
168       child of" relationship, instead of "is a kind of" or "is a part of", or
169       "could result from", or whatever the real relationship is.  So we get
170       to borrow a lot of kinship words for describing trees -- B and C are
171       "children" (or "daughters") of A; A is the "parent" (or "mother") of B
172       and C.  Node C is a "sibling" (or "sister") of node C; and so on, with
173       terms like "descendants" (a node's children, children's children,
174       etc.), and "generation" (all the nodes at the same "level" in the tree,
175       i.e., are either all grandchildren of the top node, or all great-grand-
176       children, etc.), and "lineage" or "ancestors" (parents, and parent's
177       parents, etc., all the way to the topmost node).
178
179       So then we get to express rules in terms like "A node cannot have more
180       than one parent", which means that this is not a valid tree:
181
182           A
183          / \
184         B   C
185          \ /
186           E
187
188       And: "A node can't be its own parent", which excludes this looped-up
189       connection:
190
191           /\
192          A  |
193           \/
194
195       Or, put more generally: "A node can't be its own ancestor", which
196       excludes the above loop, as well as the one here:
197
198             /\
199            Z  |
200           /   |
201          A    |
202         / \   |
203        B   C  |
204             \/
205
206       That tree is excluded because A is a child of Z, and Z is a child of C,
207       and C is a child of A, which means A is its own great-grandparent.  So
208       this whole network can't be a tree, because it breaks the sort of meta-
209       rule: once any node in the supposed tree breaks the rules for trees,
210       you don't have a tree anymore.
211
212       Q: Okay, now, are these two trees the same?
213
214            A         A
215          / | \     / | \
216         B  C  D   D  C  B
217
218       A: It depends whether you're basing your concept of trees on each node
219       having a set (unordered list) of children, or an (ordered) list of
220       children.  It's a question of whether ordering is important for what
221       you're doing.  With my diagram of citrus types, ordering isn't
222       important, so these tree diagrams express the same thing:
223
224                 citrus
225              /    |    \
226          orange  lemon  kumquat
227
228                  citrus
229              /     |    \
230          kumquat  orange  lemon
231
232       because it doesn't make sense to say that oranges are "before" or
233       "after" kumquats in the whole botanical scheme of things.  (Unless, of
234       course, you are using ordering to mean something, like a degree of
235       genetic similarity.)
236
237       But consider a tree that's a diagram of what steps are comprised in an
238       activity, to some degree of specificity:
239
240                  make tea
241                /    |     \
242          pour     infuse   serve
243        hot water    / \
244       in cup/pot  /     \
245                  add     let
246                  tea     sit
247                 leaves
248
249       This means that making tea consists of putting hot water in a cup or
250       put, infusing it (which itself consists of adding tea leaves and
251       letting it sit), then serving it -- in that order.  If you serve an
252       empty dry pot (sipping from empty cups, etc.), let it sit, add tea
253       leaves, and pour in hot water, then what you're doing is performance
254       art, not tea preparation:
255
256               performance
257                   art
258               /    |     \
259          serve   infuse    pour
260                   / \       hot water
261                 /     \      in cup/pot
262                let     add
263                sit     tea
264                       leaves
265
266       Except for my having renamed the root, this tree is the same as the
267       making-tea tree as far as what's under what, but it differs in order,
268       and what the tree means makes the order important.
269
270       Q: Wait -- "root"?  What's a root?
271
272       A: Besides kinship terms like "mother" and "daughter", the jargon for
273       tree parts also has terms from real-life tree parts:  the part that
274       everything else grows from is called the root; and nodes that don't
275       have nodes attached to them (i.e., childless nodes) are called
276       "leaves".
277
278       Q: But you've been drawing all your trees with the root at the top and
279       leaves at the bottom.
280
281       A: Yes, but for some reason, that's the way everyone seems to think of
282       trees.  They can draw trees as above; or they can draw them sort of
283       sideways with indenting representing what nodes are children of what:
284
285         * make tea
286            * pour hot water in cup/pot
287            * infuse
288               * add tea leaves
289               * let sit
290            * serve
291
292       ...but folks almost never seem to draw trees with the root at the
293       bottom.  So imagine it's based on spider plant in a hanging pot.
294       Unfortunately, spider plants aren't botanically trees, they're plants;
295       but "spider plant diagram" is rather a mouthful, so let's just call
296       them trees.
297
298   Trees Defined Formally
299       In time, I digested all these assorted facts about programmers' ideas
300       of trees (which turned out to be just a more general case of linguistic
301       ideas of trees) into a single rule:
302
303       * A node is an item that contains ("is over", "is parent of", etc.)
304       zero or more other nodes.
305
306       From this you can build up formal definitions for useful terms, like
307       so:
308
309       * A node's descendants are defined as all its children, and all their
310       children, and so on.  Or, stated recursively: a node's descendants are
311       all its children, and all its children's descendants.  (And if it has
312       no children, it has no descendants.)
313
314       * A node's ancestors consist of its parent, and its parent's parent,
315       etc, up to the root.  Or, recursively: a node's ancestors consist of
316       its parent and its parent's ancestors.  (If it has no parent, it has no
317       ancestors.)
318
319       * A tree is a root node and all the root's descendants.
320
321       And you can add a proviso or two to clarify exactly what I impute to
322       the word "other" in "other nodes":
323
324       * A node cannot contain itself, or contain any node that contains it,
325       etc.  Looking at it the other way: a node cannot be its own parent or
326       ancestor.
327
328       * A node can be root (i.e., no other node contains it) or can be
329       contained by only one parent; no node can be the child of two or more
330       parents.
331
332       Add to this the idea that children are sometimes ordered, and sometimes
333       not, and that's about all you need to know about defining what a tree
334       is.  From there it's a matter of using them.
335
336   Markup Language Trees: HTML-Tree
337       While not all markup languages are inherently tree-like, the best-known
338       family of markup languages, HTML, SGML, and XML, are about as tree-like
339       as you can get.  In these languages, a document consists of elements
340       and character data in a tree structure where there is one root element,
341       and elements can contain either other elements, or character data.
342
343           Footnote: For sake of simplicity, I'm glossing over comments (<!--
344           ... -->), processing instructions (<?xml version='1.0'>), and
345           declarations (<!ELEMENT ...>, <!DOCTYPE ...>).  And I'm not
346           bothering to distinguish entity references (&lt;, &#64;) or CDATA
347           sections (<![CDATA[ ...]]>) from normal text.
348
349       For example, consider this HTML document:
350
351         <html lang="en-US">
352           <head>
353             <title>
354               Blank Document!
355             </title>
356           </head>
357           <body bgcolor="#d010ff">
358             I've got
359             <em>
360               something to saaaaay
361             </em>
362             !
363           </body>
364         </html>
365
366       I've indented this to point out what nodes (elements or text items) are
367       children of what, with each node on a line of its own.
368
369       The HTML::TreeBuilder module (in the CPAN distribution HTML-Tree) does
370       the work of taking HTML source and building in memory the tree that the
371       document source represents.
372
373           Footnote: it requires the HTML::Parser module, which tokenizes the
374           source -- i.e., identifies each tag, bit of text, comment, etc.
375
376       The trees structures that it builds represent bits of text with normal
377       Perl scalar string values; but elements are represented with objects --
378       that is, chunks of data that belong to a class (in this case,
379       HTML::Element), a class that provides methods (routines) for accessing
380       the pieces of data in each element, and otherwise doing things with
381       elements.  (See my article in TPJ#17 for a quick explanation of
382       objects, the POD document "perltoot" for a longer explanation, or
383       Damian Conway's excellent book Object-Oriented Perl for the full
384       story.)
385
386       Each HTML::Element object contains a number of pieces of data:
387
388       * its element name ("html", "h1", etc., accessed as $element->tag)
389
390       * a list of elements (or text segments) that it contains, if any
391       (accessed as $element->content_list or $element->content, depending on
392       whether you want a list, or an arrayref)
393
394       * what element, if any, contains it (accessed as $element->parent)
395
396       * and any SGML attributes that the element has, such as "lang="en-US"",
397       "align="center"", etc. (accessed as $element->attr('lang'),
398       $element->attr('center'), etc.)
399
400       So, for example, when HTML::TreeBuilder builds the tree for the above
401       HTML document source, the object for the "body" element has these
402       pieces of data:
403
404        * element name: "body"
405        * nodes it contains:
406           the string "I've got "
407           the object for the "em" element
408           the string "!"
409        * its parent:
410           the object for the "html" element
411        * bgcolor: "#d010ff"
412
413       Now, once you have this tree of objects, almost anything you'd want to
414       do with it starts with searching the tree for some bit of information
415       in some element.
416
417       Accessing a piece of information in, say, a hash of hashes of hashes,
418       is straightforward:
419
420         $password{'sean'}{'sburke1'}{'hpux'}
421
422       because you know that all data points in that structure are accessible
423       with that syntax, but with just different keys.  Now, the "em" element
424       in the above HTML tree does happen to be accessible as the root's child
425       #1's child #1:
426
427         $root->content->[1]->content->[1]
428
429       But with trees, you typically don't know the exact location (via
430       indexes) of the data you're looking for.  Instead, finding what you
431       want will typically involve searching through the tree, seeing if every
432       node is the kind you want.  Searching the whole tree is simple enough
433       -- look at a given node, and if it's not what you want, look at its
434       children, and so on.  HTML-Tree provides several methods that do this
435       for you, such as "find_by_tag_name", which returns the elements (or the
436       first element, if called in scalar context) under a given node
437       (typically the root) whose tag name is whatever you specify.
438
439       For example, that "em" node can be found as:
440
441         my $that_em = $root->find_by_tag_name('em');
442
443       or as:
444
445         @ems = $root->find_by_tag_name('em');
446          # will only have one element for this particular tree
447
448       Now, given an HTML document of whatever structure and complexity, if
449       you wanted to do something like change every
450
451           <em>stuff</em>
452
453       to
454
455           <em class="funky"> <b>[-</b> stuff <b>-]</b> </em>
456
457       the first step is to frame this operation in terms of what you're doing
458       to the tree.  You're changing this:
459
460             em
461              |
462             ...
463
464       to this:
465
466             em
467           /  |  \
468          b  ...   b
469          |        |
470         "[-"     "-]"
471
472       In other words, you're finding all elements whose tag name is "em",
473       setting its class attribute to "funky", and adding one child to the
474       start of its content list -- a new "b" element whose content is the
475       text string "[-" -- and one to the end of its content list -- a new "b"
476       element whose content is the text string "-]".
477
478       Once you've got it in these terms, it's just a matter of running to the
479       HTML::Element documentation, and coding this up with calls to the
480       appropriate methods, like so:
481
482         use HTML::Element 1.53;
483         use HTML::TreeBuilder 2.96;
484         # Build the tree by parsing the document
485         my $root = HTML::TreeBuilder->new;
486         $root->parse_file('whatever.html'); # source file
487
488         # Now make new nodes where needed
489         foreach my $em ($root->find_by_tag_name('em')) {
490           $em->attr('class', 'funky'); # Set that attribute
491
492           # Make the two new B nodes
493           my $new1 = HTML::Element->new('b');
494           my $new2 = HTML::Element->new('b');
495           # Give them content (they have none at first)
496           $new1->push_content('[-');
497           $new2->push_content('-]');
498
499           # And put 'em in place!
500           $em->unshift_content($new1);
501           $em->push_content($new2);
502         }
503         print
504          "<!-- Looky see what I did! -->\n",
505          $root->as_HTML(), "\n";
506
507       The class HTML::Element provides just about every method I can image
508       you needing, for manipulating trees made of HTML::Element objects.
509       (And what it doesn't directly provide, it will give you the components
510       to build it with.)
511
512   Building Your Own Trees
513       Theoretically, any tree is pretty much like any other tree, so you
514       could use HTML::Element for anything you'd ever want to do with tree-
515       arranged objects.  However, as its name implies, HTML::Element is
516       basically for HTML elements; it has lots of features that make sense
517       only for HTML elements (like the idea that every element must have a
518       tag-name).  And it lacks some features that might be useful for general
519       applications -- such as any sort of checking to make sure that you're
520       not trying to arrange objects in a non-treelike way.  For a general-
521       purpose tree class that does have such features, you can use
522       Tree::DAG_Node, also available from CPAN.
523
524       However, if your task is simple enough, you might find it overkill to
525       bother using Tree::DAG_Node.  And, in any case, I find that the best
526       way to learn how something works is to implement it (or something like
527       it, but simpler) yourself.  So I'll here discuss how you'd implement a
528       tree structure, without using any of the existing classes for tree
529       nodes.
530
531   Implementation: Game Trees for Alak
532       Suppose that the task at hand is to write a program that can play
533       against a human opponent at a strategic board game (as opposed to a
534       board game where there's an element of chance).  For most such games, a
535       "game tree" is an essential part of the program (as I will argue,
536       below), and this will be our test case for implementing a tree
537       structure from scratch.
538
539       For sake of simplicity, our game is not chess or backgammon, but
540       instead a much simpler game called Alak.  Alak was invented by the
541       mathematician A. K.  Dewdney, and described in his 1984 book
542       Planiverse. The rules of Alak are simple:
543
544           Footnote: Actually, I'm describing only my interpretation of the
545           rules Dewdney describes in Planiverse.  Many other interpretations
546           are possible.
547
548       * Alak is a two-player game played on a one-dimensional board with
549       eleven slots on it.  Each slot can hold at most one piece at a time.
550       There's two kinds of pieces, which I represent here as "x" and "o" --
551       x's belong to one player (called X), o's to the other (called O).
552
553       * The initial configuration of the board is:
554
555          xxxx___oooo
556
557       For sake of the article, the slots are numbered from 1 (on the left) to
558       11 (on the right), and X always has the first move.
559
560       * The players take turns moving.  At each turn, each player can move
561       only one piece, once.  (This unlike checkers, where you move one piece
562       per move but get to keep moving it if you jump an your opponent's
563       piece.) A player cannot pass up on his turn.  A player can move any one
564       of his pieces to the next unoccupied slot to its right or left, which
565       may involve jumping over occupied slots.  A player cannot move a piece
566       off the side of the board.
567
568       * If a move creates a pattern where the opponent's pieces are
569       surrounded, on both sides, by two pieces of the mover's color (with no
570       intervening unoccupied blank slot), then those surrounded pieces are
571       removed from the board.
572
573       * The goal of the game is to remove all of your opponent's pieces, at
574       which point the game ends.  Removing all-but-one ends the game as well,
575       since the opponent can't surround you with one piece, and so will
576       always lose within a few moves anyway.
577
578       Consider, then, this rather short game where X starts:
579
580         xxxx___oooo
581           ^         Move 1: X moves from 3 (shown with caret) to 5
582                      (Note that any of X's pieces could move, but
583                      that the only place they could move to is 5.)
584         xx_xx__oooo
585                 ^   Move 2: O moves from 9 to 7.
586         xx_xx_oo_oo
587            ^        Move 3: X moves from 4 to 6.
588         xx__xxoo_oo
589                  ^  Move 4: O (stupidly) moves from 10 to 9.
590         xx__xxooo_o
591             ^       Move 5: X moves from 5 to 10, making the board
592                     "xx___xoooxo".  The three o's that X just
593                     surrounded are removed.
594         xx___x___xo
595                     O has only one piece, so has lost.
596
597       Now, move 4 could have gone quite the other way:
598
599         xx__xxoo_oo
600                     Move 4: O moves from 8 to 4, making the board
601                     "xx_oxxo__oo".  The surrounded x's are removed.
602         xx_o__o__oo
603         ^           Move 5: X moves from 1 to 2.
604         _xxo__o__oo
605               ^     Move 6: O moves from 7 to 6.
606         _xxo_o___oo
607          ^          Move 7: X moves from 2 to 5, removing the o at 4.
608         __x_xo___oo
609                     ...and so on.
610
611       To teach a computer program to play Alak (as player X, say), it needs
612       to be able to look at the configuration of the board, figure out what
613       moves it can make, and weigh the benefit or costs, immediate or
614       eventual, of those moves.
615
616       So consider the board from just before move 3, and figure all the
617       possible moves X could make.  X has pieces in slots 1, 2, 4, and 5.
618       The leftmost two x's (at 1 and 2) are up against the end of the board,
619       so they can move only right.  The other two x's (at 4 and 5) can move
620       either right or left:
621
622         Starting board: xx_xx_oo_oo
623          moving 1 to 3 gives _xxxx_oo_oo
624          moving 2 to 3 gives x_xxx_oo_oo
625          moving 4 to 3 gives xxx_x_oo_oo
626          moving 5 to 3 gives xxxx__oo_oo
627          moving 4 to 6 gives xx__xxoo_oo
628          moving 5 to 6 gives xx_x_xoo_oo
629
630       For the computer to decide which of these is the best move to make, it
631       needs to quantify the benefit of these moves as a number -- call that
632       the "payoff".  The payoff of a move can be figured as just the number
633       of x pieces removed by the most recent move, minus the number of o
634       pieces removed by the most recent move.  (It so happens that the rules
635       of the game mean that no move can delete both o's and x's, but the
636       formula still applies.)  Since none of these moves removed any pieces,
637       all these moves have the same immediate payoff: 0.
638
639       Now, we could race ahead and write an Alak-playing program that could
640       use the immediate payoff to decide which is the best move to make.  And
641       when there's more than one best move (as here, where all the moves are
642       equally good), it could choose randomly between the good alternatives.
643       This strategy is simple to implement; but it makes for a very dumb
644       program.  Consider what O's response to each of the potential moves
645       (above) could be.  Nothing immediately suggests itself for the first
646       four possibilities (X having moved something to position 3), but either
647       of the last two (illustrated below) are pretty perilous, because in
648       either case O has the obvious option (which he would be foolish to pass
649       up) of removing x's from the board:
650
651          xx_xx_oo_oo
652             ^        X moves 4 to 6.
653          xx__xxoo_oo
654                 ^    O moves 8 to 4, giving "xx_oxxo__oo".  The two
655                      surrounded x's are removed.
656          xx_o__o__oo
657
658       or
659
660          xx_xx_oo_oo
661              ^       X moves 5 to 6.
662          xx_x_xoo_oo
663                 ^    O moves 8 to 5, giving "xx_xoxo__oo".  The one
664                      surrounded x is removed.
665          xx_xo_o__oo
666
667       Both contingencies are quite bad for X -- but this is not captured by
668       the fact that they start out with X thinking his move will be harmless,
669       having a payoff of zero.
670
671       So what's needed is for X to think more than one step ahead -- to
672       consider not merely what it can do in this move, and what the payoff
673       is, but to consider what O might do in response, and the payoff of
674       those potential moves, and so on with X's possible responses to those
675       cases could be.  All these possibilities form a game tree -- a tree
676       where each node is a board, and its children are successors of that
677       node -- i.e., the boards that could result from every move possible,
678       given the parent's board.
679
680       But how to represent the tree, and how to represent the nodes?
681
682       Well, consider that a node holds several pieces of data:
683
684       1) the configuration of the board, which, being nice and simple and
685       one-dimensional, can be stored as just a string, like "xx_xx_oo_oo".
686
687       2) whose turn it is, X or O.  (Or: who moved last, from which we can
688       figure whose turn it is).
689
690       3) the successors (child nodes).
691
692       4) the immediate payoff of having moved to this board position from its
693       predecessor (parent node).
694
695       5) and what move gets us from our predecessor node to here.  (Granted,
696       knowing the board configuration before and after the move, it's easy to
697       figure out the move; but it's easier still to store it as one is
698       figuring out a node's successors.)
699
700       6) whatever else we might want to add later.
701
702       These could be stored equally well in an array or in a hash, but it's
703       my experience that hashes are best for cases where you have more than
704       just two or three bits of data, or especially when you might need to
705       add new bits of data.  Moreover, hash key names are mnemonic --
706       $node->{'last_move_payoff'} is plain as day, whereas it's not so easy
707       having to remember with an array that $node->[3] is where you decided
708       to keep the payoff.
709
710           Footnote: Of course, there are ways around that problem: just swear
711           you'll never use a real numeric index to access data in the array,
712           and instead use constants with mnemonic names:
713
714             use strict;
715             use constant idx_PAYOFF => 3;
716             ...
717             $n->[idx_PAYOFF]
718
719           Or use a pseudohash.  But I prefer to keep it simple, and use a
720           hash.
721
722           These are, incidentally, the same arguments that people weigh when
723           trying to decide whether their object-oriented modules should be
724           based on blessed hashes, blessed arrays, or what.  Essentially the
725           only difference here is that we're not blessing our nodes or
726           talking in terms of classes and methods.
727
728           [end footnote]
729
730       So, we might as well represent nodes like so:
731
732         $node = { # hashref
733            'board'          => ...board string, e.g., "xx_x_xoo_oo"
734
735            'last_move_payoff' => ...payoff of the move
736                                   that got us here.
737
738            'last_move_from' =>  ...the start...
739            'last_move_to'   =>  ...and end point of the move
740                                     that got us here.  E.g., 5 and 6,
741                                     representing a move from 5 to 6.
742
743            'whose_turn'     => ...whose move it then becomes.
744                                  just an 'x' or 'o'.
745
746            'successors' => ...the successors
747         };
748
749       Note that we could have a field called something like 'last_move_who'
750       to denote who last moved, but since turns in Alak always alternate (and
751       no-one can pass), storing whose move it is now and who last moved is
752       redundant -- if X last moved, it's O turn now, and vice versa.  I chose
753       to have a 'whose_turn' field instead of a 'last_move_who', but it
754       doesn't really matter.  Either way, we'll end up inferring one from the
755       other at several points in the program.
756
757       When we want to store the successors of a node, should we use an array
758       or a hash?  On the one hand, the successors to $node aren't essentially
759       ordered, so there's no reason to use an array per se; on the other
760       hand, if we used a hash, with successor nodes as values, we don't have
761       anything particularly meaningful to use as keys.  (And we can't use the
762       successors themselves as keys, since the nodes are referred to by hash
763       references, and you can't use a reference as a hash key.)  Given no
764       particularly compelling reason to do otherwise, I choose to just use an
765       array to store all a node's successors, although the order is never
766       actually used for anything:
767
768         $node = {
769           ...
770           'successors' => [ ...nodes... ],
771           ...
772         };
773
774       In any case, now that we've settled on what should be in a node, let's
775       make a little sample tree out of a few nodes and see what we can do
776       with it:
777
778         # Board just before move 3 in above game
779         my $n0 = {
780           'board' => 'xx_xx_oo_oo',
781           'last_move_payoff' => 0,
782           'last_move_from' =>  9,
783           'last_move_to'   =>  7,
784           'whose_turn' => 'x',
785           'successors' => [],
786         };
787
788         # And, for now, just two of the successors:
789
790         # X moves 4 to 6, giving xx__xxoo_oo
791         my $n1 = {
792           'board' => 'xx__xxoo_oo',
793           'last_move_payoff' => 0,
794           'last_move_from' =>  4,
795           'last_move_to'   =>  6,
796           'whose_turn' => 'o',
797           'successors' => [],
798         };
799
800         # or X moves 5 to 6, giving xx_x_xoo_oo
801         my $n2 = {
802           'board' => 'xx_x_xoo_oo',
803           'last_move_payoff' => 0,
804           'last_move_from' =>  5,
805           'last_move_to'   =>  6,
806           'whose_turn' => 'o',
807           'successors' => [],
808         };
809
810         # Now connect them...
811         push @{$n0->{'successors'}}, $n1, $n2;
812
813   Digression: Links to Parents
814       In comparing what we store in an Alak game tree node to what
815       HTML::Element stores in HTML element nodes, you'll note one big
816       difference: every HTML::Element node contains a link to its parent,
817       whereas we don't have our Alak nodes keeping a link to theirs.
818
819       The reason this can be an important difference is because it can affect
820       how Perl knows when you're not using pieces of memory anymore.
821       Consider the tree we just built, above:
822
823             node 0
824            /      \
825         node 1    node 2
826
827       There's two ways Perl knows you're using a piece of memory: 1) it's
828       memory that belongs directly to a variable (i.e., is necessary to hold
829       that variable's value, or values in the case of a hash or array), or 2)
830       it's a piece of memory that something holds a reference to.  In the
831       above code, Perl knows that the hash for node 0 (for board
832       "xx_xx_oo_oo") is in use because something (namely, the variable $n0)
833       holds a reference to it.  Now, even if you followed the above code with
834       this:
835
836         $n1 = $n2 = 'whatever';
837
838       to make your variables $n1 and $n2 stop holding references to the
839       hashes for the two successors of node 0, Perl would still know that
840       those hashes are still in use, because node 0's successors array holds
841       a reference to those hashes.  And Perl knows that node 0 is still in
842       use because something still holds a reference to it.  Now, if you
843       added:
844
845         my $root = $n0;
846
847       This would change nothing -- there's just be two things holding a
848       reference to the node 0 hash, which in turn holds a reference to the
849       node 1 and node 2 hashes.  And if you then added:
850
851         $n0 = 'stuff';
852
853       still nothing would change, because something ($root) still holds a
854       reference to the node 0 hash.  But once nothing holds a reference to
855       the node 0 hash, Perl will know it can destroy that hash (and reclaim
856       the memory for later use, say), and once it does that, nothing will
857       hold a reference to the node 1 or the node 2 hashes, and those will be
858       destroyed too.
859
860       But consider if the node 1 and node 2 hashes each had an attribute
861       "parent" (or "predecessor") that held a reference to node 0.  If your
862       program stopped holding a reference to the node 0 hash, Perl could not
863       then say that nothing holds a reference to node 0 -- because node 1 and
864       node 2 still do.  So, the memory for nodes 0, 1, and 2 would never get
865       reclaimed (until your program ended, at which point Perl destroys
866       everything).  If your program grew and discarded lots of nodes in the
867       game tree, but didn't let Perl know it could reclaim their memory, your
868       program could grow to use immense amounts of memory -- never a nice
869       thing to have happen.  There's three ways around this:
870
871       1) When you're finished with a node, delete the reference each of its
872       children have to it (in this case, deleting $n1->{'parent'}, say).
873       When you're finished with a whole tree, just go through the whole tree
874       erasing links that children have to their children.
875
876       2) Reconsider whether you really need to have each node hold a
877       reference to its parent.  Just not having those links will avoid the
878       whole problem.
879
880       3) use the WeakRef module with Perl 5.6 or later.  This allows you to
881       "weaken" some references (like the references that node 1 and 2 could
882       hold to their parent) so that they don't count when Perl goes asking
883       whether anything holds a reference to a given piece of memory.  This
884       wonderful new module eliminates the headaches that can often crop up
885       with either of the two previous methods.
886
887       It so happens that our Alak program is simple enough that we don't need
888       for our nodes to have links to their parents, so the second solution is
889       fine.  But in a more advanced program, the first or third solutions
890       might be unavoidable.
891
892   Recursively Printing the Tree
893       I don't like working blind -- if I have any kind of a complex data
894       structure in memory for a program I'm working on, the first thing I do
895       is write something that can dump that structure to the screen so I can
896       make sure that what I think is in memory really is what's in memory.
897       Now, I could just use the "x" pretty-printer command in Perl's
898       interactive debugger, or I could have the program use the
899       "Data::Dumper" module.  But in this case, I think the output from those
900       is rather too verbose.  Once we have trees with dozens of nodes in
901       them, we'll really want a dump of the tree to be as concise as
902       possible, hopefully just one line per node.  What I'd like is something
903       that can print $n0 and its successors (see above) as something like:
904
905         xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)
906           xx__xxoo_oo  (X moved 4 to 6, 0 payoff)
907           xx_x_xoo_oo  (X moved 5 to 6, 0 payoff)
908
909       A subroutine to print a line for a given node, and then do that again
910       for each successor, would look something like:
911
912         sub dump_tree {
913           my $n = $_[0]; # "n" is for node
914           print
915             ...something expressing $n'n content...
916           foreach my $s (@{$n->{'successors'}}) {
917             # "s for successor
918             dump($s);
919           }
920         }
921
922       And we could just start that out with a call to "dump_tree($n0)".
923
924       Since this routine...
925
926           Footnote: I first wrote this routine starting out with "sub dump
927           {".  But when I tried actually calling "dump($n0)", Perl would dump
928           core!  Imagine my shock when I discovered that this is absolutely
929           to be expected -- Perl provides a built-in function called "dump",
930           the purpose of which is to, yes, make Perl dump core.  Calling our
931           routine "dump_tree" instead of "dump" neatly avoids that problem.
932
933       ...does its work (dumping the subtree at and under the given node) by
934       calling itself, it's recursive.  However, there's a special term for
935       this kind of recursion across a tree: traversal.  To traverse a tree
936       means to do something to a node, and to traverse its children.  There's
937       two prototypical ways to do this, depending on what happens when:
938
939         traversing X in pre-order:
940           * do something to X
941           * then traverse X's children
942
943         traversing X in post-order:
944           * traverse X's children
945           * then do something to X
946
947       Dumping the tree to the screen the way we want it happens to be a
948       matter of pre-order traversal, since the thing we do (print a
949       description of the node) happens before we recurse into the successors.
950
951       When we try writing the "print" statement for our above "dump_tree", we
952       can get something like:
953
954         sub dump_tree {
955           my $n = $_[0];
956
957           # "xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)"
958           print
959             $n->{'board'}, "  (",
960             ($n->{'whose_turn'} eq 'o' ? 'X' : 'O'),
961             # Infer who last moved from whose turn it is now.
962             " moved ", $n->{'last_move_from'},
963             " to ",    $n->{'last_move_to'},
964             ", ",      $n->{'last_move_payoff'},
965             " payoff)\n",
966           ;
967
968           foreach my $s (@{$n->{'successors'}}) {
969             dump_tree($s);
970           }
971         }
972
973       If we run this on $n0 from above, we get this:
974
975         xx_xx_oo_oo  (O moved 9 to 7, 0 payoff)
976         xx__xxoo_oo  (X moved 4 to 6, 0 payoff)
977         xx_x_xoo_oo  (X moved 5 to 6, 0 payoff)
978
979       Each line on its own is fine, but we forget to allow for indenting, and
980       without that we can't tell what's a child of what.  (Imagine if the
981       first successor had successors of its own -- you wouldn't be able to
982       tell if it were a child, or a sibling.)  To get indenting, we'll need
983       to have the instances of the "dump_tree" routine know how far down in
984       the tree they're being called, by passing a depth parameter between
985       them:
986
987         sub dump_tree {
988           my $n = $_[0];
989           my $depth = $_[1];
990           $depth = 0 unless defined $depth;
991           print
992             "  " x $depth,
993             ...stuff...
994           foreach my $s (@{$n->{'successors'}}) {
995             dump_tree($s, $depth + 1);
996           }
997         }
998
999       When we call "dump_tree($n0)", $depth (from $_[1]) is undefined, so
1000       gets set to 0, which translates into an indenting of no spaces.  But
1001       when "dump_tree" invokes itself on $n0's children, those instances see
1002       $depth + 1 as their $_[1], giving appropriate indenting.
1003
1004           Footnote: Passing values around between different invocations of a
1005           recursive routine, as shown, is a decent way to share the data.
1006           Another way to share the data is by keeping it in a global
1007           variable, like $Depth, initially set to 0.  Each time "dump_tree"
1008           is about to recurse, it must "++$Depth", and when it's back, it
1009           must "--$Depth".
1010
1011           Or, if the reader is familiar with closures, consider this
1012           approach:
1013
1014             sub dump_tree {
1015               # A wrapper around calls to a recursive closure:
1016               my $start_node = $_[0];
1017               my $depth = 0;
1018                # to be shared across calls to $recursor.
1019               my $recursor;
1020               $recursor = sub {
1021                 my $n = $_[0];
1022                 print "  " x $depth,
1023                   ...stuff...
1024                 ++$depth;
1025                 foreach my $s (@{$n->{'successors'}}) {
1026                   $recursor->($s);
1027                 }
1028                 --$depth;
1029               }
1030               $recursor->($start_node); # start recursing
1031               undef $recursor;
1032             }
1033
1034           The reader with an advanced understanding of Perl's reference-
1035           count-based garbage collection is invited to consider why it is
1036           currently necessary to undef $recursor (or otherwise change its
1037           value) after all recursion is done.
1038
1039           The reader whose mind is perverse in other ways is invited to
1040           consider how (or when!) passing a depth parameter around is
1041           unnecessary because of information that Perl's caller(N) function
1042           reports!
1043
1044           [end footnote]
1045
1046   Growing the Tree
1047       Our "dump_tree" routine works fine for the sample tree we've got, so
1048       now we should get the program working on making its own trees, starting
1049       from a given board.
1050
1051       In "Games::Alak" (the CPAN-released version of Alak that uses
1052       essentially the same code that we're currently discussing the tree-
1053       related parts of), there is a routine called "figure_successors" that,
1054       given one childless node, will figure out all its possible successors.
1055       That is, it looks at the current board, looks at every piece belonging
1056       to the player whose turn it is, and considers the effect of moving each
1057       piece every possible way -- notably, it figures out the immediate
1058       payoff, and if that move would end the game, it notes that by setting
1059       an "endgame" entry in that node's hash.  (That way, we know that that's
1060       a node that can't have successors.)
1061
1062       In the code for "Games::Alak", "figure_successors" does all these
1063       things, in a rather straightforward way.  I won't walk you through the
1064       details of the "figure_successors" code I've written, since the code
1065       has nothing much to do with trees, and is all just implementation of
1066       the Alak rules for what can move where, with what result.  Especially
1067       interested readers can puzzle over that part of code in the source
1068       listing in the archive from CPAN, but others can just assume that it
1069       works as described above.
1070
1071       But consider that "figure_successors", regardless of its inner
1072       workings, does not grow the tree; it only makes one set of successors
1073       for one node at a time.  It has to be up to a different routine to call
1074       "figure_successors", and to keep applying it as needed, in order to
1075       make a nice big tree that our game-playing program can base its
1076       decisions on.
1077
1078       Now, we could do this by just starting from one node, applying
1079       "figure_successors" to it, then applying "figure_successors" on all the
1080       resulting children, and so on:
1081
1082         sub grow {  # Just a first attempt at this!
1083           my $n = $_[0];
1084           figure_successors($n);
1085            unless
1086             @{$n->{'successors'}}
1087               # already has successors.
1088             or $n->{'endgame'}
1089               # can't have successors.
1090           }
1091           foreach my $s (@{$n->{'successors'}}) {
1092             grow($s); # recurse
1093           }
1094         }
1095
1096       If you have a game tree for tic-tac-toe, and you grow it without
1097       limitation (as above), you will soon enough have a fully "solved" tree,
1098       where every node that can have successors does, and all the leaves of
1099       the tree are all the possible endgames (where, in each case, the board
1100       is filled).  But a game of Alak is different from tic-tac-toe, because
1101       it can, in theory, go on forever.  For example, the following sequence
1102       of moves is quite possible:
1103
1104         xxxx___oooo
1105         xxx_x__oooo
1106         xxx_x_o_ooo
1107         xxxx__o_ooo (x moved back)
1108         xxxx___oooo (o moved back)
1109         ...repeat forever...
1110
1111       So if you tried using our above attempt at a "grow" routine, Perl would
1112       happily start trying to construct an infinitely deep tree, containing
1113       an infinite number of nodes, consuming an infinite amount of memory,
1114       and requiring an infinite amount of time.  As the old saying goes: "You
1115       can't have everything -- where would you put it?"  So we have to place
1116       limits on how much we'll grow the tree.
1117
1118       There's more than one way to do this:
1119
1120       1. We could grow the tree until we hit some limit on the number of
1121       nodes we'll allow in the tree.
1122
1123       2. We could grow the tree until we hit some limit on the amount of time
1124       we're willing to spend.
1125
1126       3. Or we could grow the tree until it is fully fleshed out to a certain
1127       depth.
1128
1129       Since we already know to track depth (as we did in writing
1130       "dump_tree"), we'll do it that way, the third way.  The implementation
1131       for that third approach is also pretty straightforward:
1132
1133         $Max_depth = 3;
1134         sub grow {
1135           my $n = $_[0];
1136           my $depth = $_[1] || 0;
1137           figure_successors($n)
1138            unless
1139             $depth >= $Max_depth
1140             or @{$n->{'successors'}}
1141             or $n->{'endgame'}
1142           }
1143           foreach my $s (@{$n->{'successors'}}) {
1144             grow($s, $depth + 1);
1145           }
1146           # If we're at $Max_depth, then figure_successors
1147           #  didn't get called, so there's no successors
1148           #  to recurse under -- that's what stops recursion.
1149         }
1150
1151       If we start from a single node (whether it's a node for the starting
1152       board "xxxx___oooo", or for whatever board the computer is faced with),
1153       set $Max_depth to 4, and apply "grow" to it, it will grow the tree to
1154       include several hundred nodes.
1155
1156           Footnote: If at each move there are four pieces that can move, and
1157           they can each move right or left, the "branching factor" of the
1158           tree is eight, giving a tree with 1 (depth 0) + 8 (depth 1) + 8 **
1159           2 + 8 ** 3 + 8 ** 4  = 4681 nodes in it.  But, in practice, not all
1160           pieces can move in both directions (none of the x pieces in
1161           "xxxx___oooo" can move left, for example), and there may be fewer
1162           than four pieces, if some were lost.  For example, there are 801
1163           nodes in a tree of depth four starting from "xxxx___oooo",
1164           suggesting an average branching factor of about five (801 ** (1/4)
1165           is about 5.3), not eight.
1166
1167       What we need to derive from that tree is the information about what are
1168       the best moves for X.  The simplest way to consider the payoff of
1169       different successors is to just average them -- but what we average
1170       isn't always their immediate payoffs (because that'd leave us using
1171       only one generation of information), but the average payoff of their
1172       successors, if any.  We can formalize this as:
1173
1174         To figure a node's average payoff:
1175           If the node has successors:
1176             Figure each successor's average payoff.
1177             My average payoff is the average of theirs.
1178           Otherwise:
1179             My average payoff is my immediate payoff.
1180
1181       Since this involves recursing into the successors before doing anything
1182       with the current node, this will traverse the tree in post-order.
1183
1184       We could work that up as a routine of its own, and apply that to the
1185       tree after we've applied "grow" to it.  But since we'd never grow the
1186       tree without also figuring the average benefit, we might as well make
1187       that figuring part of the "grow" routine itself:
1188
1189         $Max_depth = 3;
1190         sub grow {
1191           my $n = $_[0];
1192           my $depth = $_[1] || 0;
1193           figure_successors($n);
1194            unless
1195             $depth >= $Max_depth
1196             or @{$n->{'successors'}}
1197             or $n->{'endgame'}
1198           }
1199
1200           if(@{$n->{'successors'}}) {
1201             my $a_payoff_sum = 0;
1202             foreach my $s (@{$n->{'successors'}}) {
1203               grow($s, $depth + 1);  # RECURSE
1204               $a_payoff_sum += $s->{'average_payoff'};
1205             }
1206             $n->{'average_payoff'}
1207              = $a_payoff_sum / @{$n->{'successors'}};
1208           } else {
1209             $n->{'average_payoff'}
1210              = $n->{'last_move_payoff'};
1211           }
1212         }
1213
1214       So, by time "grow" has applied to a node (wherever in the tree it is),
1215       it will have figured successors if possible (which, in turn, sets
1216       "last_move_payoff" for each node it creates), and will have set
1217       "average_benefit".
1218
1219       Beyond this, all that's needed is to start the board out with a root
1220       note of "xxxx___oooo", and have the computer (X) take turns with the
1221       user (O) until someone wins.  Whenever it's O's turn, "Games::Alak"
1222       presents a prompt to the user, letting him know the state of the
1223       current board, and asking what move he selects.  When it's X's turn,
1224       the computer grows the game tree as necessary (using just the "grow"
1225       routine from above), then selects the move with the highest average
1226       payoff (or one of the highest, in case of a tie).
1227
1228       In either case, "selecting" a move means just setting that move's node
1229       as the new root of the program's game tree.  Its sibling nodes and
1230       their descendants (the boards that didn't get selected) and its parent
1231       node will be erased from memory, since they will no longer be in use
1232       (as Perl can tell by the fact that nothing holds references to them
1233       anymore).
1234
1235       The interface code in "Games::Alak" (the code that prompts the user for
1236       his move) actually supports quite a few options besides just moving --
1237       including dumping the game tree to a specified depth (using a slightly
1238       fancier version of "dump_tree", above), resetting the game, changing
1239       $Max_depth in the middle of the game, and quitting the game.  Like
1240       "figure_successors", it's a bit too long to print here, but interested
1241       users are welcome to peruse (and freely modify) the code, as well as to
1242       enjoy just playing the game.
1243
1244       Now, in practice, there's more to game trees than this: for games with
1245       a larger branching factor than Alak has (which is most!), game trees of
1246       depth four or larger would contain too many nodes to be manageable,
1247       most of those nodes being strategically quite uninteresting for either
1248       player; dealing with game trees specifically is therefore a matter of
1249       recognizing uninteresting contingencies and not bothering to grow the
1250       tree under them.
1251
1252           Footnote: For example, to choose a straightforward case: if O has a
1253           choice between moves that put him in immediate danger of X winning
1254           and moves that don't, then O won't ever choose the dangerous moves
1255           (and if he does, the computer will know enough to end the game), so
1256           there's no point in growing the tree any further beneath those
1257           nodes.
1258
1259       But this sample implementation should illustrate the basics of how to
1260       build and manipulate a simple tree structure in memory.  And once
1261       you've understood the basics of tree storage here, you should be ready
1262       to better understand the complexities and peculiarities of other
1263       systems for creating, accessing, and changing trees, including
1264       Tree::DAG_Node, HTML::Element, XML::DOM, or related formalisms like
1265       XPath and XSL.
1266
1267       [end body of article]
1268
1269   [Author Credit]
1270       Sean M. Burke ("sburke@cpan.org") is a tree-dwelling hominid.
1271
1272   References
1273       Dewdney, A[lexander] K[eewatin].  1984.  Planiverse: Computer Contact
1274       with a Two-Dimensional World.  Poseidon Press, New York.
1275
1276       Knuth, Donald Ervin.  1997.  Art of Computer Programming, Volume 1,
1277       Third Edition: Fundamental Algorithms.  Addison-Wesley,  Reading, MA.
1278
1279       Wirth, Niklaus.  1976.  Algorithms + Data Structures = Programs
1280       Prentice-Hall, Englewood Cliffs, NJ.
1281
1282       Worth, Stan and Allman Sheldon.  Circa 1967.  George of the Jungle
1283       theme.  [music by Jay Ward.]
1284
1285       Wirth's classic, currently and lamentably out of print, has a good
1286       section on trees.  I find it clearer than Knuth's (if not quite as
1287       encyclopedic), probably because Wirth's example code is in a block-
1288       structured high-level language (basically Pascal), instead of in
1289       assembler (MIX).  I believe the book was re-issued in the 1980s under
1290       the titles Algorithms and Data Structures and, in a German edition,
1291       Algorithmen und Datenstrukturen.  Cheap copies of these editions should
1292       be available through used book services such as "abebooks.com".
1293
1294       Worth's classic, however, is available on the soundtrack to the 1997
1295       George of the Jungle movie, as performed by The Presidents of the
1296       United States of America.
1297

BACK

1299       Return to the HTML::Tree docs.
1300
1301
1302
1303perl v5.16.3                      2014-06-10         HTML::Tree::AboutTrees(3)
Impressum