1Tree::DAG_Node(3) User Contributed Perl Documentation Tree::DAG_Node(3)
2
6 Tree::DAG_Node - (super)class for representing nodes in a tree
7
9 Using as a base class:
10 package Game::Tree::Node; # or whatever you're doing
12 use Tree::DAG_Node;
13 @ISA = qw(Tree::DAG_Node);
14 ...your own methods overriding/extending
15 the methods in Tree::DAG_Node...
16 Using as a class of its own:
18 use Tree::DAG_Node;
20 my $root = Tree::DAG_Node->new();
21 $root->name("I'm the tops");
22 my $new_daughter = $root->new_daughter;
23 $new_daughter->name("More");
24 ...
25
27 This class encapsulates/makes/manipulates objects that represent nodes
28 in a tree structure. The tree structure is not an object itself, but is
29 emergent from the linkages you create between nodes. This class
30 provides the methods for making linkages that can be used to build up a
31 tree, while preventing you from ever making any kinds of linkages which
32 are not allowed in a tree (such as having a node be its own mother or
33 ancestor, or having a node have two mothers).
34 This is what I mean by a "tree structure", a bit redundantly stated:
36 * A tree is a special case of an acyclic directed graph.
38 * A tree is a network of nodes where there's exactly one root node
40 (i.e., 'the top'), and the only primary relationship between nodes is
41 the mother-daugher relationship.
42 * No node can be its own mother, or its mother's mother, etc.
44 * Each node in the tree has exactly one "parent" (node in the "up"
46 direction) -- except the root, which is parentless.
47 * Each node can have any number (0 to any finite number) of daughter
49 nodes. A given node's daughter nodes constitute an ordered list.
50 (However, you are free to consider this ordering irrelevant. Some
51 applications do need daughters to be ordered, so I chose to consider
52 this the general case.)
53 * A node can appear in only one tree, and only once in that tree.
55 Notably (notable because it doesn't follow from the two above points),
56 a node cannot appear twice in its mother's daughter list.
57 * In other words, there's an idea of up (toward the root) versus down
59 (away from the root), and left (i.e., toward the start (index 0) of a
60 given node's daughter list) versus right (toward the end of a given
61 node's daughter list).
62 Trees as described above have various applications, among them:
64 representing syntactic constituency, in formal linguistics;
65 representing contingencies in a game tree; representing abstract syntax
66 in the parsing of any computer language -- whether in expression trees
67 for programming languages, or constituency in the parse of a markup
68 language document. (Some of these might not use the fact that
69 daughters are ordered.)
70 (Note: B-Trees are a very special case of the above kinds of trees, and
72 are best treated with their own class. Check CPAN for modules
73 encapsulating B-Trees; or if you actually want a database, and for some
74 reason ended up looking here, go look at AnyDBM_File.)
75 Many base classes are not usable except as such -- but Tree::DAG_Node
77 can be used as a normal class. You can go ahead and say:
78 use Tree::DAG_Node;
80 my $root = Tree::DAG_Node->new();
81 $root->name("I'm the tops");
82 $new_daughter = Tree::DAG_Node->new();
83 $new_daughter->name("More");
84 $root->add_daughter($new_daughter);
85 and so on, constructing and linking objects from Tree::DAG_Node and
87 making useful tree structures out of them.
88
90 This class is big and provides lots of methods. If your problem is
91 simple (say, just representing a simple parse tree), this class might
92 seem like using an atomic sledgehammer to swat a fly. But the
93 complexity of this module's bells and whistles shouldn't detract from
94 the efficiency of using this class for a simple purpose. In fact, I'd
95 be very surprised if any one user ever had use for more that even a
96 third of the methods in this class. And remember: an atomic
97 sledgehammer will kill that fly.
98
100 Implementationally, each node in a tree is an object, in the sense of
101 being an arbitrarily complex data structure that belongs to a class
102 (presumably Tree::DAG_Node, or ones derived from it) that provides
103 methods.
104 The attributes of a node-object are:
106 mother -- this node's mother. undef if this is a root.
108 daughters -- the (possibly empty) list of daughters of this node.
109 name -- the name for this node.
110 Need not be unique, or even printable. This is printed in some of
111 the various dumper methods, but it's up to you if you don't put
112 anything meaningful or printable here.
113 attributes -- whatever the user wants to use it for.
115 Presumably a hashref to whatever other attributes the user wants to
116 store without risk of colliding with the object's real attributes.
117 (Example usage: attributes to an SGML tag -- you definitely
118 wouldn't want the existence of a "mother=foo" pair in such a tag to
119 collide with a node object's 'mother' attribute.)
120 Aside from (by default) initializing it to {}, and having the
122 access method called "attributes" (described a ways below), I don't
123 do anything with the "attributes" in this module. I basically
124 intended this so that users who don't want/need to bother deriving
125 a class from Tree::DAG_Node, could still attach whatever data they
126 wanted in a node.
127 "mother" and "daughters" are attributes that relate to linkage -- they
129 are never written to directly, but are changed as appropriate by the
130 "linkage methods", discussed below.
131 The other two (and whatever others you may add in derived classes) are
133 simply accessed thru the same-named methods, discussed further below.
134 ABOUT THE DOCUMENTED INTERFACE
136 Stick to the documented interface (and comments in the source --
137 especially ones saying "undocumented!" and/or "disfavored!" -- do not
138 count as documentation!), and don't rely on any behavior that's not in
139 the documented interface.
140 Specifically, unless the documentation for a particular method says
142 "this method returns thus-and-such a value", then you should not rely
143 on it returning anything meaningful.
144 A passing acquintance with at least the broader details of the source
146 code for this class is assumed for anyone using this class as a base
147 class -- especially if you're overriding existing methods, and
148 definitely if you're overriding linkage methods.
149
151 the constructor CLASS->new() or CLASS->new({...options...})
152 This creates a new node object, calls
153 $object->_init({...options...}) to provide it sane defaults (like:
154 undef name, undef mother, no daughters, 'attributes' setting of a
155 new empty hashref), and returns the object created. (If you just
156 said "CLASS->new()" or "CLASS->new", then it pretends you called
157 "CLASS->new({})".)
158 Currently no options for putting in {...options...} are part of the
160 documented interface, but the options is here in case you want to
161 add such behavior in a derived class.
162 Read on if you plan on using Tree::DAG_New as a base class.
164 (Otherwise feel free to skip to the description of _init.)
165 There are, in my mind, two ways to do object construction:
167 Way 1: create an object, knowing that it'll have certain
169 uninteresting sane default values, and then call methods to change
170 those values to what you want. Example:
171 $node = Tree::DAG_Node->new;
173 $node->name('Supahnode!');
174 $root->add_daughter($node);
175 $node->add_daughters(@some_others)
176 Way 2: be able to specify some/most/all the object's attributes in
178 the call to the constructor. Something like:
179 $node = Tree::DAG_Node->new({
181 name => 'Supahnode!',
182 mother => $root,
183 daughters => \@some_others
184 });
185 After some deliberation, I've decided that the second way is a Bad
187 Thing. First off, it is not markedly more concise than the first
188 way. Second off, it often requires subtly different syntax (e.g.,
189 \@some_others vs @some_others). It just complicates things for the
190 programmer and the user, without making either appreciably happier.
191 (This is not to say that options in general for a constructor are
193 bad -- "random_network", discussed far below, necessarily takes
194 options. But note that those are not options for the default
195 values of attributes.)
196 Anyway, if you use Tree::DAG_Node as a superclass, and you add
198 attributes that need to be initialized, what you need to do is
199 provide an _init method that calls $this->SUPER::_init($options) to
200 use its superclass's _init method, and then initializes the new
201 attributes:
202 sub _init {
204 my($this, $options) = @_[0,1];
205 $this->SUPER::_init($options); # call my superclass's _init to
206 # init all the attributes I'm inheriting
207 # Now init /my/ new attributes:
209 $this->{'amigos'} = []; # for example
210 }
211 ...or, as I prefer when I'm being a neat freak:
213 sub _init {
215 my($this, $options) = @_[0,1];
216 $this->SUPER::_init($options);
217 $this->_init_amigos($options);
219 }
220 sub _init_amigos {
222 my $this = $_[0];
223 # Or my($this,$options) = @_[0,1]; if I'm using $options
224 $this->{'amigos'} = [];
225 }
226 In other words, I like to have each attribute initialized thru a
228 method named _init_[attribute], which should expect the object as
229 $_[0] and the the options hashref (or {} if none was given) as
230 $_[1]. If you insist on having your _init recognize options for
231 setting attributes, you might as well have them dealt with by the
232 appropriate _init_[attribute] method, like this:
233 sub _init {
235 my($this, $options) = @_[0,1];
236 $this->SUPER::_init($options);
237 $this->_init_amigos($options);
239 }
240 sub _init_amigos {
242 my($this,$options) = @_[0,1]; # I need options this time
243 $this->{'amigos'} = [];
244 $this->amigos(@{$options->{'amigos'}}) if $options->{'amigos'};
245 }
246 All this bookkeeping looks silly with just one new attribute in a
248 class derived straight from Tree::DAG_Node, but if there's lots of
249 new attributes running around, and if you're deriving from a class
250 derived from a class derived from Tree::DAG_Node, then tidy
251 stratification/modularization like this can keep you sane.
252 the constructor $obj->new() or $obj->new({...options...})
254 Just another way to get at the "new" method. This does not copy
255 $obj, but merely constructs a new object of the same class as it.
256 Saves you the bother of going $class = ref $obj; $obj2 =
257 $class->new;
258 the method $node->_init({...options...})
260 Initialize the object's attribute values. See the discussion
261 above. Presumably this should be called only by the guts of the
262 "new" constructor -- never by the end user.
263 Currently there are no documented options for putting in
265 {...options...}, but (in case you want to disregard the above rant)
266 the option exists for you to use {...options...} for something
267 useful in a derived class.
268 Please see the source for more information.
270 see also (below) the constructors "new_daughter" and
272 "new_daughter_left"
273
275 $node->daughters
276 This returns the (possibly empty) list of daughters for $node.
277 $node->mother
279 This returns what node is $node's mother. This is undef if $node
280 has no mother -- i.e., if it is a root.
281 $mother->add_daughters( LIST )
283 This method adds the node objects in LIST to the (right) end of
284 $mother's "daughter" list. Making a node N1 the daughter of
285 another node N2 also means that N1's "mother" attribute is
286 "automatically" set to N2; it also means that N1 stops being
287 anything else's daughter as it becomes N2's daughter.
288 If you try to make a node its own mother, a fatal error results.
290 If you try to take one of a a node N1's ancestors and make it also
291 a daughter of N1, a fatal error results. A fatal error results if
292 anything in LIST isn't a node object.
293 If you try to make N1 a daughter of N2, but it's already a daughter
295 of N2, then this is a no-operation -- it won't move such nodes to
296 the end of the list or anything; it just skips doing anything with
297 them.
298 $node->add_daughter( LIST )
300 An exact synonym for $node->add_daughters(LIST)
301 $mother->add_daughters_left( LIST )
303 This method is just like "add_daughters", except that it adds the
304 node objects in LIST to the (left) beginning of $mother's daughter
305 list, instead of the (right) end of it.
306 $node->add_daughter_left( LIST )
308 An exact synonym for $node->add_daughters_left( LIST )
309 Note:
311 The above link-making methods perform basically an "unshift" or
312 "push" on the mother node's daughter list. To get the full range
313 of list-handling functionality, copy the daughter list, and change
314 it, and then call "set_daughters" on the result:
315 @them = $mother->daughters;
317 @removed = splice(@them, 0,2, @new_nodes);
318 $mother->set_daughters(@them);
319 Or consider a structure like:
321 $mother->set_daughters(
323 grep($_->name =~ /NP/ ,
324 $mother->daughters
325 )
326 );
327 the constructor $daughter = $mother->new_daughter, or
329 the constructor $daughter = $mother->new_daughter({...options...})
330 This constructs a new node (of the same class as $mother), and adds
331 it to the (right) end of the daughter list of $mother. This is
332 essentially the same as going
333 $daughter = $mother->new;
335 $mother->add_daughter($daughter);
336 but is rather more efficient because (since $daughter is guaranteed
338 new and isn't linked to/from anything), it doesn't have to check
339 that $daughter isn't an ancestor of $mother, isn't already daughter
340 to a mother it needs to be unlinked from, isn't already in
341 $mother's daughter list, etc.
342 As you'd expect for a constructor, it returns the node-object
344 created.
345 the constructor $mother->new_daughter_left, or
347 $mother->new_daughter_left({...options...})
348 This is just like $mother->new_daughter, but adds the new daughter
349 to the left (start) of $mother's daughter list.
350 $mother->remove_daughters( LIST )
352 This removes the nodes listed in LIST from $mother's daughter list.
353 This is a no-operation if LIST is empty. If there are things in
354 LIST that aren't a current daughter of $mother, they are ignored.
355 Not to be confused with $mother->clear_daughters.
357 $node->remove_daughter( LIST )
359 An exact synonym for $node->remove_daughters( LIST )
360 $node->unlink_from_mother
362 This removes node from the daughter list of its mother. If it has
363 no mother, this is a no-operation.
364 Returns the mother unlinked from (if any).
366 $mother->clear_daughters
368 This unlinks all $mother's daughters. Returns the the list of what
369 used to be $mother's daughters.
370 Not to be confused with $mother->remove_daughters( LIST ).
372 $mother->set_daughters( LIST )
374 This unlinks all $mother's daughters, and replaces them with the
375 daughters in LIST.
376 Currently implemented as just $mother->clear_daughters followed by
378 $mother->add_daughters( LIST ).
379 $node->replace_with( LIST )
381 This replaces $node in its mother's daughter list, by unlinking
382 $node and replacing it with the items in LIST. This returns a list
383 consisting of $node followed by LIST, i.e., the nodes that replaced
384 it.
385 LIST can include $node itself (presumably at most once). LIST can
387 also be empty-list. However, if any items in LIST are sisters to
388 $node, they are ignored, and are not in the copy of LIST passed as
389 the return value.
390 As you might expect for any linking operation, the items in LIST
392 cannot be $node's mother, or any ancestor to it; and items in LIST
393 are, of course, unlinked from their mothers (if they have any) as
394 they're linked to $node's mother.
395 (In the special (and bizarre) case where $node is root, this simply
397 calls $this->unlink_from_mother on all the items in LIST, making
398 them roots of their own trees.)
399 Note that the daughter-list of $node is not necessarily affected;
401 nor are the daughter-lists of the items in LIST. I mention this in
402 case you think replace_with switches one node for another, with
403 respect to its mother list and its daughter list, leaving the rest
404 of the tree unchanged. If that's what you want, replacing $Old with
405 $New, then you want:
406 $New->set_daughters($Old->clear_daughters);
408 $Old->replace_with($New);
409 (I can't say $node's and LIST-items' daughter lists are never
411 affected my replace_with -- they can be affected in this case:
412 $N1 = ($node->daughters)[0]; # first daughter of $node
414 $N2 = ($N1->daughters)[0]; # first daughter of $N1;
415 $N3 = Tree::DAG_Node->random_network; # or whatever
416 $node->replace_with($N1, $N2, $N3);
417 As a side affect of attaching $N1 and $N2 to $node's mother,
419 they're unlinked from their parents ($node, and $N1, replectively).
420 But N3's daughter list is unaffected.
421 In other words, this method does what it has to, as you'd expect it
423 to.
424 $node->replace_with_daughters
426 This replaces $node in its mother's daughter list, by unlinking
427 $node and replacing it with its daughters. In other words, $node
428 becomes motherless and daughterless as its daughters move up and
429 take its place. This returns a list consisting of $node followed
430 by the nodes that were its daughters.
431 In the special (and bizarre) case where $node is root, this simply
433 unlinks its daughters from it, making them roots of their own
434 trees.
435 Effectively the same as $node->replace_with($node->daughters), but
437 more efficient, since less checking has to be done. (And I also
438 think $node->replace_with_daughters is a more common operation in
439 tree-wrangling than $node->replace_with(LIST), so deserves a named
440 method of its own, but that's just me.)
441 $node->add_left_sisters( LIST )
443 This adds the elements in LIST (in that order) as immediate left
444 sisters of $node. In other words, given that B's mother's
445 daughter-list is (A,B,C,D), calling B->add_left_sisters(X,Y) makes
446 B's mother's daughter-list (A,X,Y,B,C,D).
447 If LIST is empty, this is a no-op, and returns empty-list.
449 This is basically implemented as a call to
451 $node->replace_with(LIST, $node), and so all replace_with's
452 limitations and caveats apply.
453 The return value of $node->add_left_sisters( LIST ) is the elements
455 of LIST that got added, as returned by replace_with -- minus the
456 copies of $node you'd get from a straight call to
457 $node->replace_with(LIST, $node).
458 $node->add_left_sister( LIST )
460 An exact synonym for $node->add_left_sisters(LIST)
461 $node->add_right_sisters( LIST )
463 Just like add_left_sisters (which see), except that the the
464 elements in LIST (in that order) as immediate right sisters of
465 $node;
466 In other words, given that B's mother's daughter-list is (A,B,C,D),
468 calling B->add_right_sisters(X,Y) makes B's mother's daughter-list
469 (A,B,X,Y,C,D).
470 $node->add_right_sister( LIST )
472 An exact synonym for $node->add_right_sisters(LIST)
473
475 $node->name or $node->name(SCALAR)
476 In the first form, returns the value of the node object's "name"
477 attribute. In the second form, sets it to the value of SCALAR.
478 $node->attributes or $node->attributes(SCALAR)
480 In the first form, returns the value of the node object's
481 "attributes" attribute. In the second form, sets it to the value
482 of SCALAR. I intend this to be used to store a reference to a
483 (presumably anonymous) hash the user can use to store whatever
484 attributes he doesn't want to have to store as object attributes.
485 In this case, you needn't ever set the value of this. (_init has
486 already initialized it to {}.) Instead you can just do...
487 $node->attributes->{'foo'} = 'bar';
489 ...to write foo => bar.
491 $node->attribute or $node->attribute(SCALAR)
493 An exact synonym for $node->attributes or $node->attributes(SCALAR)
494
496 $node->is_node
497 This always returns true. More pertinently,
498 $object->can('is_node') is true (regardless of what "is_node" would
499 do if called) for objects belonging to this class or for any class
500 derived from it.
501 $node->ancestors
503 Returns the list of this node's ancestors, starting with its
504 mother, then grandmother, and ending at the root. It does this by
505 simply following the 'mother' attributes up as far as it can. So
506 if $item IS the root, this returns an empty list.
507 Consider that scalar($node->ancestors) returns the ply of this node
509 within the tree -- 2 for a granddaughter of the root, etc., and 0
510 for root itself.
511 $node->root
513 Returns the root of whatever tree $node is a member of. If $node
514 is the root, then the result is $node itself.
515 $node->is_daughter_of($node2)
517 Returns true iff $node is a daughter of $node2. Currently
518 implemented as just a test of ($it->mother eq $node2).
519 $node->self_and_descendants
521 Returns a list consisting of itself (as element 0) and all the
522 descendants of $node. Returns just itself if $node is a
523 terminal_node.
524 (Note that it's spelled "descendants", not "descendents".)
526 $node->descendants
528 Returns a list consisting of all the descendants of $node. Returns
529 empty-list if $node is a terminal_node.
530 (Note that it's spelled "descendants", not "descendents".)
532 $node->leaves_under
534 Returns a list (going left-to-right) of all the leaf nodes under
535 $node. ("Leaf nodes" are also called "terminal nodes" -- i.e.,
536 nodes that have no daughters.) Returns $node in the degenerate
537 case of $node being a leaf itself.
538 $node->depth_under
540 Returns an integer representing the number of branches between this
541 $node and the most distant leaf under it. (In other words, this
542 returns the ply of subtree starting of $node. Consider
543 scalar($it->ancestors) if you want the ply of a node within the
544 whole tree.)
545 $node->generation
547 Returns a list of all nodes (going left-to-right) that are in
548 $node's generation -- i.e., that are the some number of nodes down
549 from the root. $root->generation is just $root.
550 Of course, $node is always in its own generation.
552 $node->generation_under(NODE2)
554 Like $node->generation, but returns only the nodes in $node's
555 generation that are also descendants of NODE2 -- in other words,
556 @us = $node->generation_under( $node->mother->mother );
558 is all $node's first cousins (to borrow yet more kinship
560 terminology) -- assuming $node does indeed have a grandmother.
561 Actually "cousins" isn't quite an apt word, because @us ends up
562 including $node's siblings and $node.
563 Actually, "generation_under" is just an alias to "generation", but
565 I figure that this:
566 @us = $node->generation_under($way_upline);
568 is a bit more readable than this:
570 @us = $node->generation($way_upline);
572 But it's up to you.
574 $node->generation_under($node) returns just $node.
576 If you call $node->generation_under($node) but NODE2 is not $node
578 or an ancestor of $node, it behaves as if you called just
579 $node->generation().
580 $node->self_and_sisters
582 Returns a list of all nodes (going left-to-right) that have the
583 same mother as $node -- including $node itself. This is just like
584 $node->mother->daughters, except that that fails where $node is
585 root, whereas $root->self_and_siblings, as a special case, returns
586 $root.
587 (Contrary to how you may interpret how this method is named, "self"
589 is not (necessarily) the first element of what's returned.)
590 $node->sisters
592 Returns a list of all nodes (going left-to-right) that have the
593 same mother as $node -- not including $node itself. If $node is
594 root, this returns empty-list.
595 $node->left_sister
597 Returns the node that's the immediate left sister of $node. If
598 $node is the leftmost (or only) daughter of its mother (or has no
599 mother), then this returns undef.
600 (See also $node->add_left_sisters(LIST).)
602 $node->left_sisters
604 Returns a list of nodes that're sisters to the left of $node. If
605 $node is the leftmost (or only) daughter of its mother (or has no
606 mother), then this returns an empty list.
607 (See also $node->add_left_sisters(LIST).)
609 $node->right_sister
611 Returns the node that's the immediate right sister of $node. If
612 $node is the rightmost (or only) daughter of its mother (or has no
613 mother), then this returns undef.
614 (See also $node->add_right_sisters(LIST).)
616 $node->right_sisters
618 Returns a list of nodes that're sisters to the right of $node. If
619 $node is the rightmost (or only) daughter of its mother (or has no
620 mother), then this returns an empty list.
621 (See also $node->add_right_sisters(LIST).)
623 $node->my_daughter_index
625 Returns what index this daughter is, in its mother's "daughter"
626 list. In other words, if $node is ($node->mother->daughters)[3],
627 then $node->my_daughter_index returns 3.
628 As a special case, returns 0 if $node has no mother.
630 $node->address or $anynode->address(ADDRESS)
632 With the first syntax, returns the address of $node within its
633 tree, based on its position within the tree. An address is formed
634 by noting the path between the root and $node, and concatenating
635 the daughter-indices of the nodes this passes thru (starting with 0
636 for the root, and ending with $node).
637 For example, if to get from node ROOT to node $node, you pass thru
639 ROOT, A, B, and $node, then the address is determined as:
640 * ROOT's my_daughter_index is 0.
642 * A's my_daughter_index is, suppose, 2. (A is index 2 in ROOT's
644 daughter list.)
645 * B's my_daughter_index is, suppose, 0. (B is index 0 in A's
647 daughter list.)
648 * $node's my_daughter_index is, suppose, 4. ($node is index 4 in
650 B's daughter list.)
651 The address of the above-described $node is, therefore, "0:2:0:4".
653 (As a somewhat special case, the address of the root is always "0";
655 and since addresses start from the root, all addresses start with a
656 "0".)
657 The second syntax, where you provide an address, starts from the
659 root of the tree $anynode belongs to, and returns the node
660 corresponding to that address. Returns undef if no node
661 corresponds to that address. Note that this routine may be
662 somewhat liberal in its interpretation of what can constitute an
663 address; i.e., it accepts "0.2.0.4", besides "0:2:0:4".
664 Also note that the address of a node in a tree is meaningful only
666 in that tree as currently structured.
667 (Consider how ($address1 cmp $address2) may be magically meaningful
669 to you, if you mant to figure out what nodes are to the right of
670 what other nodes.)
671 $node->common(LIST)
673 Returns the lowest node in the tree that is ancestor-or-self to the
674 nodes $node and LIST.
675 If the nodes are far enough apart in the tree, the answer is just
677 the root.
678 If the nodes aren't all in the same tree, the answer is undef.
680 As a degenerate case, if LIST is empty, returns $node.
682 $node->common_ancestor(LIST)
684 Returns the lowest node that is ancestor to all the nodes given (in
685 nodes $node and LIST). In other words, it answers the question:
686 "What node in the tree, as low as possible, is ancestor to the
687 nodes given ($node and LIST)?"
688 If the nodes are far enough apart, the answer is just the root --
690 except if any of the nodes are the root itself, in which case the
691 answer is undef (since the root has no ancestor).
692 If the nodes aren't all in the same tree, the answer is undef.
694 As a degenerate case, if LIST is empty, returns $node's mother;
696 that'll be undef if $node is root.
697
699 $node->walk_down({ callback => \&foo, callbackback => \&foo, ... })
700 Performs a depth-first traversal of the structure at and under
701 $node. What it does at each node depends on the value of the
702 options hashref, which you must provide. There are three options,
703 "callback" and "callbackback" (at least one of which must be
704 defined, as a sub reference), and "_depth". This is what
705 "walk_down" does, in pseudocode form:
706 * Start at the $node given.
708 * If there's a "callback", call it with $node as the first
710 argument, and the options hashref as the second argument (which
711 contains the potentially useful "_depth", remember). This function
712 must return true or false -- if false, it will block the next step:
713 * If $node has any daughter nodes, increment "_depth", and call
715 $daughter->walk_down(options_hashref) for each daughter (in order,
716 of course), where options_hashref is the same hashref it was called
717 with. When this returns, decrements "_depth".
718 * If there's a "callbackback", call just it as with "callback" (but
720 tossing out the return value). Note that "callback" returning
721 false blocks traversal below $node, but doesn't block calling
722 callbackback for $node. (Incidentally, in the unlikely case that
723 $node has stopped being a node object, "callbackback" won't get
724 called.)
725 * Return.
727 $node->walk_down is the way to recursively do things to a tree (if
729 you start at the root) or part of a tree; if what you're doing is
730 best done via pre-pre order traversal, use "callback"; if what
731 you're doing is best done with post-order traversal, use
732 "callbackback". "walk_down" is even the basis for plenty of the
733 methods in this class. See the source code for examples both
734 simple and horrific.
735 Note that if you don't specify "_depth", it effectively defaults to
737 0. You should set it to scalar($node->ancestors) if you want
738 "_depth" to reflect the true depth-in-the-tree for the nodes
739 called, instead of just the depth below $node. (If $node is the
740 root, there's difference, of course.)
741 And by the way, it's a bad idea to modify the tree from the
743 callback. Unpredictable things may happen. I instead suggest
744 having your callback add to a stack of things that need changing,
745 and then, once "walk_down" is all finished, changing those nodes
746 from that stack.
747 Note that the existence of "walk_down" doesn't mean you can't write
749 you own special-use traversers.
750 @lines = $node->dump_names({ ...options... });
752 Dumps, as an indented list, the names of the nodes starting at
753 $node, and continuing under it. Options are:
754 * _depth -- A nonnegative number. Indicating the depth to consider
756 $node as being at (and so the generation under that is that plus
757 one, etc.). Defaults to 0. You may choose to use set _depth =>
758 scalar($node->ancestors).
759 * tick -- a string to preface each entry with, between the
761 indenting-spacing and the node's name. Defaults to empty-string.
762 You may prefer "*" or "-> " or someting.
763 * indent -- the string used to indent with. Defaults to " " (two
765 spaces). Another sane value might be ". " (period, space).
766 Setting it to empty-string suppresses indenting.
767 The dump is not printed, but is returned as a list, where each item
769 is a line, with a "\n" at the end.
770 the constructor CLASS->random_network({...options...})
772 the method $node->random_network({...options...})
773 In the first case, constructs a randomly arranged network under a
774 new node, and returns the root node of that tree. In the latter
775 case, constructs the network under $node.
776 Currently, this is implemented a bit half-heartedly, and half-
778 wittedly. I basically needed to make up random-looking networks to
779 stress-test the various tree-dumper methods, and so wrote this. If
780 you actually want to rely on this for any application more serious
781 than that, I suggest examining the source code and seeing if this
782 does really what you need (say, in reliability of randomness); and
783 feel totally free to suggest changes to me (especially in the form
784 of "I rewrote "random_network", here's the code...")
785 It takes four options:
787 * max_node_count -- maximum number of nodes this tree will be
789 allowed to have (counting the root). Defaults to 25.
790 * min_depth -- minimum depth for the tree. Defaults to 2. Leaves
792 can be generated only after this depth is reached, so the tree will
793 be at least this deep -- unless max_node_count is hit first.
794 * max_depth -- maximum depth for the tree. Defaults to 3 plus
796 min_depth. The tree will not be deeper than this.
797 * max_children -- maximum number of children any mother in the tree
799 can have. Defaults to 4.
800 the constructor CLASS->lol_to_tree($lol);
802 Converts something like bracket-notation for "Chomsky trees" (or
803 rather, the closest you can come with Perl
804 list-of-lists(-of-lists(-of-lists))) into a tree structure.
805 Returns the root of the tree converted.
806 The conversion rules are that: 1) if the last (possibly the only)
808 item in a given list is a scalar, then that is used as the "name"
809 attribute for the node based on this list. 2) All other items in
810 the list represent daughter nodes of the current node --
811 recursively so, if they are list references; otherwise, (non-
812 terminal) scalars are considered to denote nodes with that name.
813 So ['Foo', 'Bar', 'N'] is an alternate way to represent [['Foo'],
814 ['Bar'], 'N'].
815 An example will illustrate:
817 use Tree::DAG_Node;
819 $lol =
820 [
821 [
822 [ [ 'Det:The' ],
823 [ [ 'dog' ], 'N'], 'NP'],
824 [ '/with rabies\\', 'PP'],
825 'NP'
826 ],
827 [ 'died', 'VP'],
828 'S'
829 ];
830 $tree = Tree::DAG_Node->lol_to_tree($lol);
831 $diagram = $tree->draw_ascii_tree;
832 print map "$_\n", @$diagram;
833 ...returns this tree:
835 |
837 <S>
838 |
839 /------------------\
840 | |
841 <NP> <VP>
842 | |
843 /---------------\ <died>
844 | |
845 <NP> <PP>
846 | |
847 /-------\ </with rabies\>
848 | |
849 <Det:The> <N>
850 |
851 <dog>
852 By the way (and this rather follows from the above rules), when
854 denoting a LoL tree consisting of just one node, this:
855 $tree = Tree::DAG_Node->lol_to_tree( 'Lonely' );
857 is okay, although it'd probably occur to you to denote it only as:
859 $tree = Tree::DAG_Node->lol_to_tree( ['Lonely'] );
861 which is of course fine, too.
863 $node->tree_to_lol_notation({...options...})
865 Dumps a tree (starting at $node) as the sort of LoL-like bracket
866 notation you see in the above example code. Returns just one big
867 block of text. The only option is "multiline" -- if true, it dumps
868 the text as the sort of indented structure as seen above; if false
869 (and it defaults to false), dumps it all on one line (with no
870 indenting, of course).
871 For example, starting with the tree from the above example, this:
873 print $tree->tree_to_lol_notation, "\n";
875 prints the following (which I've broken over two lines for sake of
877 printablitity of documentation):
878 [[[['Det:The'], [['dog'], 'N'], 'NP'], [["/with rabies\x5c"],
880 'PP'], 'NP'], [['died'], 'VP'], 'S'],
881 Doing this:
883 print $tree->tree_to_lol_notation({ multiline => 1 });
885 prints the same content, just spread over many lines, and prettily
887 indented.
888 $node->tree_to_lol
890 Returns that tree (starting at $node) represented as a LoL, like
891 what $lol, above, holds. (This is as opposed to
892 "tree_to_lol_notation", which returns the viewable code like what
893 gets evaluated and stored in $lol, above.)
894 Lord only knows what you use this for -- maybe for feeding to
896 Data::Dumper, in case "tree_to_lol_notation" doesn't do just what
897 you want?
898 the constructor CLASS->simple_lol_to_tree($simple_lol);
900 This is like lol_to_tree, except that rule 1 doesn't apply -- i.e.,
901 all scalars (or really, anything not a listref) in the LoL-
902 structure end up as named terminal nodes, and only terminal nodes
903 get names (and, of course, that name comes from that scalar value).
904 This method is useful for making things like expression trees, or
905 at least starting them off. Consider that this:
906 $tree = Tree::DAG_Node->simple_lol_to_tree(
908 [ 'foo', ['bar', ['baz'], 'quux'], 'zaz', 'pati' ]
909 );
910 converts from something like a Lispish or Iconish tree, if you
912 pretend the brackets are parentheses.
913 Note that there is a (possibly surprising) degenerate case of what
915 I'm calling a "simple-LoL", and it's like this:
916 $tree = Tree::DAG_Node->simple_lol_to_tree('Lonely');
918 This is the (only) way you can specify a tree consisting of only a
920 single node, which here gets the name 'Lonely'.
921 $node->tree_to_simple_lol
923 Returns that tree (starting at $node) represented as a simple-LoL
924 -- i.e., one where non-terminal nodes are represented as listrefs,
925 and terminal nodes are gotten from the contents of those nodes'
926 "name' attributes.
927 Note that in the case of $node being terminal, what you get back is
929 the same as $node->name.
930 Compare to tree_to_simple_lol_notation.
932 $node->tree_to_simple_lol_notation({...options...})
934 A simple-LoL version of tree_to_lol_notation (which see); takes the
935 same options.
936 $list_r = $node->draw_ascii_tree({ ... options ... })
938 Draws a nice ASCII-art representation of the tree structure at-and-
939 under $node, with $node at the top. Returns a reference to the
940 list of lines (with no "\n"s or anything at the end of them) that
941 make up the picture.
942 Example usage:
944 print map("$_\n", @{$tree->draw_ascii_tree});
946 draw_ascii_tree takes parameters you set in the options hashref:
948 * "no_name" -- if true, "draw_ascii_tree" doesn't print the name of
950 the node; simply prints a "*". Defaults to 0 (i.e., print the node
951 name.)
952 * "h_spacing" -- number 0 or greater. Sets the number of spaces
954 inserted horizontally between nodes (and groups of nodes) in a
955 tree. Defaults to 1.
956 * "h_compact" -- number 0 or 1. Sets the extent to which
958 "draw_ascii_tree" tries to save horizontal space. Defaults to 1.
959 If I think of a better scrunching algorithm, there'll be a "2"
960 setting for this.
961 * "v_compact" -- number 0, 1, or 2. Sets the degree to which
963 "draw_ascii_tree" tries to save vertical space. Defaults to 1.
964 This occasionally returns trees that are a bit cock-eyed in parts;
966 if anyone can suggest a better drawing algorithm, I'd be
967 appreciative.
968 $node->copy_tree or $node->copy_tree({...options...})
970 This returns the root of a copy of the tree that $node is a member
971 of. If you pass no options, copy_tree pretends you've passed {}.
972 This method is currently implemented as just a call to
974 $this->root->copy_at_and_under({...options...}), but magic may be
975 added in the future.
976 Options you specify are passed down to calls to $node->copy.
978 $node->copy_at_and_under or $node->copy_at_and_under({...options...})
980 This returns a copy of the subtree consisting of $node and
981 everything under it.
982 If you pass no options, copy_at_and_under pretends you've passed
984 {}.
985 This works by recursively building up the new tree from the leaves,
987 duplicating nodes using $orig_node->copy($options_ref) and then
988 linking them up into a new tree of the same shape.
989 Options you specify are passed down to calls to $node->copy.
991 the constructor $node->copy or $node->copy({...options...})
993 Returns a copy of $node, minus its daughter or mother attributes
994 (which are set back to default values).
995 If you pass no options, "copy" pretends you've passed {}.
997 Magic happens with the 'attributes' attribute: if it's a hashref
999 (and it usually is), the new node doesn't end up with the same
1000 hashref, but with ref to a hash with the content duplicated from
1001 the original's hashref. If 'attributes' is not a hashref, but
1002 instead an object that belongs to a class that provides a method
1003 called "copy", then that method is called, and the result saved in
1004 the clone's 'attribute' attribute. Both of these kinds of magic
1005 are disabled if the options you pass to "copy" (maybe via
1006 "copy_tree", or "copy_at_and_under") includes ("no_attribute_copy"
1007 => 1).
1008 The options hashref you pass to "copy" (derictly or indirectly)
1010 gets changed slightly after you call "copy" -- it gets an entry
1011 called "from_to" added to it. Chances are you would never know nor
1012 care, but this is reserved for possible future use. See the source
1013 if you are wildly curious.
1014 Note that if you are using $node->copy (whether directly or via
1016 $node->copy_tree or $node->copy_at_or_under), and it's not properly
1017 copying object attributes containing references, you probably
1018 shouldn't fight it or try to fix it -- simply override copy_tree
1019 with:
1020 sub copy_tree {
1022 use Storable qw(dclone);
1023 my $this = $_[0];
1024 return dclone($this->root);
1025 # d for "deep"
1026 }
1027 or
1029 sub copy_tree {
1031 use Data::Dumper;
1032 my $this = $_[0];
1033 $Data::Dumper::Purity = 1;
1034 return eval(Dumper($this->root));
1035 }
1036 Both of these avoid you having to reinvent the wheel.
1038 How to override copy_at_or_under with something that uses Storable
1040 or Data::Dumper is left as an exercise to the reader.
1041 Consider that if in a derived class, you add attributes with really
1043 bizarre contents (like a unique-for-all-time-ID), you may need to
1044 override "copy". Consider:
1045 sub copy {
1047 my($it, @etc) = @_;
1048 $it->SUPER::copy(@etc);
1049 $it->{'UID'} = &get_new_UID;
1050 }
1051 ...or the like. See the source of Tree::DAG_Node::copy for
1053 inspiration.
1054 $node->delete_tree
1056 Destroys the entire tree that $node is a member of (starting at the
1057 root), by nulling out each node-object's attributes (including,
1058 most importantly, its linkage attributes -- hopefully this is more
1059 than sufficient to eliminate all circularity in the data
1060 structure), and then moving it into the class DEADNODE.
1061 Use this when you're finished with the tree in question, and want
1063 to free up its memory. (If you don't do this, it'll get freed up
1064 anyway when your program ends.)
1065 If you try calling any methods on any of the node objects in the
1067 tree you've destroyed, you'll get an error like:
1068 Can't locate object method "leaves_under"
1070 via package "DEADNODE".
1071 So if you see that, that's what you've done wrong. (Actually, the
1073 class DEADNODE does provide one method: a no-op method
1074 "delete_tree". So if you want to delete a tree, but think you may
1075 have deleted it already, it's safe to call $node->delete_tree on it
1076 (again).)
1077 The "delete_tree" method is needed because Perl's garbage collector
1079 would never (as currently implemented) see that it was time to de-
1080 allocate the memory the tree uses -- until either you call
1081 $node->delete_tree, or until the program stops (at "global
1082 destruction" time, when everything is unallocated).
1083 Incidentally, there are better ways to do garbage-collecting on a
1085 tree, ways which don't require the user to explicitly call a method
1086 like "delete_tree" -- they involve dummy classes, as explained at
1087 "http://mox.perl.com/misc/circle-destroy.pod"
1088 However, introducing a dummy class concept into Tree::DAG_Node
1090 would be rather a distraction. If you want to do this with your
1091 derived classes, via a DESTROY in a dummy class (or in a tree-
1092 metainformation class, maybe), then feel free to.
1093 The only case where I can imagine "delete_tree" failing to totally
1095 void the tree, is if you use the hashref in the "attributes"
1096 attribute to store (presumably among other things) references to
1097 other nodes' "attributes" hashrefs -- which 1) is maybe a bit odd,
1098 and 2) is your problem, because it's your hash structure that's
1099 circular, not the tree's. Anyway, consider:
1100 # null out all my "attributes" hashes
1102 $anywhere->root->walk_down({
1103 'callback' => sub {
1104 $hr = $_[0]->attributes; %$hr = (); return 1;
1105 }
1106 });
1107 # And then:
1108 $anywhere->delete_tree;
1109 (I suppose "delete_tree" is a "destructor", or as close as you can
1111 meaningfully come for a circularity-rich data structure in Perl.)
1112 When and How to Destroy
1114 It should be clear to you that if you've built a big parse tree or
1115 something, and then you're finished with it, you should call
1116 $some_node->delete_tree on it if you want the memory back.
1117 But consider this case: you've got this tree:
1119 A
1121 / | \
1122 B C D
1123 | | \
1124 E X Y
1125 Let's say you decide you don't want D or any of its descendants in the
1127 tree, so you call D->unlink_from_mother. This does NOT automagically
1128 destroy the tree D-X-Y. Instead it merely splits the tree into two:
1129 A D
1131 / \ / \
1132 B C X Y
1133 |
1134 E
1135 To destroy D and its little tree, you have to explicitly call
1137 delete_tree on it.
1138 Note, however, that if you call C->unlink_from_mother, and if you don't
1140 have a link to C anywhere, then it does magically go away. This is
1141 because nothing links to C -- whereas with the D-X-Y tree, D links to X
1142 and Y, and X and Y each link back to D. Note that calling
1143 C->delete_tree is harmless -- after all, a tree of only one node is
1144 still a tree.
1145 So, this is a surefire way of getting rid of all $node's children and
1147 freeing up the memory associated with them and their descendants:
1148 foreach my $it ($node->clear_daughters) { $it->delete_tree }
1150 Just be sure not to do this:
1152 foreach my $it ($node->daughters) { $it->delete_tree }
1154 $node->clear_daughters;
1155 That's bad; the first call to $_->delete_tree will climb to the root of
1157 $node's tree, and nuke the whole tree, not just the bits under $node.
1158 You might as well have just called $node->delete_tree. (Moreavor, once
1159 $node is dead, you can't call clear_daughters on it, so you'll get an
1160 error there.)
1161
1163 If you find a bug in this library, report it to me as soon as possible,
1164 at the address listed in the MAINTAINER section, below. Please try to
1165 be as specific as possible about how you got the bug to occur.
1166
1168 If you develop a given routine for dealing with trees in some way, and
1169 use it a lot, then if you think it'd be of use to anyone else, do email
1170 me about it; it might be helpful to others to include that routine, or
1171 something based on it, in a later version of this module.
1172 It's occurred to me that you might like to (and might yourself develop
1174 routines to) draw trees in something other than ASCII art. If you do
1175 so -- say, for PostScript output, or for output interpretable by some
1176 external plotting program -- I'd be most interested in the results.
1177
1179 This module uses "strict", but I never wrote it with -w warnings in
1180 mind -- so if you use -w, do not be surprised if you see complaints
1181 from the guts of DAG_Node. As long as there is no way to turn off -w
1182 for a given module (instead of having to do it in every single
1183 subroutine with a "local $^W"), I'm not going to change this. However,
1184 I do, at points, get bursts of ambition, and I try to fix code in
1185 DAG_Node that generates warnings, as I come across them -- which is
1186 only occasionally. Feel free to email me any patches for any such
1187 fixes you come up with, tho.
1188 Currently I don't assume (or enforce) anything about the class
1190 membership of nodes being manipulated, other than by testing whether
1191 each one provides a method "is_node", a la:
1192 die "Not a node!!!" unless UNIVERSAL::can($node, "is_node");
1194 So, as far as I'm concerned, a given tree's nodes are free to belong to
1196 different classes, just so long as they provide/inherit "is_node", the
1197 few methods that this class relies on to navigate the tree, and have
1198 the same internal object structure, or a superset of it. Presumably
1199 this would be the case for any object belonging to a class derived from
1200 "Tree::DAG_Node", or belonging to "Tree::DAG_Node" itself.
1201 When routines in this class access a node's "mother" attribute, or its
1203 "daughters" attribute, they (generally) do so directly (via
1204 $node->{'mother'}, etc.), for sake of efficiency. But classes derived
1205 from this class should probably do this instead thru a method (via
1206 $node->mother, etc.), for sake of portability, abstraction, and general
1207 goodness.
1208 However, no routines in this class (aside from, necessarily, "_init",
1210 "_init_name", and "name") access the "name" attribute directly;
1211 routines (like the various tree draw/dump methods) get the "name" value
1212 thru a call to $obj->name(). So if you want the object's name to not
1213 be a real attribute, but instead have it derived dynamically from some
1214 feature of the object (say, based on some of its other attributes, or
1215 based on its address), you can to override the "name" method, without
1216 causing problems. (Be sure to consider the case of $obj->name as a
1217 write method, as it's used in "lol_to_tree" and "random_network".)
1218
1220 HTML::Element
1221 Wirth, Niklaus. 1976. Algorithms + Data Structures = Programs
1223 Prentice-Hall, Englewood Cliffs, NJ.
1224 Knuth, Donald Ervin. 1997. Art of Computer Programming, Volume 1,
1226 Third Edition: Fundamental Algorithms. Addison-Wesley, Reading, MA.
1227 Wirth's classic, currently and lamentably out of print, has a good
1229 section on trees. I find it clearer than Knuth's (if not quite as
1230 encyclopedic), probably because Wirth's example code is in a block-
1231 structured high-level language (basically Pascal), instead of in
1232 assembler (MIX).
1233 Until some kind publisher brings out a new printing of Wirth's book,
1235 try poking around used bookstores (or "www.abebooks.com") for a copy.
1236 I think it was also republished in the 1980s under the title Algorithms
1237 and Data Structures, and in a German edition called Algorithmen und
1238 Datenstrukturen. (That is, I'm sure books by Knuth were published
1239 under those titles, but I'm assuming that they're just later
1240 printings/editions of Algorithms + Data Structures = Programs.)
1241
1243 David Hand, "<cogent@cpan.org>"
1244
1246 Sean M. Burke, "<sburke@cpan.org>"
1247
1249 Copyright 1998-2001, 2004, 2007 by Sean M. Burke and David Hand.
1250 This program is free software; you can redistribute it and/or modify it
1252 under the same terms as Perl itself.
1253 This program is distributed in the hope that it will be useful, but
1255 without any warranty; without even the implied warranty of
1256 merchantability or fitness for a particular purpose.
1257perl v5.10.1 2007-12-09 Tree::DAG_Node(3)