1Tree::DAG_Node(3) User Contributed Perl Documentation Tree::DAG_Node(3)
2
6 Tree::DAG_Node - An N-ary tree
7
9 Using as a base class
10 package Game::Tree::Node;
11 use parent 'Tree::DAG_Node';
13 # Now add your own methods overriding/extending the methods in C<Tree::DAG_Node>...
15 Using as a class on its own
17 use Tree::DAG_Node;
18 my($root) = Tree::DAG_Node -> new({name => 'root', attributes => {uid => 0} });
20 $root -> add_daughter(Tree::DAG_Node -> new({name => 'one', attributes => {uid => 1} }) );
22 $root -> add_daughter(Tree::DAG_Node -> new({name => 'two', attributes => {} }) );
23 $root -> add_daughter(Tree::DAG_Node -> new({name => 'three'}) ); # Attrs default to {}.
24 Or:
26 my($count) = 0;
28 my($tree) = Tree::DAG_Node -> new({name => 'Root', attributes => {'uid' => $count} });
29 Or:
31 my $root = Tree::DAG_Node -> new();
33 $root -> name("I'm the tops");
35 $root -> attributes({uid => 0});
36 my $new_daughter = $root -> new_daughter;
38 $new_daughter -> name('Another node');
40 $new_daughter -> attributes({uid => 1});
41 ...
42 Lastly, for fancy wrappers - called _add_daughter() - around "new()",
44 see these modules: Marpa::Demo::StringParser and GraphViz2::Marpa. Both
45 of these modules use Moo.
46 See scripts/*.pl for other samples.
48 Using with utf-8 data
50 read_tree($file_name) works with utf-8 data. See t/read.tree.t and
51 t/tree.utf8.attributes.txt. Such a file can be created by redirecting
52 the output of tree2string() to a file of type utf-8.
53 See the docs for Encode for the difference between utf8 and utf-8. In
55 brief, use utf-8.
56 See also scripts/write_tree.pl and scripts/read.tree.pl and
58 scripts/read.tree.log.
59
61 This class encapsulates/makes/manipulates objects that represent nodes
62 in a tree structure. The tree structure is not an object itself, but is
63 emergent from the linkages you create between nodes. This class
64 provides the methods for making linkages that can be used to build up a
65 tree, while preventing you from ever making any kinds of linkages which
66 are not allowed in a tree (such as having a node be its own mother or
67 ancestor, or having a node have two mothers).
68 This is what I mean by a "tree structure", a bit redundantly stated:
70 o A tree is a special case of an acyclic directed graph
72 o A tree is a network of nodes where there's exactly one root node
73 Also, the only primary relationship between nodes is the mother-
74 daughter relationship.
75 o No node can be its own mother, or its mother's mother, etc
77 o Each node in the tree has exactly one parent
78 Except for the root of course, which is parentless.
79 o Each node can have any number (0 .. N) daughter nodes
81 A given node's daughter nodes constitute an ordered list.
82 However, you are free to consider this ordering irrelevant. Some
84 applications do need daughters to be ordered, so I chose to
85 consider this the general case.
86 o A node can appear in only one tree, and only once in that tree
88 Notably (notable because it doesn't follow from the two above
89 points), a node cannot appear twice in its mother's daughter list.
90 o There's an idea of up versus down
92 Up means towards to the root, and down means away from the root
93 (and towards the leaves).
94 o There's an idea of left versus right
96 Left is toward the start (index 0) of a given node's daughter list,
97 and right is toward the end of a given node's daughter list.
98 Trees as described above have various applications, among them:
100 representing syntactic constituency, in formal linguistics;
101 representing contingencies in a game tree; representing abstract syntax
102 in the parsing of any computer language -- whether in expression trees
103 for programming languages, or constituency in the parse of a markup
104 language document. (Some of these might not use the fact that
105 daughters are ordered.)
106 (Note: B-Trees are a very special case of the above kinds of trees, and
108 are best treated with their own class. Check CPAN for modules
109 encapsulating B-Trees; or if you actually want a database, and for some
110 reason ended up looking here, go look at AnyDBM_File.)
111 Many base classes are not usable except as such -- but "Tree::DAG_Node"
113 can be used as a normal class. You can go ahead and say:
114 use Tree::DAG_Node;
116 my $root = Tree::DAG_Node->new();
117 $root->name("I'm the tops");
118 $new_daughter = Tree::DAG_Node->new();
119 $new_daughter->name("More");
120 $root->add_daughter($new_daughter);
121 and so on, constructing and linking objects from "Tree::DAG_Node" and
123 making useful tree structures out of them.
124
126 This class is big and provides lots of methods. If your problem is
127 simple (say, just representing a simple parse tree), this class might
128 seem like using an atomic sledgehammer to swat a fly. But the
129 complexity of this module's bells and whistles shouldn't detract from
130 the efficiency of using this class for a simple purpose. In fact, I'd
131 be very surprised if any one user ever had use for more that even a
132 third of the methods in this class. And remember: an atomic
133 sledgehammer will kill that fly.
134
136 Implementationally, each node in a tree is an object, in the sense of
137 being an arbitrarily complex data structure that belongs to a class
138 (presumably "Tree::DAG_Node", or ones derived from it) that provides
139 methods.
140 The attributes of a node-object are:
142 o mother -- this node's mother. undef if this is a root
144 o daughters -- the (possibly empty) list of daughters of this node
145 o name -- the name for this node
146 Need not be unique, or even printable. This is printed in some of
147 the various dumper methods, but it's up to you if you don't put
148 anything meaningful or printable here.
149 o attributes -- whatever the user wants to use it for
151 Presumably a hashref to whatever other attributes the user wants to
152 store without risk of colliding with the object's real attributes.
153 (Example usage: attributes to an SGML tag -- you definitely
154 wouldn't want the existence of a "mother=foo" pair in such a tag to
155 collide with a node object's 'mother' attribute.)
156 Aside from (by default) initializing it to {}, and having the
158 access method called "attributes" (described a ways below), I don't
159 do anything with the "attributes" in this module. I basically
160 intended this so that users who don't want/need to bother deriving
161 a class from "Tree::DAG_Node", could still attach whatever data
162 they wanted in a node.
163 "mother" and "daughters" are attributes that relate to linkage -- they
165 are never written to directly, but are changed as appropriate by the
166 "linkage methods", discussed below.
167 The other two (and whatever others you may add in derived classes) are
169 simply accessed thru the same-named methods, discussed further below.
170 About The Documented Interface
172 Stick to the documented interface (and comments in the source --
173 especially ones saying "undocumented!" and/or "disfavored!" -- do not
174 count as documentation!), and don't rely on any behavior that's not in
175 the documented interface.
176 Specifically, unless the documentation for a particular method says
178 "this method returns thus-and-such a value", then you should not rely
179 on it returning anything meaningful.
180 A passing acquaintance with at least the broader details of the source
182 code for this class is assumed for anyone using this class as a base
183 class -- especially if you're overriding existing methods, and
184 definitely if you're overriding linkage methods.
185
187 the constructor CLASS->new() or CLASS->new($options)
188 This creates a new node object, calls $object->_init($options) to
189 provide it sane defaults (like: undef name, undef mother, no
190 daughters, 'attributes' setting of a new empty hashref), and
191 returns the object created. (If you just said "CLASS->new()" or
192 "CLASS->new", then it pretends you called "CLASS->new({})".)
193 See also the comments under "new($hashref)" for options supported
195 in the call to new().
196 If you use "Tree::DAG_Node" as a superclass, and you add attributes
198 that need to be initialized, what you need to do is provide an
199 _init method that calls $this->SUPER::_init($options) to use its
200 superclass's _init method, and then initializes the new attributes:
201 sub _init {
203 my($this, $options) = @_[0,1];
204 $this->SUPER::_init($options); # call my superclass's _init to
205 # init all the attributes I'm inheriting
206 # Now init /my/ new attributes:
208 $this->{'amigos'} = []; # for example
209 }
210 the constructor $obj->new() or $obj->new($options)
212 Just another way to get at the "new($hashref)" method. This does
213 not copy $obj, but merely constructs a new object of the same class
214 as it. Saves you the bother of going $class = ref $obj; $obj2 =
215 $class->new;
216 the method $node->_init($options)
218 Initialize the object's attribute values. See the discussion
219 above. Presumably this should be called only by the guts of the
220 "new($hashref)" constructor -- never by the end user.
221 Currently there are no documented options for putting in the
223 $options hashref, but (in case you want to disregard the above
224 rant) the option exists for you to use $options for something
225 useful in a derived class.
226 Please see the source for more information.
228 see also (below) the constructors "new_daughter" and
230 "new_daughter_left"
231
233 add_daughter(LIST)
234 An exact synonym for "add_daughters(LIST)".
235 add_daughters(LIST)
237 This method adds the node objects in LIST to the (right) end of
238 $mother's daughter list. Making a node N1 the daughter of another node
239 N2 also means that N1's mother attribute is "automatically" set to N2;
240 it also means that N1 stops being anything else's daughter as it
241 becomes N2's daughter.
242 If you try to make a node its own mother, a fatal error results. If
244 you try to take one of a node N1's ancestors and make it also a
245 daughter of N1, a fatal error results. A fatal error results if
246 anything in LIST isn't a node object.
247 If you try to make N1 a daughter of N2, but it's already a daughter of
249 N2, then this is a no-operation -- it won't move such nodes to the end
250 of the list or anything; it just skips doing anything with them.
251 add_daughter_left(LIST)
253 An exact synonym for "add_daughters_left(LIST)".
254 add_daughters_left(LIST)
256 This method is just like "add_daughters(LIST)", except that it adds the
257 node objects in LIST to the (left) beginning of $mother's daughter
258 list, instead of the (right) end of it.
259 add_left_sister(LIST)
261 An exact synonym for "add_left_sisters(LIST)".
262 add_left_sisters(LIST)
264 This adds the elements in LIST (in that order) as immediate left
265 sisters of $node. In other words, given that B's mother's daughter-
266 list is (A,B,C,D), calling B->add_left_sisters(X,Y) makes B's mother's
267 daughter-list (A,X,Y,B,C,D).
268 If LIST is empty, this is a no-op, and returns empty-list.
270 This is basically implemented as a call to $node->replace_with(LIST,
272 $node), and so all replace_with's limitations and caveats apply.
273 The return value of $node->add_left_sisters(LIST) is the elements of
275 LIST that got added, as returned by replace_with -- minus the copies of
276 $node you'd get from a straight call to $node->replace_with(LIST,
277 $node).
278 add_right_sister(LIST)
280 An exact synonym for "add_right_sisters(LIST)".
281 add_right_sisters(LIST)
283 Just like add_left_sisters (which see), except that the elements in
284 LIST (in that order) as immediate right sisters of $node;
285 In other words, given that B's mother's daughter-list is (A,B,C,D),
287 calling B->add_right_sisters(X,Y) makes B's mother's daughter-list
288 (A,B,X,Y,C,D).
289 address()
291 address(ADDRESS)
292 With the first syntax, returns the address of $node within its tree,
293 based on its position within the tree. An address is formed by noting
294 the path between the root and $node, and concatenating the daughter-
295 indices of the nodes this passes thru (starting with 0 for the root,
296 and ending with $node).
297 For example, if to get from node ROOT to node $node, you pass thru
299 ROOT, A, B, and $node, then the address is determined as:
300 o ROOT's my_daughter_index is 0
302 o A's my_daughter_index is, suppose, 2
303 A is index 2 in ROOT's daughter list.
304 o B's my_daughter_index is, suppose, 0
306 B is index 0 in A's daughter list.
307 o $node's my_daughter_index is, suppose, 4
309 $node is index 4 in B's daughter list.
310 The address of the above-described $node is, therefore, "0:2:0:4".
312 (As a somewhat special case, the address of the root is always "0"; and
314 since addresses start from the root, all addresses start with a "0".)
315 The second syntax, where you provide an address, starts from the root
317 of the tree $anynode belongs to, and returns the node corresponding to
318 that address. Returns undef if no node corresponds to that address.
319 Note that this routine may be somewhat liberal in its interpretation of
320 what can constitute an address; i.e., it accepts "0.2.0.4", besides
321 "0:2:0:4".
322 Also note that the address of a node in a tree is meaningful only in
324 that tree as currently structured.
325 (Consider how ($address1 cmp $address2) may be magically meaningful to
327 you, if you meant to figure out what nodes are to the right of what
328 other nodes.)
329 ancestors()
331 Returns the list of this node's ancestors, starting with its mother,
332 then grandmother, and ending at the root. It does this by simply
333 following the 'mother' attributes up as far as it can. So if $item IS
334 the root, this returns an empty list.
335 Consider that scalar($node->ancestors) returns the ply of this node
337 within the tree -- 2 for a granddaughter of the root, etc., and 0 for
338 root itself.
339 attribute()
341 attribute(SCALAR)
342 Exact synonyms for "attributes()" and "attributes(SCALAR)".
343 attributes()
345 attributes(SCALAR)
346 In the first form, returns the value of the node object's "attributes"
347 attribute. In the second form, sets it to the value of SCALAR. I
348 intend this to be used to store a reference to a (presumably anonymous)
349 hash the user can use to store whatever attributes he doesn't want to
350 have to store as object attributes. In this case, you needn't ever set
351 the value of this. (_init has already initialized it to {}.) Instead
352 you can just do...
353 $node->attributes->{'foo'} = 'bar';
355 ...to write foo => bar.
357 clear_daughters()
359 This unlinks all $mother's daughters. Returns the list of what used to
360 be $mother's daughters.
361 Not to be confused with "remove_daughters(LIST)".
363 common(LIST)
365 Returns the lowest node in the tree that is ancestor-or-self to the
366 nodes $node and LIST.
367 If the nodes are far enough apart in the tree, the answer is just the
369 root.
370 If the nodes aren't all in the same tree, the answer is undef.
372 As a degenerate case, if LIST is empty, returns $node.
374 common_ancestor(LIST)
376 Returns the lowest node that is ancestor to all the nodes given (in
377 nodes $node and LIST). In other words, it answers the question: "What
378 node in the tree, as low as possible, is ancestor to the nodes given
379 ($node and LIST)?"
380 If the nodes are far enough apart, the answer is just the root --
382 except if any of the nodes are the root itself, in which case the
383 answer is undef (since the root has no ancestor).
384 If the nodes aren't all in the same tree, the answer is undef.
386 As a degenerate case, if LIST is empty, returns $node's mother; that'll
388 be undef if $node is root.
389 copy($option)
391 Returns a copy of the calling node (the invocant). E.g.: my($copy) =
392 $node -> copy;
393 $option is a hashref of options, with these (key => value) pairs:
395 o no_attribute_copy => $Boolean
397 If set to 1, do not copy the node's attributes.
398 If not specified, defaults to 0, which copies attributes.
400 copy_at_and_under()
402 copy_at_and_under($options)
403 This returns a copy of the subtree consisting of $node and everything
404 under it.
405 If you pass no options, copy_at_and_under pretends you've passed {}.
407 This works by recursively building up the new tree from the leaves,
409 duplicating nodes using $orig_node->copy($options_ref) and then linking
410 them up into a new tree of the same shape.
411 Options you specify are passed down to calls to $node->copy.
413 copy_tree()
415 copy_tree($options)
416 This returns the root of a copy of the tree that $node is a member of.
417 If you pass no options, copy_tree pretends you've passed {}.
418 This method is currently implemented as just a call to
420 $this->root->copy_at_and_under($options), but magic may be added in the
421 future.
422 Options you specify are passed down to calls to $node->copy.
424 daughters()
426 This returns the (possibly empty) list of daughters for $node.
427 decode_lol($lol)
429 Returns an arrayref having decoded the deeply nested structure $lol.
430 $lol will be the output of either tree_to_lol() or
432 tree_to_simple_lol().
433 See scripts/read.tree.pl, and it's output file scripts/read.tree.log.
435 delete_tree()
437 Destroys the entire tree that $node is a member of (starting at the
438 root), by nulling out each node-object's attributes (including, most
439 importantly, its linkage attributes -- hopefully this is more than
440 sufficient to eliminate all circularity in the data structure), and
441 then moving it into the class DEADNODE.
442 Use this when you're finished with the tree in question, and want to
444 free up its memory. (If you don't do this, it'll get freed up anyway
445 when your program ends.)
446 If you try calling any methods on any of the node objects in the tree
448 you've destroyed, you'll get an error like:
449 Can't locate object method "leaves_under"
451 via package "DEADNODE".
452 So if you see that, that's what you've done wrong. (Actually, the
454 class DEADNODE does provide one method: a no-op method "delete_tree".
455 So if you want to delete a tree, but think you may have deleted it
456 already, it's safe to call $node->delete_tree on it (again).)
457 The "delete_tree()" method is needed because Perl's garbage collector
459 would never (as currently implemented) see that it was time to de-
460 allocate the memory the tree uses -- until either you call
461 $node->delete_tree, or until the program stops (at "global destruction"
462 time, when everything is unallocated).
463 Incidentally, there are better ways to do garbage-collecting on a tree,
465 ways which don't require the user to explicitly call a method like
466 "delete_tree()" -- they involve dummy classes, as explained at
467 <http://mox.perl.com/misc/circle-destroy.pod>
468 However, introducing a dummy class concept into "Tree::DAG_Node" would
470 be rather a distraction. If you want to do this with your derived
471 classes, via a DESTROY in a dummy class (or in a tree-metainformation
472 class, maybe), then feel free to.
473 The only case where I can imagine "delete_tree()" failing to totally
475 void the tree, is if you use the hashref in the "attributes" attribute
476 to store (presumably among other things) references to other nodes'
477 "attributes" hashrefs -- which 1) is maybe a bit odd, and 2) is your
478 problem, because it's your hash structure that's circular, not the
479 tree's. Anyway, consider:
480 # null out all my "attributes" hashes
482 $anywhere->root->walk_down({
483 'callback' => sub {
484 $hr = $_[0]->attributes; %$hr = (); return 1;
485 }
486 });
487 # And then:
488 $anywhere->delete_tree;
489 (I suppose "delete_tree()" is a "destructor", or as close as you can
491 meaningfully come for a circularity-rich data structure in Perl.)
492 See also "WHEN AND HOW TO DESTROY THE TREE".
494 depth_under()
496 Returns an integer representing the number of branches between this
497 $node and the most distant leaf under it. (In other words, this
498 returns the ply of subtree starting of $node. Consider
499 scalar($it->ancestors) if you want the ply of a node within the whole
500 tree.)
501 descendants()
503 Returns a list consisting of all the descendants of $node. Returns
504 empty-list if $node is a terminal_node.
505 (Note that it's spelled "descendants", not "descendents".)
507 draw_ascii_tree([$options])
509 Here, the [] refer to an optional parameter.
510 Returns an arrayref of lines suitable for printing.
512 Draws a nice ASCII-art representation of the tree structure.
514 The tree looks like:
516 |
518 <Root>
519 /-------+-----+---+---\
520 | | | | |
521 <I> <H> <D> <E> <B>
522 /---\ /---\ | | |
523 | | | | <F> <F> <C>
524 <J> <J> <J> <J> | |
525 | | | | <G> <G>
526 <K> <L> <K> <L>
527 | |
528 <M> <M>
529 | |
530 <N> <N>
531 | |
532 <O> <O>
533 See scripts/cut.and.paste.subtrees.pl.
535 Example usage:
537 print map("$_\n", @{$tree->draw_ascii_tree});
539 draw_ascii_tree() takes parameters you set in the $options hashref:
541 o h_compact
543 Takes 0 or 1. Sets the extent to which draw_ascii_tree() tries to
544 save horizontal space.
545 If I think of a better scrunching algorithm, there'll be a "2"
547 setting for this.
548 Default: 1.
550 o h_spacing
552 Takes a number 0 or greater. Sets the number of spaces inserted
553 horizontally between nodes (and groups of nodes) in a tree.
554 Default: 1.
556 o no_name
558 If true, draw_ascii_tree() doesn't print the name of the node; it
559 simply prints a "*".
560 Default: 0 (i.e., print the node name.)
562 o v_compact
564 Takes a number 0, 1, or 2. Sets the degree to which
565 draw_ascii_tree() tries to save vertical space. Defaults to 1.
566 The code occasionally returns trees that are a bit cock-eyed in parts;
568 if anyone can suggest a better drawing algorithm, I'd be appreciative.
569 See also "tree2string($options, [$some_tree])".
571 dump_names($options)
573 Returns an array.
574 Dumps, as an indented list, the names of the nodes starting at $node,
576 and continuing under it. Options are:
577 o _depth -- A nonnegative number
579 Indicating the depth to consider $node as being at (and so the
580 generation under that is that plus one, etc.). You may choose to
581 use set _depth => scalar($node->ancestors).
582 Default: 0.
584 o tick -- a string to preface each entry with
586 This string goes between the indenting-spacing and the node's name.
587 You may prefer "*" or "-> " or something.
588 Default: ''.
590 o indent -- the string used to indent with
592 Another sane value might be '. ' (period, space). Setting it to
593 empty-string suppresses indenting.
594 Default: ' ' x 2.
596 The output is not printed, but is returned as a list, where each item
598 is a line, with a "\n" at the end.
599 format_node($options, $node)
601 Returns a string consisting of the node's name and, optionally, it's
602 attributes.
603 Possible keys in the $options hashref:
605 o no_attributes => $Boolean
607 If 1, the node's attributes are not included in the string
608 returned.
609 Default: 0 (include attributes).
611 Calls "hashref2string($hashref)".
613 Called by "node2string($options, $node, $vert_dashes)".
615 You would not normally call this method.
617 If you don't wish to supply options, use format_node({}, $node).
619 generation()
621 Returns a list of all nodes (going left-to-right) that are in $node's
622 generation -- i.e., that are the some number of nodes down from the
623 root. $root->generation() is just $root.
624 Of course, $node is always in its own generation.
626 generation_under($node)
628 Like "generation()", but returns only the nodes in $node's generation
629 that are also descendants of $node -- in other words,
630 @us = $node->generation_under( $node->mother->mother );
632 is all $node's first cousins (to borrow yet more kinship terminology)
634 -- assuming $node does indeed have a grandmother. Actually "cousins"
635 isn't quite an apt word, because @us ends up including $node's siblings
636 and $node.
637 Actually, "generation_under($node)" is just an alias to "generation()",
639 but I figure that this:
640 @us = $node->generation_under($way_upline);
642 is a bit more readable than this:
644 @us = $node->generation($way_upline);
646 But it's up to you.
648 $node->generation_under($node) returns just $node.
650 If you call $node->generation_under($node) but NODE2 is not $node or an
652 ancestor of $node, it behaves as if you called just
653 $node->generation().
654 hashref2string($hashref)
656 Returns the given hashref as a string.
657 Called by "format_node($options, $node)".
659 is_daughter_of($node2)
661 Returns true iff $node is a daughter of $node2. Currently implemented
662 as just a test of ($it->mother eq $node2).
663 is_node()
665 This always returns true. More pertinently, $object->can('is_node') is
666 true (regardless of what "is_node()" would do if called) for objects
667 belonging to this class or for any class derived from it.
668 is_root()
670 Returns 1 if the caller is the root, and 0 if it is not.
671 leaves_under()
673 Returns a list (going left-to-right) of all the leaf nodes under $node.
674 ("Leaf nodes" are also called "terminal nodes" -- i.e., nodes that have
675 no daughters.) Returns $node in the degenerate case of $node being a
676 leaf itself.
677 left_sister()
679 Returns the node that's the immediate left sister of $node. If $node
680 is the leftmost (or only) daughter of its mother (or has no mother),
681 then this returns undef.
682 See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
684 left_sisters()
686 Returns a list of nodes that're sisters to the left of $node. If $node
687 is the leftmost (or only) daughter of its mother (or has no mother),
688 then this returns an empty list.
689 See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
691 lol_to_tree($lol)
693 This must be called as a class method.
694 Converts something like bracket-notation for "Chomsky trees" (or
696 rather, the closest you can come with Perl
697 list-of-lists(-of-lists(-of-lists))) into a tree structure. Returns
698 the root of the tree converted.
699 The conversion rules are that: 1) if the last (possibly the only) item
701 in a given list is a scalar, then that is used as the "name" attribute
702 for the node based on this list. 2) All other items in the list
703 represent daughter nodes of the current node -- recursively so, if they
704 are list references; otherwise, (non-terminal) scalars are considered
705 to denote nodes with that name. So ['Foo', 'Bar', 'N'] is an alternate
706 way to represent [['Foo'], ['Bar'], 'N'].
707 An example will illustrate:
709 use Tree::DAG_Node;
711 $lol =
712 [
713 [
714 [ [ 'Det:The' ],
715 [ [ 'dog' ], 'N'], 'NP'],
716 [ '/with rabies\\', 'PP'],
717 'NP'
718 ],
719 [ 'died', 'VP'],
720 'S'
721 ];
722 $tree = Tree::DAG_Node->lol_to_tree($lol);
723 $diagram = $tree->draw_ascii_tree;
724 print map "$_\n", @$diagram;
725 ...returns this tree:
727 |
729 <S>
730 |
731 /------------------\
732 | |
733 <NP> <VP>
734 | |
735 /---------------\ <died>
736 | |
737 <NP> <PP>
738 | |
739 /-------\ </with rabies\>
740 | |
741 <Det:The> <N>
742 |
743 <dog>
744 By the way (and this rather follows from the above rules), when
746 denoting a LoL tree consisting of just one node, this:
747 $tree = Tree::DAG_Node->lol_to_tree( 'Lonely' );
749 is okay, although it'd probably occur to you to denote it only as:
751 $tree = Tree::DAG_Node->lol_to_tree( ['Lonely'] );
753 which is of course fine, too.
755 mother()
757 This returns what node is $node's mother. This is undef if $node has
758 no mother -- i.e., if it is a root.
759 See also "is_root()" and "root()".
761 my_daughter_index()
763 Returns what index this daughter is, in its mother's "daughter" list.
764 In other words, if $node is ($node->mother->daughters)[3], then
765 $node->my_daughter_index returns 3.
766 As a special case, returns 0 if $node has no mother.
768 name()
770 name(SCALAR)
771 In the first form, returns the value of the node object's "name"
772 attribute. In the second form, sets it to the value of SCALAR.
773 new($hashref)
775 These options are supported in $hashref:
776 o attributes => A hashref of attributes
778 o daughters => An arrayref of nodes
779 o mother => A node
780 o name => A string
781 See also "MAIN CONSTRUCTOR, AND INITIALIZER" for a long discussion on
783 object creation.
784 new_daughter()
786 new_daughter($options)
787 This constructs a new node (of the same class as $mother), and adds it
788 to the (right) end of the daughter list of $mother. This is essentially
789 the same as going
790 $daughter = $mother->new;
792 $mother->add_daughter($daughter);
793 but is rather more efficient because (since $daughter is guaranteed new
795 and isn't linked to/from anything), it doesn't have to check that
796 $daughter isn't an ancestor of $mother, isn't already daughter to a
797 mother it needs to be unlinked from, isn't already in $mother's
798 daughter list, etc.
799 As you'd expect for a constructor, it returns the node-object created.
801 Note that if you radically change 'mother'/'daughters' bookkeeping, you
803 may have to change this routine, since it's one of the places that
804 directly writes to 'daughters' and 'mother'.
805 new_daughter_left()
807 new_daughter_left($options)
808 This is just like $mother->new_daughter, but adds the new daughter to
809 the left (start) of $mother's daughter list.
810 Note that if you radically change 'mother'/'daughters' bookkeeping, you
812 may have to change this routine, since it's one of the places that
813 directly writes to 'daughters' and 'mother'.
814 node2string($options, $node, $vert_dashes)
816 Returns a string of the node's name and attributes, with a leading
817 indent, suitable for printing.
818 Possible keys in the $options hashref:
820 o no_attributes => $Boolean
822 If 1, the node's attributes are not included in the string
823 returned.
824 Default: 0 (include attributes).
826 Ignore the parameter $vert_dashes. The code uses it as temporary
828 storage.
829 Calls "format_node($options, $node)".
831 Called by "tree2string($options, [$some_tree])".
833 quote_name($name)
835 Returns the string "'$name'", which is used in various methods for
836 outputting node names.
837 random_network($options)
839 This method can be called as a class method or as an object method.
840 In the first case, constructs a randomly arranged network under a new
842 node, and returns the root node of that tree. In the latter case,
843 constructs the network under $node.
844 Currently, this is implemented a bit half-heartedly, and half-wittedly.
846 I basically needed to make up random-looking networks to stress-test
847 the various tree-dumper methods, and so wrote this. If you actually
848 want to rely on this for any application more serious than that, I
849 suggest examining the source code and seeing if this does really what
850 you need (say, in reliability of randomness); and feel totally free to
851 suggest changes to me (especially in the form of "I rewrote
852 "random_network($options)", here's the code...")
853 It takes four options:
855 o max_node_count -- maximum number of nodes this tree will be allowed
857 to have (counting the root)
858 Default: 25.
859 o min_depth -- minimum depth for the tree
861 Leaves can be generated only after this depth is reached, so the
862 tree will be at least this deep -- unless max_node_count is hit
863 first.
864 Default: 2.
866 o max_depth -- maximum depth for the tree
868 The tree will not be deeper than this.
869 Default: 3 plus min_depth.
871 o max_children -- maximum number of children any mother in the tree can
873 have.
874 Default: 4.
875 read_attributes($s)
877 Parses the string $s and extracts the name and attributes, assuming the
878 format is as generated by "tree2string($options, [$some_tree])".
879 This bascially means the attribute string was generated by
881 "hashref2string($hashref)".
882 Attributes may be absent, in which case they default to {}.
884 Returns a new node with this name and these attributes.
886 This method is for use by "read_tree($file_name)".
888 See t/tree.without.attributes.txt and t/tree.with.attributes.txt for
890 sample data.
891 read_tree($file_name)
893 Returns the root of the tree read from $file_name.
894 The file must have been written by re-directing the output of
896 "tree2string($options, [$some_tree])" to a file, since it makes
897 assumptions about the format of the stringified attributes.
898 read_tree() works with utf-8 data. See t/read.tree.t and
900 t/tree.utf8.attributes.txt.
901 Note: To call this method you need a caller. It'll be a tree of 1 node.
903 The reason is that inside this method it calls various other methods,
904 and for these calls it needs $self. That way, those methods can be
905 called from anywhere, and not just from within read_tree().
906 For reading and writing trees to databases, see
908 Tree::DAG_Node::Persist.
909 Calls "string2hashref($s)".
911 remove_daughter(LIST)
913 An exact synonym for "remove_daughters(LIST)".
914 remove_daughters(LIST)
916 This removes the nodes listed in LIST from $mother's daughter list.
917 This is a no-operation if LIST is empty. If there are things in LIST
918 that aren't a current daughter of $mother, they are ignored.
919 Not to be confused with "clear_daughters()".
921 replace_with(LIST)
923 This replaces $node in its mother's daughter list, by unlinking $node
924 and replacing it with the items in LIST. This returns a list
925 consisting of $node followed by LIST, i.e., the nodes that replaced it.
926 LIST can include $node itself (presumably at most once). LIST can also
928 be the empty list. However, if any items in LIST are sisters to $node,
929 they are ignored, and are not in the copy of LIST passed as the return
930 value.
931 As you might expect for any linking operation, the items in LIST cannot
933 be $node's mother, or any ancestor to it; and items in LIST are, of
934 course, unlinked from their mothers (if they have any) as they're
935 linked to $node's mother.
936 (In the special (and bizarre) case where $node is root, this simply
938 calls $this->unlink_from_mother on all the items in LIST, making them
939 roots of their own trees.)
940 Note that the daughter-list of $node is not necessarily affected; nor
942 are the daughter-lists of the items in LIST. I mention this in case
943 you think replace_with switches one node for another, with respect to
944 its mother list and its daughter list, leaving the rest of the tree
945 unchanged. If that's what you want, replacing $Old with $New, then you
946 want:
947 $New->set_daughters($Old->clear_daughters);
949 $Old->replace_with($New);
950 (I can't say $node's and LIST-items' daughter lists are never affected
952 my replace_with -- they can be affected in this case:
953 $N1 = ($node->daughters)[0]; # first daughter of $node
955 $N2 = ($N1->daughters)[0]; # first daughter of $N1;
956 $N3 = Tree::DAG_Node->random_network; # or whatever
957 $node->replace_with($N1, $N2, $N3);
958 As a side affect of attaching $N1 and $N2 to $node's mother, they're
960 unlinked from their parents ($node, and $N1, respectively). But N3's
961 daughter list is unaffected.
962 In other words, this method does what it has to, as you'd expect it to.
964 replace_with_daughters()
966 This replaces $node in its mother's daughter list, by unlinking $node
967 and replacing it with its daughters. In other words, $node becomes
968 motherless and daughterless as its daughters move up and take its
969 place. This returns a list consisting of $node followed by the nodes
970 that were its daughters.
971 In the special (and bizarre) case where $node is root, this simply
973 unlinks its daughters from it, making them roots of their own trees.
974 Effectively the same as $node->replace_with($node->daughters), but more
976 efficient, since less checking has to be done. (And I also think
977 $node->replace_with_daughters is a more common operation in tree-
978 wrangling than $node->replace_with(LIST), so deserves a named method of
979 its own, but that's just me.)
980 Note that if you radically change 'mother'/'daughters' bookkeeping, you
982 may have to change this routine, since it's one of the places that
983 directly writes to 'daughters' and 'mother'.
984 right_sister()
986 Returns the node that's the immediate right sister of $node. If $node
987 is the rightmost (or only) daughter of its mother (or has no mother),
988 then this returns undef.
989 See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
991 right_sisters()
993 Returns a list of nodes that're sisters to the right of $node. If $node
994 is the rightmost (or only) daughter of its mother (or has no mother),
995 then this returns an empty list.
996 See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
998 root()
1000 Returns the root of whatever tree $node is a member of. If $node is
1001 the root, then the result is $node itself.
1002 Not to be confused with "is_root()".
1004 self_and_descendants()
1006 Returns a list consisting of itself (as element 0) and all the
1007 descendants of $node. Returns just itself if $node is a terminal_node.
1008 (Note that it's spelled "descendants", not "descendents".)
1010 self_and_sisters()
1012 Returns a list of all nodes (going left-to-right) that have the same
1013 mother as $node -- including $node itself. This is just like
1014 $node->mother->daughters, except that that fails where $node is root,
1015 whereas $root->self_and_siblings, as a special case, returns $root.
1016 (Contrary to how you may interpret how this method is named, "self" is
1018 not (necessarily) the first element of what's returned.)
1019 set_daughters(LIST)
1021 This unlinks all $mother's daughters, and replaces them with the
1022 daughters in LIST.
1023 Currently implemented as just $mother->clear_daughters followed by
1025 $mother->add_daughters(LIST).
1026 simple_lol_to_tree($simple_lol)
1028 This must be called as a class method.
1029 This is like lol_to_tree, except that rule 1 doesn't apply -- i.e., all
1031 scalars (or really, anything not a listref) in the LoL-structure end up
1032 as named terminal nodes, and only terminal nodes get names (and, of
1033 course, that name comes from that scalar value). This method is useful
1034 for making things like expression trees, or at least starting them off.
1035 Consider that this:
1036 $tree = Tree::DAG_Node->simple_lol_to_tree(
1038 [ 'foo', ['bar', ['baz'], 'quux'], 'zaz', 'pati' ]
1039 );
1040 converts from something like a Lispish or Iconish tree, if you pretend
1042 the brackets are parentheses.
1043 Note that there is a (possibly surprising) degenerate case of what I'm
1045 calling a "simple-LoL", and it's like this:
1046 $tree = Tree::DAG_Node->simple_lol_to_tree('Lonely');
1048 This is the (only) way you can specify a tree consisting of only a
1050 single node, which here gets the name 'Lonely'.
1051 sisters()
1053 Returns a list of all nodes (going left-to-right) that have the same
1054 mother as $node -- not including $node itself. If $node is root, this
1055 returns empty-list.
1056 string2hashref($s)
1058 Returns the hashref built from the string.
1059 The string is expected to be something like '{AutoCommit => '1',
1061 PrintError => "0", ReportError => 1}'.
1062 The empty string is returned as {}.
1064 Called by "read_tree($file_name)".
1066 tree_to_lol()
1068 Returns that tree (starting at $node) represented as a LoL, like what
1069 $lol, above, holds. (This is as opposed to
1070 "tree_to_lol_notation($options)", which returns the viewable code like
1071 what gets evaluated and stored in $lol, above.)
1072 Undefined node names are returned as the string 'undef'.
1074 See also "decode_lol($lol)".
1076 Lord only knows what you use this for -- maybe for feeding to
1078 Data::Dumper, in case "tree_to_lol_notation($options)" doesn't do just
1079 what you want?
1080 tree_to_lol_notation($options)
1082 Dumps a tree (starting at $node) as the sort of LoL-like bracket
1083 notation you see in the above example code. Returns just one big block
1084 of text. The only option is "multiline" -- if true, it dumps the text
1085 as the sort of indented structure as seen above; if false (and it
1086 defaults to false), dumps it all on one line (with no indenting, of
1087 course).
1088 For example, starting with the tree from the above example, this:
1090 print $tree->tree_to_lol_notation, "\n";
1092 prints the following (which I've broken over two lines for sake of
1094 printability of documentation):
1095 [[[['Det:The'], [['dog'], 'N'], 'NP'], [["/with rabies\x5c"],
1097 'PP'], 'NP'], [['died'], 'VP'], 'S'],
1098 Doing this:
1100 print $tree->tree_to_lol_notation({ multiline => 1 });
1102 prints the same content, just spread over many lines, and prettily
1104 indented.
1105 Undefined node names are returned as the string 'undef'.
1107 tree_to_simple_lol()
1109 Returns that tree (starting at $node) represented as a simple-LoL --
1110 i.e., one where non-terminal nodes are represented as listrefs, and
1111 terminal nodes are gotten from the contents of those nodes' "name'
1112 attributes.
1113 Note that in the case of $node being terminal, what you get back is the
1115 same as $node->name.
1116 Compare to tree_to_simple_lol_notation.
1118 Undefined node names are returned as the string 'undef'.
1120 See also "decode_lol($lol)".
1122 tree_to_simple_lol_notation($options)
1124 A simple-LoL version of tree_to_lol_notation (which see); takes the
1125 same options.
1126 Undefined node names are returned as the string 'undef'.
1128 tree2string($options, [$some_tree])
1130 Here, the [] represent an optional parameter.
1131 Returns an arrayref of lines, suitable for printing.
1133 Draws a nice ASCII-art representation of the tree structure.
1135 The tree looks like:
1137 Root. Attributes: {}
1139 |--- Â. Attributes: {# => "ÂÂ"}
1140 | |--- â. Attributes: {# => "ââ"}
1141 | | |--- É. Attributes: {# => "ÉÉ"}
1142 | |--- ä. Attributes: {# => "ää"}
1143 | |--- é. Attributes: {# => "éé"}
1144 | |--- Ñ. Attributes: {# => "ÑÑ"}
1145 | |--- ñ. Attributes: {# => "ññ"}
1146 | |--- Ô. Attributes: {# => "ÔÔ"}
1147 | |--- ô. Attributes: {# => "ôô"}
1148 | |--- ô. Attributes: {# => "ôô"}
1149 |--- ß. Attributes: {# => "ßß"}
1150 |--- ®. Attributes: {# => "®®"}
1151 | |--- ©. Attributes: {# => "©©"}
1152 |--- £. Attributes: {# => "££"}
1153 |--- €. Attributes: {# => "€€"}
1154 |--- √. Attributes: {# => "√√"}
1155 |--- ×xX. Attributes: {# => "×xX×xX"}
1156 |--- í. Attributes: {# => "íí"}
1157 |--- ú. Attributes: {# => "úú"}
1158 |--- «. Attributes: {# => "««"}
1159 |--- ». Attributes: {# => "»»"}
1160 Or, without attributes:
1162 Root
1164 |--- Â
1165 | |--- â
1166 | | |--- É
1167 | |--- ä
1168 | |--- é
1169 | |--- Ñ
1170 | |--- ñ
1171 | |--- Ô
1172 | |--- ô
1173 | |--- ô
1174 |--- ß
1175 |--- ®
1176 | |--- ©
1177 |--- £
1178 |--- €
1179 |--- √
1180 |--- ×xX
1181 |--- í
1182 |--- ú
1183 |--- «
1184 |--- »
1185 See scripts/cut.and.paste.subtrees.pl.
1187 Example usage:
1189 print map("$_\n", @{$tree->tree2string});
1191 Can be called with $some_tree set to any $node, and will print the tree
1193 assuming $node is the root.
1194 If you don't wish to supply options, use tree2string({}, $node).
1196 Possible keys in the $options hashref (which defaults to {}):
1198 o no_attributes => $Boolean
1200 If 1, the node's attributes are not included in the string
1201 returned.
1202 Default: 0 (include attributes).
1204 Calls "node2string($options, $node, $vert_dashes)".
1206 See also "draw_ascii_tree([$options])".
1208 unlink_from_mother()
1210 This removes node from the daughter list of its mother. If it has no
1211 mother, this is a no-operation.
1212 Returns the mother unlinked from (if any).
1214 walk_down($options)
1216 Performs a depth-first traversal of the structure at and under $node.
1217 What it does at each node depends on the value of the options hashref,
1218 which you must provide. There are three options, "callback" and
1219 "callbackback" (at least one of which must be defined, as a sub
1220 reference), and "_depth".
1221 This is what walk_down() does, in pseudocode form:
1223 o Starting point
1225 Start at the $node given.
1226 o Callback
1228 If there's a callback, call it with $node as the first argument,
1229 and the options hashref as the second argument (which contains the
1230 potentially useful _depth, remember). This function must return
1231 true or false -- if false, it will block the next step:
1232 o Daughters
1234 If $node has any daughter nodes, increment _depth, and call
1235 $daughter->walk_down($options) for each daughter (in order, of
1236 course), where options_hashref is the same hashref it was called
1237 with. When this returns, decrements _depth.
1238 Callbackback
1240 If there's a callbackback, call just it as with callback (but
1241 tossing out the return value). Note that callback returning false
1242 blocks traversal below $node, but doesn't block calling
1243 callbackback for $node. (Incidentally, in the unlikely case that
1244 $node has stopped being a node object, callbackback won't get
1245 called.)
1246 o Return
1248 $node->walk_down($options) is the way to recursively do things to a
1250 tree (if you start at the root) or part of a tree; if what you're doing
1251 is best done via pre-pre order traversal, use callback; if what you're
1252 doing is best done with post-order traversal, use callbackback.
1253 walk_down() is even the basis for plenty of the methods in this class.
1254 See the source code for examples both simple and horrific.
1255 Note that if you don't specify _depth, it effectively defaults to 0.
1257 You should set it to scalar($node->ancestors) if you want _depth to
1258 reflect the true depth-in-the-tree for the nodes called, instead of
1259 just the depth below $node. (If $node is the root, there's no
1260 difference, of course.)
1261 And by the way, it's a bad idea to modify the tree from the callback.
1263 Unpredictable things may happen. I instead suggest having your
1264 callback add to a stack of things that need changing, and then, once
1265 walk_down() is all finished, changing those nodes from that stack.
1266 Note that the existence of walk_down() doesn't mean you can't write you
1268 own special-use traversers.
1269
1271 It should be clear to you that if you've built a big parse tree or
1272 something, and then you're finished with it, you should call
1273 $some_node->delete_tree on it if you want the memory back.
1274 But consider this case: you've got this tree:
1276 A
1278 / | \
1279 B C D
1280 | | \
1281 E X Y
1282 Let's say you decide you don't want D or any of its descendants in the
1284 tree, so you call D->unlink_from_mother. This does NOT automagically
1285 destroy the tree D-X-Y. Instead it merely splits the tree into two:
1286 A D
1288 / \ / \
1289 B C X Y
1290 |
1291 E
1292 To destroy D and its little tree, you have to explicitly call
1294 delete_tree on it.
1295 Note, however, that if you call C->unlink_from_mother, and if you don't
1297 have a link to C anywhere, then it does magically go away. This is
1298 because nothing links to C -- whereas with the D-X-Y tree, D links to X
1299 and Y, and X and Y each link back to D. Note that calling
1300 C->delete_tree is harmless -- after all, a tree of only one node is
1301 still a tree.
1302 So, this is a surefire way of getting rid of all $node's children and
1304 freeing up the memory associated with them and their descendants:
1305 foreach my $it ($node->clear_daughters) { $it->delete_tree }
1307 Just be sure not to do this:
1309 foreach my $it ($node->daughters) { $it->delete_tree }
1311 $node->clear_daughters;
1312 That's bad; the first call to $_->delete_tree will climb to the root of
1314 $node's tree, and nuke the whole tree, not just the bits under $node.
1315 You might as well have just called $node->delete_tree. (Moreavor, once
1316 $node is dead, you can't call clear_daughters on it, so you'll get an
1317 error there.)
1318
1320 If you find a bug in this library, report it to me as soon as possible,
1321 at the address listed in the MAINTAINER section, below. Please try to
1322 be as specific as possible about how you got the bug to occur.
1323
1325 If you develop a given routine for dealing with trees in some way, and
1326 use it a lot, then if you think it'd be of use to anyone else, do email
1327 me about it; it might be helpful to others to include that routine, or
1328 something based on it, in a later version of this module.
1329 It's occurred to me that you might like to (and might yourself develop
1331 routines to) draw trees in something other than ASCII art. If you do
1332 so -- say, for PostScript output, or for output interpretable by some
1333 external plotting program -- I'd be most interested in the results.
1334
1336 This module uses "strict", but I never wrote it with -w warnings in
1337 mind -- so if you use -w, do not be surprised if you see complaints
1338 from the guts of DAG_Node. As long as there is no way to turn off -w
1339 for a given module (instead of having to do it in every single
1340 subroutine with a "local $^W"), I'm not going to change this. However,
1341 I do, at points, get bursts of ambition, and I try to fix code in
1342 DAG_Node that generates warnings, as I come across them -- which is
1343 only occasionally. Feel free to email me any patches for any such
1344 fixes you come up with, tho.
1345 Currently I don't assume (or enforce) anything about the class
1347 membership of nodes being manipulated, other than by testing whether
1348 each one provides a method "is_node()", a la:
1349 die "Not a node!!!" unless UNIVERSAL::can($node, "is_node");
1351 So, as far as I'm concerned, a given tree's nodes are free to belong to
1353 different classes, just so long as they provide/inherit "is_node()",
1354 the few methods that this class relies on to navigate the tree, and
1355 have the same internal object structure, or a superset of it.
1356 Presumably this would be the case for any object belonging to a class
1357 derived from "Tree::DAG_Node", or belonging to "Tree::DAG_Node" itself.
1358 When routines in this class access a node's "mother" attribute, or its
1360 "daughters" attribute, they (generally) do so directly (via
1361 $node->{'mother'}, etc.), for sake of efficiency. But classes derived
1362 from this class should probably do this instead thru a method (via
1363 $node->mother, etc.), for sake of portability, abstraction, and general
1364 goodness.
1365 However, no routines in this class (aside from, necessarily, _init(),
1367 _init_name(), and "name()") access the "name" attribute directly;
1368 routines (like the various tree draw/dump methods) get the "name" value
1369 thru a call to $obj->name(). So if you want the object's name to not
1370 be a real attribute, but instead have it derived dynamically from some
1371 feature of the object (say, based on some of its other attributes, or
1372 based on its address), you can to override the "name()" method, without
1373 causing problems. (Be sure to consider the case of $obj->name as a
1374 write method, as it's used in /lol_to_tree($lol) and
1375 "random_network($options)".)
1376
1378 Which is the best tree processing module?
1379 "Tree::DAG_Node", as it happens. More details: "SEE ALSO".
1380 How to process every node in tree?
1382 See "walk_down($options)". $options normally looks like this, assuming
1383 we wish to pass in an arrayref as a stack:
1384 my(@stack);
1386 $tree -> walk_down
1388 ({
1389 callback =>
1390 sub
1391 {
1392 my(@node, $options) = @_;
1393 # Process $node, using $options...
1395 push @{$$options{stack} }, $node -> name;
1397 return 1; # Keep walking.
1399 },
1400 _depth => 0,
1401 stack => \@stack,
1402 });
1403 # Process @stack...
1405 How do I switch from Tree to Tree::DAG_Node?
1407 o The node's name
1408 In "Tree" you use $node -> value and in "Tree::DAG_Node" it's $node
1409 -> name.
1410 o The node's attributes
1412 In "Tree" you use $node -> meta and in "Tree::DAG_Node" it's $node
1413 -> attributes.
1414 Are there techniques for processing lists of nodes?
1416 o Copy the daughter list, and change it
1417 @them = $mother->daughters;
1418 @removed = splice(@them, 0, 2, @new_nodes);
1419 $mother->set_daughters(@them);
1421 o Select a sub-set of nodes
1423 $mother->set_daughters
1424 (
1425 grep($_->name =~ /wanted/, $mother->daughters)
1426 );
1427 Why did you break up the sections of methods in the POD?
1429 Because I want to list the methods in alphabetical order.
1430 Why did you move the POD to the end?
1432 Because the apostrophes in the text confused the syntax hightlighter in
1433 my editor UltraEdit.
1434
1436 o HTML::Element, HTML::Tree and HTML::TreeBuilder
1437 Sean is also the author of these modules.
1438 o Tree
1440 Lightweight.
1441 o Tree::Binary
1443 Lightweight.
1444 o Tree::DAG_Node::Persist
1446 Lightweight.
1447 o Tree::Persist
1449 Lightweight.
1450 o Forest
1452 Uses Moose.
1453 "Tree::DAG_Node" itself is also lightweight.
1455
1457 Wirth, Niklaus. 1976. Algorithms + Data Structures = Programs
1458 Prentice-Hall, Englewood Cliffs, NJ.
1459 Knuth, Donald Ervin. 1997. Art of Computer Programming, Volume 1,
1461 Third Edition: Fundamental Algorithms. Addison-Wesley, Reading, MA.
1462 Wirth's classic, currently and lamentably out of print, has a good
1464 section on trees. I find it clearer than Knuth's (if not quite as
1465 encyclopedic), probably because Wirth's example code is in a block-
1466 structured high-level language (basically Pascal), instead of in
1467 assembler (MIX).
1468 Until some kind publisher brings out a new printing of Wirth's book,
1470 try poking around used bookstores (or "www.abebooks.com") for a copy.
1471 I think it was also republished in the 1980s under the title Algorithms
1472 and Data Structures, and in a German edition called Algorithmen und
1473 Datenstrukturen. (That is, I'm sure books by Knuth were published
1474 under those titles, but I'm assuming that they're just later
1475 printings/editions of Algorithms + Data Structures = Programs.)
1476
1478 The file Changes was converted into Changelog.ini by
1479 Module::Metadata::Changes.
1480
1482 <https://github.com/ronsavage/Tree-DAG_Node>
1483
1485 Email the author, or log a bug on RT:
1486 <https://rt.cpan.org/Public/Dist/Display.html?Name=Tree-DAG_Node>.
1488
1490 The code to print the tree, in tree2string(), was adapted from
1491 Forest::Tree::Writer::ASCIIWithBranches by the dread Stevan Little.
1492
1494 David Hand, "<cogent@cpan.org>" up to V 1.06.
1495 Ron Savage "<rsavage@cpan.org>" from V 1.07.
1497 In this POD, usage of 'I' refers to Sean, up until V 1.07.
1499
1501 Sean M. Burke, "<sburke@cpan.org>"
1502
1504 Copyright 1998-2001, 2004, 2007 by Sean M. Burke and David Hand.
1505 This Program of ours is 'OSI Certified Open Source Software'; you can
1507 redistribute it and/or modify it under the terms of The Perl License, a
1508 copy of which is available at: http://dev.perl.org/licenses/
1509 This program is distributed in the hope that it will be useful, but
1511 without any warranty; without even the implied warranty of
1512 merchantability or fitness for a particular purpose.
1513perl v5.32.0 2020-07-28 Tree::DAG_Node(3)