1Tree::DAG_Node(3)     User Contributed Perl Documentation    Tree::DAG_Node(3)
2
3
4

NAME

6       Tree::DAG_Node - An N-ary tree
7

SYNOPSIS

9   Using as a base class
10               package Game::Tree::Node;
11
12               use parent 'Tree::DAG_Node';
13
14               # Now add your own methods overriding/extending the methods in C<Tree::DAG_Node>...
15
16   Using as a class on its own
17               use Tree::DAG_Node;
18
19               my($root) = Tree::DAG_Node -> new({name => 'root', attributes => {uid => 0} });
20
21               $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
25       Or:
26
27               my($count) = 0;
28               my($tree)  = Tree::DAG_Node -> new({name => 'Root', attributes => {'uid' => $count} });
29
30       Or:
31
32               my $root = Tree::DAG_Node -> new();
33
34               $root -> name("I'm the tops");
35               $root -> attributes({uid => 0});
36
37               my $new_daughter = $root -> new_daughter;
38
39               $new_daughter -> name('Another node');
40               $new_daughter -> attributes({uid => 1});
41               ...
42
43       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
47       See scripts/*.pl for other samples.
48
49   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
54       See the docs for Encode for the difference between utf8 and utf-8. In
55       brief, use utf-8.
56
57       See also scripts/write_tree.pl and scripts/read.tree.pl and
58       scripts/read.tree.log.
59

DESCRIPTION

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
69       This is what I mean by a "tree structure", a bit redundantly stated:
70
71       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
76       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
80       o Each node can have any number (0 .. N) daughter nodes
81           A given node's daughter nodes constitute an ordered list.
82
83           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
87       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
91       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
95       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
99       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
107       (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
112       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
115               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
122       and so on, constructing and linking objects from "Tree::DAG_Node" and
123       making useful tree structures out of them.
124

A NOTE TO THE READER

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

OBJECT CONTENTS

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
141       The attributes of a node-object are:
142
143       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
150       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
157           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
164       "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
168       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
171   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
177       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
181       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

MAIN CONSTRUCTOR, AND INITIALIZER

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
194           See also the comments under "new($hashref)" for options supported
195           in the call to new().
196
197           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
202             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
207               # Now init /my/ new attributes:
208               $this->{'amigos'} = []; # for example
209             }
210
211       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
217       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
222           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
227           Please see the source for more information.
228
229       see also (below) the constructors "new_daughter" and
230       "new_daughter_left"
231

METHODS

233   add_daughter(LIST)
234       An exact synonym for "add_daughters(LIST)".
235
236   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
243       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
248       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
252   add_daughter_left(LIST)
253       An exact synonym for "add_daughters_left(LIST)".
254
255   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
260   add_left_sister(LIST)
261       An exact synonym for "add_left_sisters(LIST)".
262
263   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
269       If LIST is empty, this is a no-op, and returns empty-list.
270
271       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
274       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
279   add_right_sister(LIST)
280       An exact synonym for "add_right_sisters(LIST)".
281
282   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
286       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
290   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
298       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
301       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
305       o B's my_daughter_index is, suppose, 0
306           B is index 0 in A's daughter list.
307
308       o $node's my_daughter_index is, suppose, 4
309           $node is index 4 in B's daughter list.
310
311       The address of the above-described $node is, therefore, "0:2:0:4".
312
313       (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
316       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
323       Also note that the address of a node in a tree is meaningful only in
324       that tree as currently structured.
325
326       (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
330   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
336       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
340   attribute()
341   attribute(SCALAR)
342       Exact synonyms for "attributes()" and "attributes(SCALAR)".
343
344   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
354         $node->attributes->{'foo'} = 'bar';
355
356       ...to write foo => bar.
357
358   clear_daughters()
359       This unlinks all $mother's daughters.  Returns the list of what used to
360       be $mother's daughters.
361
362       Not to be confused with "remove_daughters(LIST)".
363
364   common(LIST)
365       Returns the lowest node in the tree that is ancestor-or-self to the
366       nodes $node and LIST.
367
368       If the nodes are far enough apart in the tree, the answer is just the
369       root.
370
371       If the nodes aren't all in the same tree, the answer is undef.
372
373       As a degenerate case, if LIST is empty, returns $node.
374
375   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
381       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
385       If the nodes aren't all in the same tree, the answer is undef.
386
387       As a degenerate case, if LIST is empty, returns $node's mother; that'll
388       be undef if $node is root.
389
390   copy($option)
391       Returns a copy of the calling node (the invocant). E.g.: my($copy) =
392       $node -> copy;
393
394       $option is a hashref of options, with these (key => value) pairs:
395
396       o no_attribute_copy => $Boolean
397           If set to 1, do not copy the node's attributes.
398
399           If not specified, defaults to 0, which copies attributes.
400
401   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
406       If you pass no options, copy_at_and_under pretends you've passed {}.
407
408       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
412       Options you specify are passed down to calls to $node->copy.
413
414   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
419       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
423       Options you specify are passed down to calls to $node->copy.
424
425   daughters()
426       This returns the (possibly empty) list of daughters for $node.
427
428   decode_lol($lol)
429       Returns an arrayref having decoded the deeply nested structure $lol.
430
431       $lol will be the output of either tree_to_lol() or
432       tree_to_simple_lol().
433
434       See scripts/read.tree.pl, and it's output file scripts/read.tree.log.
435
436   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
443       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
447       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
450         Can't locate object method "leaves_under"
451           via package "DEADNODE".
452
453       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
458       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
464       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
469       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
474       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
481             # 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
490       (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
493       See also "WHEN AND HOW TO DESTROY THE TREE".
494
495   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
502   descendants()
503       Returns a list consisting of all the descendants of $node.  Returns
504       empty-list if $node is a terminal_node.
505
506       (Note that it's spelled "descendants", not "descendents".)
507
508   draw_ascii_tree([$options])
509       Here, the [] refer to an optional parameter.
510
511       Returns an arrayref of lines suitable for printing.
512
513       Draws a nice ASCII-art representation of the tree structure.
514
515       The tree looks like:
516
517                            |
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
534       See scripts/cut.and.paste.subtrees.pl.
535
536       Example usage:
537
538         print map("$_\n", @{$tree->draw_ascii_tree});
539
540       draw_ascii_tree() takes parameters you set in the $options hashref:
541
542       o h_compact
543           Takes 0 or 1.  Sets the extent to which draw_ascii_tree() tries to
544           save horizontal space.
545
546           If I think of a better scrunching algorithm, there'll be a "2"
547           setting for this.
548
549           Default: 1.
550
551       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
555           Default: 1.
556
557       o no_name
558           If true, draw_ascii_tree() doesn't print the name of the node; it
559           simply prints a "*".
560
561           Default: 0 (i.e., print the node name.)
562
563       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
567       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
570       See also "tree2string($options, [$some_tree])".
571
572   dump_names($options)
573       Returns an array.
574
575       Dumps, as an indented list, the names of the nodes starting at $node,
576       and continuing under it.  Options are:
577
578       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
583           Default: 0.
584
585       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
589           Default: ''.
590
591       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
595           Default: ' ' x 2.
596
597       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
600   format_node($options, $node)
601       Returns a string consisting of the node's name and, optionally, it's
602       attributes.
603
604       Possible keys in the $options hashref:
605
606       o no_attributes => $Boolean
607           If 1, the node's attributes are not included in the string
608           returned.
609
610           Default: 0 (include attributes).
611
612       Calls "hashref2string($hashref)".
613
614       Called by "node2string($options, $node, $vert_dashes)".
615
616       You would not normally call this method.
617
618       If you don't wish to supply options, use format_node({}, $node).
619
620   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
625       Of course, $node is always in its own generation.
626
627   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
631           @us = $node->generation_under( $node->mother->mother );
632
633       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
638       Actually, "generation_under($node)" is just an alias to "generation()",
639       but I figure that this:
640
641          @us = $node->generation_under($way_upline);
642
643       is a bit more readable than this:
644
645          @us = $node->generation($way_upline);
646
647       But it's up to you.
648
649       $node->generation_under($node) returns just $node.
650
651       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
655   hashref2string($hashref)
656       Returns the given hashref as a string.
657
658       Called by "format_node($options, $node)".
659
660   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
664   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
669   is_root()
670       Returns 1 if the caller is the root, and 0 if it is not.
671
672   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
678   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
683       See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
684
685   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
690       See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
691
692   lol_to_tree($lol)
693       This must be called as a class method.
694
695       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
700       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
708       An example will illustrate:
709
710         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
726       ...returns this tree:
727
728                          |
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
745       By the way (and this rather follows from the above rules), when
746       denoting a LoL tree consisting of just one node, this:
747
748         $tree = Tree::DAG_Node->lol_to_tree( 'Lonely' );
749
750       is okay, although it'd probably occur to you to denote it only as:
751
752         $tree = Tree::DAG_Node->lol_to_tree( ['Lonely'] );
753
754       which is of course fine, too.
755
756   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
760       See also "is_root()" and "root()".
761
762   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
767       As a special case, returns 0 if $node has no mother.
768
769   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
774   new($hashref)
775       These options are supported in $hashref:
776
777       o attributes => A hashref of attributes
778       o daughters => An arrayref of nodes
779       o mother => A node
780       o name => A string
781
782       See also "MAIN CONSTRUCTOR, AND INITIALIZER" for a long discussion on
783       object creation.
784
785   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
791             $daughter = $mother->new;
792             $mother->add_daughter($daughter);
793
794       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
800       As you'd expect for a constructor, it returns the node-object created.
801
802       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
806   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
811       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
815   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
819       Possible keys in the $options hashref:
820
821       o no_attributes => $Boolean
822           If 1, the node's attributes are not included in the string
823           returned.
824
825           Default: 0 (include attributes).
826
827       Ignore the parameter $vert_dashes. The code uses it as temporary
828       storage.
829
830       Calls "format_node($options, $node)".
831
832       Called by "tree2string($options, [$some_tree])".
833
834   quote_name($name)
835       Returns the string "'$name'", which is used in various methods for
836       outputting node names.
837
838   random_network($options)
839       This method can be called as a class method or as an object method.
840
841       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
845       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
854       It takes four options:
855
856       o max_node_count -- maximum number of nodes this tree will be allowed
857       to have (counting the root)
858           Default: 25.
859
860       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
865           Default: 2.
866
867       o max_depth -- maximum depth for the tree
868           The tree will not be deeper than this.
869
870           Default: 3 plus min_depth.
871
872       o max_children -- maximum number of children any mother in the tree can
873       have.
874           Default: 4.
875
876   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
880       This bascially means the attribute string was generated by
881       "hashref2string($hashref)".
882
883       Attributes may be absent, in which case they default to {}.
884
885       Returns a new node with this name and these attributes.
886
887       This method is for use by "read_tree($file_name)".
888
889       See t/tree.without.attributes.txt and t/tree.with.attributes.txt for
890       sample data.
891
892   read_tree($file_name)
893       Returns the root of the tree read from $file_name.
894
895       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
899       read_tree() works with utf-8 data. See t/read.tree.t and
900       t/tree.utf8.attributes.txt.
901
902       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
907       For reading and writing trees to databases, see
908       Tree::DAG_Node::Persist.
909
910       Calls "string2hashref($s)".
911
912   remove_daughter(LIST)
913       An exact synonym for "remove_daughters(LIST)".
914
915   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
920       Not to be confused with "clear_daughters()".
921
922   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
927       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
932       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
937       (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
941       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
948         $New->set_daughters($Old->clear_daughters);
949         $Old->replace_with($New);
950
951       (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
954         $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
959       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
963       In other words, this method does what it has to, as you'd expect it to.
964
965   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
972       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
975       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
981       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
985   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
990       See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
991
992   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
997       See also "add_left_sisters(LIST)" and "add_right_sisters(LIST)".
998
999   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
1003       Not to be confused with "is_root()".
1004
1005   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
1009       (Note that it's spelled "descendants", not "descendents".)
1010
1011   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
1017       (Contrary to how you may interpret how this method is named, "self" is
1018       not (necessarily) the first element of what's returned.)
1019
1020   set_daughters(LIST)
1021       This unlinks all $mother's daughters, and replaces them with the
1022       daughters in LIST.
1023
1024       Currently implemented as just $mother->clear_daughters followed by
1025       $mother->add_daughters(LIST).
1026
1027   simple_lol_to_tree($simple_lol)
1028       This must be called as a class method.
1029
1030       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
1037           $tree = Tree::DAG_Node->simple_lol_to_tree(
1038             [ 'foo', ['bar', ['baz'], 'quux'], 'zaz', 'pati' ]
1039           );
1040
1041       converts from something like a Lispish or Iconish tree, if you pretend
1042       the brackets are parentheses.
1043
1044       Note that there is a (possibly surprising) degenerate case of what I'm
1045       calling a "simple-LoL", and it's like this:
1046
1047         $tree = Tree::DAG_Node->simple_lol_to_tree('Lonely');
1048
1049       This is the (only) way you can specify a tree consisting of only a
1050       single node, which here gets the name 'Lonely'.
1051
1052   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
1057   string2hashref($s)
1058       Returns the hashref built from the string.
1059
1060       The string is expected to be something like '{AutoCommit => '1',
1061       PrintError => "0", ReportError => 1}'.
1062
1063       The empty string is returned as {}.
1064
1065       Called by "read_tree($file_name)".
1066
1067   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
1073       Undefined node names are returned as the string 'undef'.
1074
1075       See also "decode_lol($lol)".
1076
1077       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
1081   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
1089       For example, starting with the tree from the above example, this:
1090
1091         print $tree->tree_to_lol_notation, "\n";
1092
1093       prints the following (which I've broken over two lines for sake of
1094       printability of documentation):
1095
1096         [[[['Det:The'], [['dog'], 'N'], 'NP'], [["/with rabies\x5c"],
1097         'PP'], 'NP'], [['died'], 'VP'], 'S'],
1098
1099       Doing this:
1100
1101         print $tree->tree_to_lol_notation({ multiline => 1 });
1102
1103       prints the same content, just spread over many lines, and prettily
1104       indented.
1105
1106       Undefined node names are returned as the string 'undef'.
1107
1108   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
1114       Note that in the case of $node being terminal, what you get back is the
1115       same as $node->name.
1116
1117       Compare to tree_to_simple_lol_notation.
1118
1119       Undefined node names are returned as the string 'undef'.
1120
1121       See also "decode_lol($lol)".
1122
1123   tree_to_simple_lol_notation($options)
1124       A simple-LoL version of tree_to_lol_notation (which see); takes the
1125       same options.
1126
1127       Undefined node names are returned as the string 'undef'.
1128
1129   tree2string($options, [$some_tree])
1130       Here, the [] represent an optional parameter.
1131
1132       Returns an arrayref of lines, suitable for printing.
1133
1134       Draws a nice ASCII-art representation of the tree structure.
1135
1136       The tree looks like:
1137
1138               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
1161       Or, without attributes:
1162
1163               Root
1164                   |--- Â
1165                   |    |--- â
1166                   |    |    |--- É
1167                   |    |--- ä
1168                   |    |--- é
1169                   |         |--- Ñ
1170                   |              |--- ñ
1171                   |                   |--- Ô
1172                   |                        |--- ô
1173                   |                        |--- ô
1174                   |--- ß
1175                        |--- ®
1176                        |    |--- ©
1177                        |--- £
1178                        |--- €
1179                        |--- √
1180                        |--- ×xX
1181                             |--- í
1182                             |--- ú
1183                             |--- «
1184                             |--- »
1185
1186       See scripts/cut.and.paste.subtrees.pl.
1187
1188       Example usage:
1189
1190         print map("$_\n", @{$tree->tree2string});
1191
1192       Can be called with $some_tree set to any $node, and will print the tree
1193       assuming $node is the root.
1194
1195       If you don't wish to supply options, use tree2string({}, $node).
1196
1197       Possible keys in the $options hashref (which defaults to {}):
1198
1199       o no_attributes => $Boolean
1200           If 1, the node's attributes are not included in the string
1201           returned.
1202
1203           Default: 0 (include attributes).
1204
1205       Calls "node2string($options, $node, $vert_dashes)".
1206
1207       See also "draw_ascii_tree([$options])".
1208
1209   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
1213       Returns the mother unlinked from (if any).
1214
1215   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
1222       This is what walk_down() does, in pseudocode form:
1223
1224       o Starting point
1225           Start at the $node given.
1226
1227       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
1233       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
1239       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
1247       o Return
1248
1249       $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
1256       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
1262       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
1267       Note that the existence of walk_down() doesn't mean you can't write you
1268       own special-use traversers.
1269

WHEN AND HOW TO DESTROY THE TREE

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
1275       But consider this case:  you've got this tree:
1276
1277             A
1278           / | \
1279          B  C  D
1280          |     | \
1281          E     X  Y
1282
1283       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
1287            A                        D
1288           / \                      / \
1289          B   C                    X   Y
1290          |
1291          E
1292
1293       To destroy D and its little tree, you have to explicitly call
1294       delete_tree on it.
1295
1296       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
1303       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
1306         foreach my $it ($node->clear_daughters) { $it->delete_tree }
1307
1308       Just be sure not to do this:
1309
1310         foreach my $it ($node->daughters) { $it->delete_tree }
1311         $node->clear_daughters;
1312
1313       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

BUG REPORTS

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

HELP!

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
1330       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

RAMBLINGS

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
1346       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
1350         die "Not a node!!!" unless UNIVERSAL::can($node, "is_node");
1351
1352       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
1359       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
1366       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

FAQ

1378   Which is the best tree processing module?
1379       "Tree::DAG_Node", as it happens. More details: "SEE ALSO".
1380
1381   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
1385               my(@stack);
1386
1387               $tree -> walk_down
1388               ({
1389                       callback =>
1390                       sub
1391                       {
1392                               my(@node, $options) = @_;
1393
1394                               # Process $node, using $options...
1395
1396                               push @{$$options{stack} }, $node -> name;
1397
1398                               return 1; # Keep walking.
1399                       },
1400                       _depth => 0,
1401                       stack  => \@stack,
1402               });
1403
1404               # Process @stack...
1405
1406   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
1411       o The node's attributes
1412           In "Tree" you use $node -> meta and in "Tree::DAG_Node" it's $node
1413           -> attributes.
1414
1415   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
1420                   $mother->set_daughters(@them);
1421
1422       o Select a sub-set of nodes
1423                   $mother->set_daughters
1424                   (
1425                           grep($_->name =~ /wanted/, $mother->daughters)
1426                   );
1427
1428   Why did you break up the sections of methods in the POD?
1429       Because I want to list the methods in alphabetical order.
1430
1431   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

SEE ALSO

1436       o HTML::Element, HTML::Tree and HTML::TreeBuilder
1437           Sean is also the author of these modules.
1438
1439       o Tree
1440           Lightweight.
1441
1442       o Tree::Binary
1443           Lightweight.
1444
1445       o Tree::DAG_Node::Persist
1446           Lightweight.
1447
1448       o Tree::Persist
1449           Lightweight.
1450
1451       o Forest
1452           Uses Moose.
1453
1454       "Tree::DAG_Node" itself is also lightweight.
1455

REFERENCES

1457       Wirth, Niklaus.  1976.  Algorithms + Data Structures = Programs
1458       Prentice-Hall, Englewood Cliffs, NJ.
1459
1460       Knuth, Donald Ervin.  1997.  Art of Computer Programming, Volume 1,
1461       Third Edition: Fundamental Algorithms.  Addison-Wesley,  Reading, MA.
1462
1463       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
1469       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

MACHINE-READABLE CHANGE LOG

1478       The file Changes was converted into Changelog.ini by
1479       Module::Metadata::Changes.
1480

REPOSITORY

1482       <https://github.com/ronsavage/Tree-DAG_Node>
1483

SUPPORT

1485       Email the author, or log a bug on RT:
1486
1487       <https://rt.cpan.org/Public/Dist/Display.html?Name=Tree-DAG_Node>.
1488

ACKNOWLEDGEMENTS

1490       The code to print the tree, in tree2string(), was adapted from
1491       Forest::Tree::Writer::ASCIIWithBranches by the dread Stevan Little.
1492

MAINTAINER

1494       David Hand, "<cogent@cpan.org>" up to V 1.06.
1495
1496       Ron Savage "<rsavage@cpan.org>" from V 1.07.
1497
1498       In this POD, usage of 'I' refers to Sean, up until V 1.07.
1499

AUTHOR

1501       Sean M. Burke, "<sburke@cpan.org>"
1502

COPYRIGHT, LICENSE, AND DISCLAIMER

1504       Copyright 1998-2001, 2004, 2007 by Sean M. Burke and David Hand.
1505
1506       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
1510       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.
1513
1514
1515
1516perl v5.32.0                      2020-07-28                 Tree::DAG_Node(3)
Impressum