1 .\" Automatically generated by Pod::Man 2.22 (Pod::Simple 3.10)
4 .\" ========================================================================
5 .de Sp \" Vertical space (when we can't use .PP)
9 .de Vb \" Begin verbatim text
14 .de Ve \" End verbatim text
18 .\" Set up some character translations and predefined strings. \*(-- will
19 .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
20 .\" double quote, and \*(R" will give a right double quote. \*(C+ will
21 .\" give a nicer C++. Capital omega is used to do unbreakable dashes and
22 .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff,
23 .\" nothing in troff, for use with C<>.
25 .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
29 . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
30 . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch
43 .\" Escape single quotes in literal strings from groff's Unicode transform.
47 .\" If the F register is turned on, we'll generate index entries on stderr for
48 .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
49 .\" entries marked with X<> in POD. Of course, you'll have to process the
50 .\" output yourself in some meaningful fashion.
53 . tm Index:\\$1\t\\n%\t"\\$2"
63 .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
64 .\" Fear. Run. Save yourself. No user-serviceable parts.
65 . \" fudge factors for nroff and troff
74 . ds #H ((1u-(\\\\n(.fu%2u))*.13m)
80 . \" simple accents for nroff and troff
90 . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
91 . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
92 . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
93 . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
94 . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
95 . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
97 . \" troff and (daisy-wheel) nroff accents
98 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
99 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
100 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
101 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
102 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
103 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
104 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
105 .ds ae a\h'-(\w'a'u*4/10)'e
106 .ds Ae A\h'-(\w'A'u*4/10)'E
107 . \" corrections for vroff
108 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
109 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
110 . \" for low resolution devices (crt and lpr)
111 .if \n(.H>23 .if \n(.V>19 \
124 .\" ========================================================================
126 .IX Title "Tree::DAG_Node 3"
127 .TH Tree::DAG_Node 3 "2007-12-09" "perl v5.8.7" "User Contributed Perl Documentation"
128 .\" For nroff, turn off justification. Always turn off hyphenation; it makes
129 .\" way too many mistakes in technical documents.
133 Tree::DAG_Node \- (super)class for representing nodes in a tree
135 .IX Header "SYNOPSIS"
136 Using as a base class:
139 \& package Game::Tree::Node; # or whatever you\*(Aqre doing
140 \& use Tree::DAG_Node;
141 \& @ISA = qw(Tree::DAG_Node);
142 \& ...your own methods overriding/extending
143 \& the methods in Tree::DAG_Node...
146 Using as a class of its own:
149 \& use Tree::DAG_Node;
150 \& my $root = Tree::DAG_Node\->new();
151 \& $root\->name("I\*(Aqm the tops");
152 \& my $new_daughter = $root\->new_daughter;
153 \& $new_daughter\->name("More");
157 .IX Header "DESCRIPTION"
158 This class encapsulates/makes/manipulates objects that represent nodes
159 in a tree structure. The tree structure is not an object itself, but
160 is emergent from the linkages you create between nodes. This class
161 provides the methods for making linkages that can be used to build up
162 a tree, while preventing you from ever making any kinds of linkages
163 which are not allowed in a tree (such as having a node be its own
164 mother or ancestor, or having a node have two mothers).
166 This is what I mean by a \*(L"tree structure\*(R", a bit redundantly stated:
168 * A tree is a special case of an acyclic directed graph.
170 * A tree is a network of nodes where there's exactly one root
171 node (i.e., 'the top'), and the only primary relationship between nodes
172 is the mother-daugher relationship.
174 * No node can be its own mother, or its mother's mother, etc.
176 * Each node in the tree has exactly one \*(L"parent\*(R" (node in the \*(L"up\*(R"
177 direction) \*(-- except the root, which is parentless.
179 * Each node can have any number (0 to any finite number) of daughter
180 nodes. A given node's daughter nodes constitute an \fIordered\fR list.
181 (However, you are free to consider this ordering irrelevant.
182 Some applications do need daughters to be ordered, so I chose to
183 consider this the general case.)
185 * A node can appear in only one tree, and only once in that tree.
186 Notably (notable because it doesn't follow from the two above points),
187 a node cannot appear twice in its mother's daughter list.
189 * In other words, there's an idea of up (toward the root) versus
190 down (away from the root), and left (i.e., toward the start (index 0)
191 of a given node's daughter list) versus right (toward the end of a
192 given node's daughter list).
194 Trees as described above have various applications, among them:
195 representing syntactic constituency, in formal linguistics;
196 representing contingencies in a game tree; representing abstract
197 syntax in the parsing of any computer language \*(-- whether in
198 expression trees for programming languages, or constituency in the
199 parse of a markup language document. (Some of these might not use the
200 fact that daughters are ordered.)
202 (Note: B\-Trees are a very special case of the above kinds of trees,
203 and are best treated with their own class. Check \s-1CPAN\s0 for modules
204 encapsulating B\-Trees; or if you actually want a database, and for
205 some reason ended up looking here, go look at AnyDBM_File.)
207 Many base classes are not usable except as such \*(-- but Tree::DAG_Node
208 can be used as a normal class. You can go ahead and say:
211 \& use Tree::DAG_Node;
212 \& my $root = Tree::DAG_Node\->new();
213 \& $root\->name("I\*(Aqm the tops");
214 \& $new_daughter = Tree::DAG_Node\->new();
215 \& $new_daughter\->name("More");
216 \& $root\->add_daughter($new_daughter);
219 and so on, constructing and linking objects from Tree::DAG_Node and
220 making useful tree structures out of them.
221 .SH "A NOTE TO THE READER"
222 .IX Header "A NOTE TO THE READER"
223 This class is big and provides lots of methods. If your problem is
224 simple (say, just representing a simple parse tree), this class might
225 seem like using an atomic sledgehammer to swat a fly. But the
226 complexity of this module's bells and whistles shouldn't detract from
227 the efficiency of using this class for a simple purpose. In fact, I'd
228 be very surprised if any one user ever had use for more that even a
229 third of the methods in this class. And remember: an atomic
230 sledgehammer \fBwill\fR kill that fly.
231 .SH "OBJECT CONTENTS"
232 .IX Header "OBJECT CONTENTS"
233 Implementationally, each node in a tree is an object, in the sense of
234 being an arbitrarily complex data structure that belongs to a class
235 (presumably Tree::DAG_Node, or ones derived from it) that provides
238 The attributes of a node-object are:
239 .IP "mother \*(-- this node's mother. undef if this is a root." 4
240 .IX Item "mother this node's mother. undef if this is a root."
242 .IP "daughters \*(-- the (possibly empty) list of daughters of this node." 4
243 .IX Item "daughters the (possibly empty) list of daughters of this node."
244 .IP "name \*(-- the name for this node." 4
245 .IX Item "name the name for this node."
247 Need not be unique, or even printable. This is printed in some of the
248 various dumper methods, but it's up to you if you don't put anything
249 meaningful or printable here.
250 .IP "attributes \*(-- whatever the user wants to use it for." 4
251 .IX Item "attributes whatever the user wants to use it for."
252 Presumably a hashref to whatever other attributes the user wants to
253 store without risk of colliding with the object's real attributes.
254 (Example usage: attributes to an \s-1SGML\s0 tag \*(-- you definitely wouldn't
255 want the existence of a \*(L"mother=foo\*(R" pair in such a tag to collide with
256 a node object's 'mother' attribute.)
258 Aside from (by default) initializing it to {}, and having the access
259 method called \*(L"attributes\*(R" (described a ways below), I don't do
260 anything with the \*(L"attributes\*(R" in this module. I basically intended
261 this so that users who don't want/need to bother deriving a class
262 from Tree::DAG_Node, could still attach whatever data they wanted in a
265 \&\*(L"mother\*(R" and \*(L"daughters\*(R" are attributes that relate to linkage \*(-- they
266 are never written to directly, but are changed as appropriate by the
267 \&\*(L"linkage methods\*(R", discussed below.
269 The other two (and whatever others you may add in derived classes) are
270 simply accessed thru the same-named methods, discussed further below.
271 .SS "\s-1ABOUT\s0 \s-1THE\s0 \s-1DOCUMENTED\s0 \s-1INTERFACE\s0"
272 .IX Subsection "ABOUT THE DOCUMENTED INTERFACE"
273 Stick to the documented interface (and comments in the source \*(--
274 especially ones saying \*(L"undocumented!\*(R" and/or \*(L"disfavored!\*(R" \*(-- do not
275 count as documentation!), and don't rely on any behavior that's not in
276 the documented interface.
278 Specifically, unless the documentation for a particular method says
279 \&\*(L"this method returns thus-and-such a value\*(R", then you should not rely on
280 it returning anything meaningful.
282 A \fIpassing\fR acquintance with at least the broader details of the source
283 code for this class is assumed for anyone using this class as a base
284 class \*(-- especially if you're overriding existing methods, and
285 \&\fBdefinitely\fR if you're overriding linkage methods.
286 .SH "MAIN CONSTRUCTOR, AND INITIALIZER"
287 .IX Header "MAIN CONSTRUCTOR, AND INITIALIZER"
288 .IP "the constructor \s-1CLASS\-\s0>\fInew()\fR or \s-1CLASS\-\s0>new({...options...})" 4
289 .IX Item "the constructor CLASS->new() or CLASS->new({...options...})"
290 This creates a new node object, calls \f(CW$object\fR\->_init({...options...})
291 to provide it sane defaults (like: undef name, undef mother, no
292 daughters, 'attributes' setting of a new empty hashref), and returns
293 the object created. (If you just said \*(L"\s-1CLASS\-\s0>\fInew()\fR\*(R" or \*(L"\s-1CLASS\-\s0>new\*(R",
294 then it pretends you called \*(L"\s-1CLASS\-\s0>new({})\*(R".)
296 Currently no options for putting in {...options...} are part
297 of the documented interface, but the options is here in case
298 you want to add such behavior in a derived class.
300 Read on if you plan on using Tree::DAG_New as a base class.
301 (Otherwise feel free to skip to the description of _init.)
303 There are, in my mind, two ways to do object construction:
305 Way 1: create an object, knowing that it'll have certain uninteresting
306 sane default values, and then call methods to change those values to
307 what you want. Example:
310 \& $node = Tree::DAG_Node\->new;
311 \& $node\->name(\*(AqSupahnode!\*(Aq);
312 \& $root\->add_daughter($node);
313 \& $node\->add_daughters(@some_others)
316 Way 2: be able to specify some/most/all the object's attributes in
317 the call to the constructor. Something like:
320 \& $node = Tree::DAG_Node\->new({
321 \& name => \*(AqSupahnode!\*(Aq,
323 \& daughters => \e@some_others
327 After some deliberation, I've decided that the second way is a Bad
328 Thing. First off, it is \fBnot\fR markedly more concise than the first
329 way. Second off, it often requires subtly different syntax (e.g.,
330 \&\e@some_others vs \f(CW@some_others\fR). It just complicates things for the
331 programmer and the user, without making either appreciably happier.
333 (This is not to say that options in general for a constructor are bad
334 \&\*(-- \f(CW\*(C`random_network\*(C'\fR, discussed far below, necessarily takes options.
335 But note that those are not options for the default values of
338 Anyway, if you use Tree::DAG_Node as a superclass, and you add
339 attributes that need to be initialized, what you need to do is provide
340 an _init method that calls \f(CW$this\fR\->SUPER::_init($options) to use its
341 superclass's _init method, and then initializes the new attributes:
345 \& my($this, $options) = @_[0,1];
346 \& $this\->SUPER::_init($options); # call my superclass\*(Aqs _init to
347 \& # init all the attributes I\*(Aqm inheriting
349 \& # Now init /my/ new attributes:
350 \& $this\->{\*(Aqamigos\*(Aq} = []; # for example
354 \&...or, as I prefer when I'm being a neat freak:
358 \& my($this, $options) = @_[0,1];
359 \& $this\->SUPER::_init($options);
361 \& $this\->_init_amigos($options);
364 \& sub _init_amigos {
366 \& # Or my($this,$options) = @_[0,1]; if I\*(Aqm using $options
367 \& $this\->{\*(Aqamigos\*(Aq} = [];
371 In other words, I like to have each attribute initialized thru a
372 method named _init_[attribute], which should expect the object as
373 \&\f(CW$_\fR[0] and the the options hashref (or {} if none was given) as \f(CW$_\fR[1].
374 If you insist on having your _init recognize options for setting
375 attributes, you might as well have them dealt with by the appropriate
376 _init_[attribute] method, like this:
380 \& my($this, $options) = @_[0,1];
381 \& $this\->SUPER::_init($options);
383 \& $this\->_init_amigos($options);
386 \& sub _init_amigos {
387 \& my($this,$options) = @_[0,1]; # I need options this time
388 \& $this\->{\*(Aqamigos\*(Aq} = [];
389 \& $this\->amigos(@{$options\->{\*(Aqamigos\*(Aq}}) if $options\->{\*(Aqamigos\*(Aq};
393 All this bookkeeping looks silly with just one new attribute in a
394 class derived straight from Tree::DAG_Node, but if there's lots of new
395 attributes running around, and if you're deriving from a class derived
396 from a class derived from Tree::DAG_Node, then tidy
397 stratification/modularization like this can keep you sane.
398 .ie n .IP "the constructor $obj\->\fInew()\fR or $obj\->new({...options...})" 4
399 .el .IP "the constructor \f(CW$obj\fR\->\fInew()\fR or \f(CW$obj\fR\->new({...options...})" 4
400 .IX Item "the constructor $obj->new() or $obj->new({...options...})"
401 Just another way to get at the \f(CW\*(C`new\*(C'\fR method. This \fBdoes not copy\fR
402 \&\f(CW$obj\fR, but merely constructs a new object of the same class as it.
403 Saves you the bother of going \f(CW$class\fR = ref \f(CW$obj\fR; \f(CW$obj2\fR = \f(CW$class\fR\->new;
404 .ie n .IP "the method $node\->_init({...options...})" 4
405 .el .IP "the method \f(CW$node\fR\->_init({...options...})" 4
406 .IX Item "the method $node->_init({...options...})"
407 Initialize the object's attribute values. See the discussion above.
408 Presumably this should be called only by the guts of the \f(CW\*(C`new\*(C'\fR
409 constructor \*(-- never by the end user.
411 Currently there are no documented options for putting in
412 {...options...}, but (in case you want to disregard the above rant)
413 the option exists for you to use {...options...} for something useful
416 Please see the source for more information.
417 .ie n .IP "see also (below) the constructors ""new_daughter"" and ""new_daughter_left""" 4
418 .el .IP "see also (below) the constructors ``new_daughter'' and ``new_daughter_left''" 4
419 .IX Item "see also (below) the constructors new_daughter and new_daughter_left"
420 .SH "LINKAGE-RELATED METHODS"
421 .IX Header "LINKAGE-RELATED METHODS"
423 .ie n .IP "$node\->daughters" 4
424 .el .IP "\f(CW$node\fR\->daughters" 4
425 .IX Item "$node->daughters"
427 This returns the (possibly empty) list of daughters for \f(CW$node\fR.
428 .ie n .IP "$node\->mother" 4
429 .el .IP "\f(CW$node\fR\->mother" 4
430 .IX Item "$node->mother"
431 This returns what node is \f(CW$node\fR's mother. This is undef if \f(CW$node\fR has
432 no mother \*(-- i.e., if it is a root.
433 .ie n .IP "$mother\->add_daughters( \s-1LIST\s0 )" 4
434 .el .IP "\f(CW$mother\fR\->add_daughters( \s-1LIST\s0 )" 4
435 .IX Item "$mother->add_daughters( LIST )"
436 This method adds the node objects in \s-1LIST\s0 to the (right) end of
437 \&\f(CW$mother\fR's \f(CW\*(C`daughter\*(C'\fR list. Making a node N1 the daughter of another
438 node N2 also means that N1's \f(CW\*(C`mother\*(C'\fR attribute is \*(L"automatically\*(R" set
439 to N2; it also means that N1 stops being anything else's daughter as
440 it becomes N2's daughter.
442 If you try to make a node its own mother, a fatal error results. If
443 you try to take one of a a node N1's ancestors and make it also a
444 daughter of N1, a fatal error results. A fatal error results if
445 anything in \s-1LIST\s0 isn't a node object.
447 If you try to make N1 a daughter of N2, but it's \fBalready\fR a daughter
448 of N2, then this is a no-operation \*(-- it won't move such nodes to the
449 end of the list or anything; it just skips doing anything with them.
450 .ie n .IP "$node\->add_daughter( \s-1LIST\s0 )" 4
451 .el .IP "\f(CW$node\fR\->add_daughter( \s-1LIST\s0 )" 4
452 .IX Item "$node->add_daughter( LIST )"
453 An exact synonym for \f(CW$node\fR\->add_daughters(\s-1LIST\s0)
454 .ie n .IP "$mother\->add_daughters_left( \s-1LIST\s0 )" 4
455 .el .IP "\f(CW$mother\fR\->add_daughters_left( \s-1LIST\s0 )" 4
456 .IX Item "$mother->add_daughters_left( LIST )"
457 This method is just like \f(CW\*(C`add_daughters\*(C'\fR, except that it adds the
458 node objects in \s-1LIST\s0 to the (left) beginning of \f(CW$mother\fR's daughter
459 list, instead of the (right) end of it.
460 .ie n .IP "$node\->add_daughter_left( \s-1LIST\s0 )" 4
461 .el .IP "\f(CW$node\fR\->add_daughter_left( \s-1LIST\s0 )" 4
462 .IX Item "$node->add_daughter_left( LIST )"
463 An exact synonym for \f(CW$node\fR\->add_daughters_left( \s-1LIST\s0 )
466 The above link-making methods perform basically an \f(CW\*(C`unshift\*(C'\fR or
467 \&\f(CW\*(C`push\*(C'\fR on the mother node's daughter list. To get the full range of
468 list-handling functionality, copy the daughter list, and change it,
469 and then call \f(CW\*(C`set_daughters\*(C'\fR on the result:
472 \& @them = $mother\->daughters;
473 \& @removed = splice(@them, 0,2, @new_nodes);
474 \& $mother\->set_daughters(@them);
477 Or consider a structure like:
480 \& $mother\->set_daughters(
481 \& grep($_\->name =~ /NP/ ,
482 \& $mother\->daughters
486 .ie n .IP "the constructor $daughter = $mother\->new_daughter, or" 4
487 .el .IP "the constructor \f(CW$daughter\fR = \f(CW$mother\fR\->new_daughter, or" 4
488 .IX Item "the constructor $daughter = $mother->new_daughter, or"
490 .ie n .IP "the constructor $daughter = $mother\->new_daughter({...options...})" 4
491 .el .IP "the constructor \f(CW$daughter\fR = \f(CW$mother\fR\->new_daughter({...options...})" 4
492 .IX Item "the constructor $daughter = $mother->new_daughter({...options...})"
494 This \fBconstructs\fR a \fBnew\fR node (of the same class as \f(CW$mother\fR), and
495 adds it to the (right) end of the daughter list of \f(CW$mother\fR. This is
496 essentially the same as going
499 \& $daughter = $mother\->new;
500 \& $mother\->add_daughter($daughter);
503 but is rather more efficient because (since \f(CW$daughter\fR is guaranteed new
504 and isn't linked to/from anything), it doesn't have to check that
505 \&\f(CW$daughter\fR isn't an ancestor of \f(CW$mother\fR, isn't already daughter to a
506 mother it needs to be unlinked from, isn't already in \f(CW$mother\fR's
509 As you'd expect for a constructor, it returns the node-object created.
510 .ie n .IP "the constructor $mother\->new_daughter_left, or" 4
511 .el .IP "the constructor \f(CW$mother\fR\->new_daughter_left, or" 4
512 .IX Item "the constructor $mother->new_daughter_left, or"
514 .ie n .IP "$mother\->new_daughter_left({...options...})" 4
515 .el .IP "\f(CW$mother\fR\->new_daughter_left({...options...})" 4
516 .IX Item "$mother->new_daughter_left({...options...})"
518 This is just like \f(CW$mother\fR\->new_daughter, but adds the new daughter
519 to the left (start) of \f(CW$mother\fR's daughter list.
520 .ie n .IP "$mother\->remove_daughters( \s-1LIST\s0 )" 4
521 .el .IP "\f(CW$mother\fR\->remove_daughters( \s-1LIST\s0 )" 4
522 .IX Item "$mother->remove_daughters( LIST )"
523 This removes the nodes listed in \s-1LIST\s0 from \f(CW$mother\fR's daughter list.
524 This is a no-operation if \s-1LIST\s0 is empty. If there are things in \s-1LIST\s0
525 that aren't a current daughter of \f(CW$mother\fR, they are ignored.
527 Not to be confused with \f(CW$mother\fR\->clear_daughters.
528 .ie n .IP "$node\->remove_daughter( \s-1LIST\s0 )" 4
529 .el .IP "\f(CW$node\fR\->remove_daughter( \s-1LIST\s0 )" 4
530 .IX Item "$node->remove_daughter( LIST )"
531 An exact synonym for \f(CW$node\fR\->remove_daughters( \s-1LIST\s0 )
532 .ie n .IP "$node\->unlink_from_mother" 4
533 .el .IP "\f(CW$node\fR\->unlink_from_mother" 4
534 .IX Item "$node->unlink_from_mother"
535 This removes node from the daughter list of its mother. If it has no
536 mother, this is a no-operation.
538 Returns the mother unlinked from (if any).
539 .ie n .IP "$mother\->clear_daughters" 4
540 .el .IP "\f(CW$mother\fR\->clear_daughters" 4
541 .IX Item "$mother->clear_daughters"
542 This unlinks all \f(CW$mother\fR's daughters.
543 Returns the the list of what used to be \f(CW$mother\fR's daughters.
545 Not to be confused with \f(CW$mother\fR\->remove_daughters( \s-1LIST\s0 ).
546 .ie n .IP "$mother\->set_daughters( \s-1LIST\s0 )" 4
547 .el .IP "\f(CW$mother\fR\->set_daughters( \s-1LIST\s0 )" 4
548 .IX Item "$mother->set_daughters( LIST )"
549 This unlinks all \f(CW$mother\fR's daughters, and replaces them with the
550 daughters in \s-1LIST\s0.
552 Currently implemented as just \f(CW$mother\fR\->clear_daughters followed by
553 \&\f(CW$mother\fR\->add_daughters( \s-1LIST\s0 ).
554 .ie n .IP "$node\->replace_with( \s-1LIST\s0 )" 4
555 .el .IP "\f(CW$node\fR\->replace_with( \s-1LIST\s0 )" 4
556 .IX Item "$node->replace_with( LIST )"
557 This replaces \f(CW$node\fR in its mother's daughter list, by unlinking \f(CW$node\fR
558 and replacing it with the items in \s-1LIST\s0. This returns a list consisting
559 of \f(CW$node\fR followed by \s-1LIST\s0, i.e., the nodes that replaced it.
561 \&\s-1LIST\s0 can include \f(CW$node\fR itself (presumably at most once). \s-1LIST\s0 can
562 also be empty-list. However, if any items in \s-1LIST\s0 are sisters to
563 \&\f(CW$node\fR, they are ignored, and are not in the copy of \s-1LIST\s0 passed as the
566 As you might expect for any linking operation, the items in \s-1LIST\s0
567 cannot be \f(CW$node\fR's mother, or any ancestor to it; and items in \s-1LIST\s0 are,
568 of course, unlinked from their mothers (if they have any) as they're
569 linked to \f(CW$node\fR's mother.
571 (In the special (and bizarre) case where \f(CW$node\fR is root, this simply calls
572 \&\f(CW$this\fR\->unlink_from_mother on all the items in \s-1LIST\s0, making them roots of
575 Note that the daughter-list of \f(CW$node\fR is not necessarily affected; nor
576 are the daughter-lists of the items in \s-1LIST\s0. I mention this in case you
577 think replace_with switches one node for another, with respect to its
578 mother list \fBand\fR its daughter list, leaving the rest of the tree
579 unchanged. If that's what you want, replacing \f(CW$Old\fR with \f(CW$New\fR, then you
583 \& $New\->set_daughters($Old\->clear_daughters);
584 \& $Old\->replace_with($New);
587 (I can't say \f(CW$node\fR's and LIST\-items' daughter lists are \fBnever\fR
588 affected my replace_with \*(-- they can be affected in this case:
591 \& $N1 = ($node\->daughters)[0]; # first daughter of $node
592 \& $N2 = ($N1\->daughters)[0]; # first daughter of $N1;
593 \& $N3 = Tree::DAG_Node\->random_network; # or whatever
594 \& $node\->replace_with($N1, $N2, $N3);
597 As a side affect of attaching \f(CW$N1\fR and \f(CW$N2\fR to \f(CW$node\fR's mother, they're
598 unlinked from their parents ($node, and \f(CW$N1\fR, replectively).
599 But N3's daughter list is unaffected.
601 In other words, this method does what it has to, as you'd expect it
603 .ie n .IP "$node\->replace_with_daughters" 4
604 .el .IP "\f(CW$node\fR\->replace_with_daughters" 4
605 .IX Item "$node->replace_with_daughters"
606 This replaces \f(CW$node\fR in its mother's daughter list, by unlinking \f(CW$node\fR
607 and replacing it with its daughters. In other words, \f(CW$node\fR becomes
608 motherless and daughterless as its daughters move up and take its place.
609 This returns a list consisting of \f(CW$node\fR followed by the nodes that were
612 In the special (and bizarre) case where \f(CW$node\fR is root, this simply
613 unlinks its daughters from it, making them roots of their own trees.
615 Effectively the same as \f(CW$node\fR\->replace_with($node\->daughters), but more
616 efficient, since less checking has to be done. (And I also think
617 \&\f(CW$node\fR\->replace_with_daughters is a more common operation in
618 tree-wrangling than \f(CW$node\fR\->replace_with(\s-1LIST\s0), so deserves a named
619 method of its own, but that's just me.)
620 .ie n .IP "$node\->add_left_sisters( \s-1LIST\s0 )" 4
621 .el .IP "\f(CW$node\fR\->add_left_sisters( \s-1LIST\s0 )" 4
622 .IX Item "$node->add_left_sisters( LIST )"
623 This adds the elements in \s-1LIST\s0 (in that order) as immediate left sisters of
624 \&\f(CW$node\fR. In other words, given that B's mother's daughter-list is (A,B,C,D),
625 calling B\->add_left_sisters(X,Y) makes B's mother's daughter-list
628 If \s-1LIST\s0 is empty, this is a no-op, and returns empty-list.
630 This is basically implemented as a call to \f(CW$node\fR\->replace_with(\s-1LIST\s0,
631 \&\f(CW$node\fR), and so all replace_with's limitations and caveats apply.
633 The return value of \f(CW$node\fR\->add_left_sisters( \s-1LIST\s0 ) is the elements of
634 \&\s-1LIST\s0 that got added, as returned by replace_with \*(-- minus the copies
635 of \f(CW$node\fR you'd get from a straight call to \f(CW$node\fR\->replace_with(\s-1LIST\s0,
637 .ie n .IP "$node\->add_left_sister( \s-1LIST\s0 )" 4
638 .el .IP "\f(CW$node\fR\->add_left_sister( \s-1LIST\s0 )" 4
639 .IX Item "$node->add_left_sister( LIST )"
640 An exact synonym for \f(CW$node\fR\->add_left_sisters(\s-1LIST\s0)
641 .ie n .IP "$node\->add_right_sisters( \s-1LIST\s0 )" 4
642 .el .IP "\f(CW$node\fR\->add_right_sisters( \s-1LIST\s0 )" 4
643 .IX Item "$node->add_right_sisters( LIST )"
644 Just like add_left_sisters (which see), except that the the elements
645 in \s-1LIST\s0 (in that order) as immediate \fBright\fR sisters of \f(CW$node\fR;
647 In other words, given that B's mother's daughter-list is (A,B,C,D),
648 calling B\->add_right_sisters(X,Y) makes B's mother's daughter-list
650 .ie n .IP "$node\->add_right_sister( \s-1LIST\s0 )" 4
651 .el .IP "\f(CW$node\fR\->add_right_sister( \s-1LIST\s0 )" 4
652 .IX Item "$node->add_right_sister( LIST )"
653 An exact synonym for \f(CW$node\fR\->add_right_sisters(\s-1LIST\s0)
654 .SH "OTHER ATTRIBUTE METHODS"
655 .IX Header "OTHER ATTRIBUTE METHODS"
656 .ie n .IP "$node\->name or $node\->name(\s-1SCALAR\s0)" 4
657 .el .IP "\f(CW$node\fR\->name or \f(CW$node\fR\->name(\s-1SCALAR\s0)" 4
658 .IX Item "$node->name or $node->name(SCALAR)"
659 In the first form, returns the value of the node object's \*(L"name\*(R"
660 attribute. In the second form, sets it to the value of \s-1SCALAR\s0.
661 .ie n .IP "$node\->attributes or $node\->attributes(\s-1SCALAR\s0)" 4
662 .el .IP "\f(CW$node\fR\->attributes or \f(CW$node\fR\->attributes(\s-1SCALAR\s0)" 4
663 .IX Item "$node->attributes or $node->attributes(SCALAR)"
664 In the first form, returns the value of the node object's \*(L"attributes\*(R"
665 attribute. In the second form, sets it to the value of \s-1SCALAR\s0. I
666 intend this to be used to store a reference to a (presumably
667 anonymous) hash the user can use to store whatever attributes he
668 doesn't want to have to store as object attributes. In this case, you
669 needn't ever set the value of this. (_init has already initialized it
670 to {}.) Instead you can just do...
673 \& $node\->attributes\->{\*(Aqfoo\*(Aq} = \*(Aqbar\*(Aq;
676 \&...to write foo => bar.
677 .ie n .IP "$node\->attribute or $node\->attribute(\s-1SCALAR\s0)" 4
678 .el .IP "\f(CW$node\fR\->attribute or \f(CW$node\fR\->attribute(\s-1SCALAR\s0)" 4
679 .IX Item "$node->attribute or $node->attribute(SCALAR)"
680 An exact synonym for \f(CW$node\fR\->attributes or \f(CW$node\fR\->attributes(\s-1SCALAR\s0)
681 .SH "OTHER METHODS TO DO WITH RELATIONSHIPS"
682 .IX Header "OTHER METHODS TO DO WITH RELATIONSHIPS"
683 .ie n .IP "$node\->is_node" 4
684 .el .IP "\f(CW$node\fR\->is_node" 4
685 .IX Item "$node->is_node"
686 This always returns true. More pertinently, \f(CW$object\fR\->can('is_node')
687 is true (regardless of what \f(CW\*(C`is_node\*(C'\fR would do if called) for objects
688 belonging to this class or for any class derived from it.
689 .ie n .IP "$node\->ancestors" 4
690 .el .IP "\f(CW$node\fR\->ancestors" 4
691 .IX Item "$node->ancestors"
692 Returns the list of this node's ancestors, starting with its mother,
693 then grandmother, and ending at the root. It does this by simply
694 following the 'mother' attributes up as far as it can. So if \f(CW$item\fR \s-1IS\s0
695 the root, this returns an empty list.
697 Consider that scalar($node\->ancestors) returns the ply of this node
698 within the tree \*(-- 2 for a granddaughter of the root, etc., and 0 for
700 .ie n .IP "$node\->root" 4
701 .el .IP "\f(CW$node\fR\->root" 4
702 .IX Item "$node->root"
703 Returns the root of whatever tree \f(CW$node\fR is a member of. If \f(CW$node\fR is
704 the root, then the result is \f(CW$node\fR itself.
705 .ie n .IP "$node\->is_daughter_of($node2)" 4
706 .el .IP "\f(CW$node\fR\->is_daughter_of($node2)" 4
707 .IX Item "$node->is_daughter_of($node2)"
708 Returns true iff \f(CW$node\fR is a daughter of \f(CW$node2\fR.
709 Currently implemented as just a test of ($it\->mother eq \f(CW$node2\fR).
710 .ie n .IP "$node\->self_and_descendants" 4
711 .el .IP "\f(CW$node\fR\->self_and_descendants" 4
712 .IX Item "$node->self_and_descendants"
713 Returns a list consisting of itself (as element 0) and all the
714 descendants of \f(CW$node\fR. Returns just itself if \f(CW$node\fR is a
717 (Note that it's spelled \*(L"descendants\*(R", not \*(L"descendents\*(R".)
718 .ie n .IP "$node\->descendants" 4
719 .el .IP "\f(CW$node\fR\->descendants" 4
720 .IX Item "$node->descendants"
721 Returns a list consisting of all the descendants of \f(CW$node\fR. Returns
722 empty-list if \f(CW$node\fR is a terminal_node.
724 (Note that it's spelled \*(L"descendants\*(R", not \*(L"descendents\*(R".)
725 .ie n .IP "$node\->leaves_under" 4
726 .el .IP "\f(CW$node\fR\->leaves_under" 4
727 .IX Item "$node->leaves_under"
728 Returns a list (going left-to-right) of all the leaf nodes under
729 \&\f(CW$node\fR. (\*(L"Leaf nodes\*(R" are also called \*(L"terminal nodes\*(R" \*(-- i.e., nodes
730 that have no daughters.) Returns \f(CW$node\fR in the degenerate case of
731 \&\f(CW$node\fR being a leaf itself.
732 .ie n .IP "$node\->depth_under" 4
733 .el .IP "\f(CW$node\fR\->depth_under" 4
734 .IX Item "$node->depth_under"
735 Returns an integer representing the number of branches between this
736 \&\f(CW$node\fR and the most distant leaf under it. (In other words, this
737 returns the ply of subtree starting of \f(CW$node\fR. Consider
738 scalar($it\->ancestors) if you want the ply of a node within the whole
740 .ie n .IP "$node\->generation" 4
741 .el .IP "\f(CW$node\fR\->generation" 4
742 .IX Item "$node->generation"
743 Returns a list of all nodes (going left-to-right) that are in \f(CW$node\fR's
744 generation \*(-- i.e., that are the some number of nodes down from
745 the root. \f(CW$root\fR\->generation is just \f(CW$root\fR.
747 Of course, \f(CW$node\fR is always in its own generation.
748 .ie n .IP "$node\->generation_under(\s-1NODE2\s0)" 4
749 .el .IP "\f(CW$node\fR\->generation_under(\s-1NODE2\s0)" 4
750 .IX Item "$node->generation_under(NODE2)"
751 Like \f(CW$node\fR\->generation, but returns only the nodes in \f(CW$node\fR's generation
752 that are also descendants of \s-1NODE2\s0 \*(-- in other words,
755 \& @us = $node\->generation_under( $node\->mother\->mother );
758 is all \f(CW$node\fR's first cousins (to borrow yet more kinship terminology) \*(--
759 assuming \f(CW$node\fR does indeed have a grandmother. Actually \*(L"cousins\*(R" isn't
760 quite an apt word, because \f(CW@us\fR ends up including \f(CW$node\fR's siblings and
763 Actually, \f(CW\*(C`generation_under\*(C'\fR is just an alias to \f(CW\*(C`generation\*(C'\fR, but I
767 \& @us = $node\->generation_under($way_upline);
770 is a bit more readable than this:
773 \& @us = $node\->generation($way_upline);
778 \&\f(CW$node\fR\->generation_under($node) returns just \f(CW$node\fR.
780 If you call \f(CW$node\fR\->generation_under($node) but \s-1NODE2\s0 is not \f(CW$node\fR or an
781 ancestor of \f(CW$node\fR, it behaves as if you called just \f(CW$node\fR\->\fIgeneration()\fR.
782 .ie n .IP "$node\->self_and_sisters" 4
783 .el .IP "\f(CW$node\fR\->self_and_sisters" 4
784 .IX Item "$node->self_and_sisters"
785 Returns a list of all nodes (going left-to-right) that have the same
786 mother as \f(CW$node\fR \*(-- including \f(CW$node\fR itself. This is just like
787 \&\f(CW$node\fR\->mother\->daughters, except that that fails where \f(CW$node\fR is root,
788 whereas \f(CW$root\fR\->self_and_siblings, as a special case, returns \f(CW$root\fR.
790 (Contrary to how you may interpret how this method is named, \*(L"self\*(R" is
791 not (necessarily) the first element of what's returned.)
792 .ie n .IP "$node\->sisters" 4
793 .el .IP "\f(CW$node\fR\->sisters" 4
794 .IX Item "$node->sisters"
795 Returns a list of all nodes (going left-to-right) that have the same
796 mother as \f(CW$node\fR \*(-- \fBnot including\fR \f(CW$node\fR itself. If \f(CW$node\fR is root,
797 this returns empty-list.
798 .ie n .IP "$node\->left_sister" 4
799 .el .IP "\f(CW$node\fR\->left_sister" 4
800 .IX Item "$node->left_sister"
801 Returns the node that's the immediate left sister of \f(CW$node\fR. If \f(CW$node\fR
802 is the leftmost (or only) daughter of its mother (or has no mother),
803 then this returns undef.
805 (See also \f(CW$node\fR\->add_left_sisters(\s-1LIST\s0).)
806 .ie n .IP "$node\->left_sisters" 4
807 .el .IP "\f(CW$node\fR\->left_sisters" 4
808 .IX Item "$node->left_sisters"
809 Returns a list of nodes that're sisters to the left of \f(CW$node\fR. If
810 \&\f(CW$node\fR is the leftmost (or only) daughter of its mother (or has no
811 mother), then this returns an empty list.
813 (See also \f(CW$node\fR\->add_left_sisters(\s-1LIST\s0).)
814 .ie n .IP "$node\->right_sister" 4
815 .el .IP "\f(CW$node\fR\->right_sister" 4
816 .IX Item "$node->right_sister"
817 Returns the node that's the immediate right sister of \f(CW$node\fR. If \f(CW$node\fR
818 is the rightmost (or only) daughter of its mother (or has no mother),
819 then this returns undef.
821 (See also \f(CW$node\fR\->add_right_sisters(\s-1LIST\s0).)
822 .ie n .IP "$node\->right_sisters" 4
823 .el .IP "\f(CW$node\fR\->right_sisters" 4
824 .IX Item "$node->right_sisters"
825 Returns a list of nodes that're sisters to the right of \f(CW$node\fR. If
826 \&\f(CW$node\fR is the rightmost (or only) daughter of its mother (or has no
827 mother), then this returns an empty list.
829 (See also \f(CW$node\fR\->add_right_sisters(\s-1LIST\s0).)
830 .ie n .IP "$node\->my_daughter_index" 4
831 .el .IP "\f(CW$node\fR\->my_daughter_index" 4
832 .IX Item "$node->my_daughter_index"
833 Returns what index this daughter is, in its mother's \f(CW\*(C`daughter\*(C'\fR list.
834 In other words, if \f(CW$node\fR is ($node\->mother\->daughters)[3], then
835 \&\f(CW$node\fR\->my_daughter_index returns 3.
837 As a special case, returns 0 if \f(CW$node\fR has no mother.
838 .ie n .IP "$node\->address or $anynode\->address(\s-1ADDRESS\s0)" 4
839 .el .IP "\f(CW$node\fR\->address or \f(CW$anynode\fR\->address(\s-1ADDRESS\s0)" 4
840 .IX Item "$node->address or $anynode->address(ADDRESS)"
841 With the first syntax, returns the address of \f(CW$node\fR within its tree,
842 based on its position within the tree. An address is formed by noting
843 the path between the root and \f(CW$node\fR, and concatenating the
844 daughter-indices of the nodes this passes thru (starting with 0 for
845 the root, and ending with \f(CW$node\fR).
847 For example, if to get from node \s-1ROOT\s0 to node \f(CW$node\fR, you pass thru
848 \&\s-1ROOT\s0, A, B, and \f(CW$node\fR, then the address is determined as:
850 * \s-1ROOT\s0's my_daughter_index is 0.
852 * A's my_daughter_index is, suppose, 2. (A is index 2 in \s-1ROOT\s0's
855 * B's my_daughter_index is, suppose, 0. (B is index 0 in A's
858 * \f(CW$node\fR's my_daughter_index is, suppose, 4. ($node is index 4 in
861 The address of the above-described \f(CW$node\fR is, therefore, \*(L"0:2:0:4\*(R".
863 (As a somewhat special case, the address of the root is always \*(L"0\*(R";
864 and since addresses start from the root, all addresses start with a
867 The second syntax, where you provide an address, starts from the root
868 of the tree \f(CW$anynode\fR belongs to, and returns the node corresponding to
869 that address. Returns undef if no node corresponds to that address.
870 Note that this routine may be somewhat liberal in its interpretation
871 of what can constitute an address; i.e., it accepts \*(L"0.2.0.4\*(R", besides
874 Also note that the address of a node in a tree is meaningful only in
875 that tree as currently structured.
877 (Consider how ($address1 cmp \f(CW$address2\fR) may be magically meaningful
878 to you, if you mant to figure out what nodes are to the right of what
880 .ie n .IP "$node\->common(\s-1LIST\s0)" 4
881 .el .IP "\f(CW$node\fR\->common(\s-1LIST\s0)" 4
882 .IX Item "$node->common(LIST)"
883 Returns the lowest node in the tree that is ancestor-or-self to the
884 nodes \f(CW$node\fR and \s-1LIST\s0.
886 If the nodes are far enough apart in the tree, the answer is just the
889 If the nodes aren't all in the same tree, the answer is undef.
891 As a degenerate case, if \s-1LIST\s0 is empty, returns \f(CW$node\fR.
892 .ie n .IP "$node\->common_ancestor(\s-1LIST\s0)" 4
893 .el .IP "\f(CW$node\fR\->common_ancestor(\s-1LIST\s0)" 4
894 .IX Item "$node->common_ancestor(LIST)"
895 Returns the lowest node that is ancestor to all the nodes given (in
896 nodes \f(CW$node\fR and \s-1LIST\s0). In other words, it answers the question: \*(L"What
897 node in the tree, as low as possible, is ancestor to the nodes given
898 ($node and \s-1LIST\s0)?\*(R"
900 If the nodes are far enough apart, the answer is just the root \*(--
901 except if any of the nodes are the root itself, in which case the
902 answer is undef (since the root has no ancestor).
904 If the nodes aren't all in the same tree, the answer is undef.
906 As a degenerate case, if \s-1LIST\s0 is empty, returns \f(CW$node\fR's mother;
907 that'll be undef if \f(CW$node\fR is root.
908 .SH "YET MORE METHODS"
909 .IX Header "YET MORE METHODS"
910 .ie n .IP "$node\->walk_down({ callback => \e&foo, callbackback => \e&foo, ... })" 4
911 .el .IP "\f(CW$node\fR\->walk_down({ callback => \e&foo, callbackback => \e&foo, ... })" 4
912 .IX Item "$node->walk_down({ callback => &foo, callbackback => &foo, ... })"
913 Performs a depth-first traversal of the structure at and under \f(CW$node\fR.
914 What it does at each node depends on the value of the options hashref,
915 which you must provide. There are three options, \*(L"callback\*(R" and
916 \&\*(L"callbackback\*(R" (at least one of which must be defined, as a sub
917 reference), and \*(L"_depth\*(R". This is what \f(CW\*(C`walk_down\*(C'\fR does, in
920 * Start at the \f(CW$node\fR given.
922 * If there's a \f(CW\*(C`callback\*(C'\fR, call it with \f(CW$node\fR as the first argument,
923 and the options hashref as the second argument (which contains the
924 potentially useful \f(CW\*(C`_depth\*(C'\fR, remember). This function must return
925 true or false \*(-- if false, it will block the next step:
927 * If \f(CW$node\fR has any daughter nodes, increment \f(CW\*(C`_depth\*(C'\fR, and call
928 \&\f(CW$daughter\fR\->walk_down(options_hashref) for each daughter (in order, of
929 course), where options_hashref is the same hashref it was called with.
930 When this returns, decrements \f(CW\*(C`_depth\*(C'\fR.
932 * If there's a \f(CW\*(C`callbackback\*(C'\fR, call just it as with \f(CW\*(C`callback\*(C'\fR (but
933 tossing out the return value). Note that \f(CW\*(C`callback\*(C'\fR returning false
934 blocks traversal below \f(CW$node\fR, but doesn't block calling callbackback
935 for \f(CW$node\fR. (Incidentally, in the unlikely case that \f(CW$node\fR has stopped
936 being a node object, \f(CW\*(C`callbackback\*(C'\fR won't get called.)
940 \&\f(CW$node\fR\->walk_down is the way to recursively do things to a tree (if you
941 start at the root) or part of a tree; if what you're doing is best done
942 via pre-pre order traversal, use \f(CW\*(C`callback\*(C'\fR; if what you're doing is
943 best done with post-order traversal, use \f(CW\*(C`callbackback\*(C'\fR.
944 \&\f(CW\*(C`walk_down\*(C'\fR is even the basis for plenty of the methods in this
945 class. See the source code for examples both simple and horrific.
947 Note that if you don't specify \f(CW\*(C`_depth\*(C'\fR, it effectively defaults to
948 0. You should set it to scalar($node\->ancestors) if you want
949 \&\f(CW\*(C`_depth\*(C'\fR to reflect the true depth-in-the-tree for the nodes called,
950 instead of just the depth below \f(CW$node\fR. (If \f(CW$node\fR is the root, there's
951 difference, of course.)
953 And \fBby the way\fR, it's a bad idea to modify the tree from the callback.
954 Unpredictable things may happen. I instead suggest having your callback
955 add to a stack of things that need changing, and then, once \f(CW\*(C`walk_down\*(C'\fR
956 is all finished, changing those nodes from that stack.
958 Note that the existence of \f(CW\*(C`walk_down\*(C'\fR doesn't mean you can't write
959 you own special-use traversers.
960 .ie n .IP "@lines = $node\->dump_names({ ...options... });" 4
961 .el .IP "\f(CW@lines\fR = \f(CW$node\fR\->dump_names({ ...options... });" 4
962 .IX Item "@lines = $node->dump_names({ ...options... });"
963 Dumps, as an indented list, the names of the nodes starting at \f(CW$node\fR,
964 and continuing under it. Options are:
966 * _depth \*(-- A nonnegative number. Indicating the depth to consider
967 \&\f(CW$node\fR as being at (and so the generation under that is that plus one,
968 etc.). Defaults to 0. You may choose to use set _depth =>
969 scalar($node\->ancestors).
971 * tick \*(-- a string to preface each entry with, between the
972 indenting-spacing and the node's name. Defaults to empty-string. You
973 may prefer \*(L"*\*(R" or \*(L"\-> \*(R" or someting.
975 * indent \*(-- the string used to indent with. Defaults to \*(L" \*(R" (two
976 spaces). Another sane value might be \*(L". \*(R" (period, space). Setting it
977 to empty-string suppresses indenting.
979 The dump is not printed, but is returned as a list, where each
980 item is a line, with a \*(L"\en\*(R" at the end.
981 .IP "the constructor \s-1CLASS\-\s0>random_network({...options...})" 4
982 .IX Item "the constructor CLASS->random_network({...options...})"
984 .ie n .IP "the method $node\->random_network({...options...})" 4
985 .el .IP "the method \f(CW$node\fR\->random_network({...options...})" 4
986 .IX Item "the method $node->random_network({...options...})"
988 In the first case, constructs a randomly arranged network under a new
989 node, and returns the root node of that tree. In the latter case,
990 constructs the network under \f(CW$node\fR.
992 Currently, this is implemented a bit half-heartedly, and
993 half-wittedly. I basically needed to make up random-looking networks
994 to stress-test the various tree-dumper methods, and so wrote this. If
995 you actually want to rely on this for any application more
996 serious than that, I suggest examining the source code and seeing if
997 this does really what you need (say, in reliability of randomness);
998 and feel totally free to suggest changes to me (especially in the form
999 of "I rewrote \f(CW\*(C`random_network\*(C'\fR, here's the code...")
1001 It takes four options:
1003 * max_node_count \*(-- maximum number of nodes this tree will be allowed
1004 to have (counting the root). Defaults to 25.
1006 * min_depth \*(-- minimum depth for the tree. Defaults to 2. Leaves can
1007 be generated only after this depth is reached, so the tree will be at
1008 least this deep \*(-- unless max_node_count is hit first.
1010 * max_depth \*(-- maximum depth for the tree. Defaults to 3 plus
1011 min_depth. The tree will not be deeper than this.
1013 * max_children \*(-- maximum number of children any mother in the tree
1014 can have. Defaults to 4.
1015 .IP "the constructor \s-1CLASS\-\s0>lol_to_tree($lol);" 4
1016 .IX Item "the constructor CLASS->lol_to_tree($lol);"
1017 Converts something like bracket-notation for \*(L"Chomsky trees\*(R" (or
1018 rather, the closest you can come with Perl
1019 list\-of\-lists(\-of\-lists(\-of\-lists))) into a tree structure. Returns
1020 the root of the tree converted.
1022 The conversion rules are that: 1) if the last (possibly the only) item
1023 in a given list is a scalar, then that is used as the \*(L"name\*(R" attribute
1024 for the node based on this list. 2) All other items in the list
1025 represent daughter nodes of the current node \*(-- recursively so, if
1026 they are list references; otherwise, (non-terminal) scalars are
1027 considered to denote nodes with that name. So ['Foo', 'Bar', 'N'] is
1028 an alternate way to represent [['Foo'], ['Bar'], 'N'].
1030 An example will illustrate:
1033 \& use Tree::DAG_Node;
1037 \& [ [ \*(AqDet:The\*(Aq ],
1038 \& [ [ \*(Aqdog\*(Aq ], \*(AqN\*(Aq], \*(AqNP\*(Aq],
1039 \& [ \*(Aq/with rabies\e\e\*(Aq, \*(AqPP\*(Aq],
1042 \& [ \*(Aqdied\*(Aq, \*(AqVP\*(Aq],
1045 \& $tree = Tree::DAG_Node\->lol_to_tree($lol);
1046 \& $diagram = $tree\->draw_ascii_tree;
1047 \& print map "$_\en", @$diagram;
1050 \&...returns this tree:
1056 \& /\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\e
1060 \& /\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\e <died>
1064 \& /\-\-\-\-\-\-\-\e </with rabies\e>
1071 By the way (and this rather follows from the above rules), when
1072 denoting a LoL tree consisting of just one node, this:
1075 \& $tree = Tree::DAG_Node\->lol_to_tree( \*(AqLonely\*(Aq );
1078 is okay, although it'd probably occur to you to denote it only as:
1081 \& $tree = Tree::DAG_Node\->lol_to_tree( [\*(AqLonely\*(Aq] );
1084 which is of course fine, too.
1085 .ie n .IP "$node\->tree_to_lol_notation({...options...})" 4
1086 .el .IP "\f(CW$node\fR\->tree_to_lol_notation({...options...})" 4
1087 .IX Item "$node->tree_to_lol_notation({...options...})"
1088 Dumps a tree (starting at \f(CW$node\fR) as the sort of LoL-like bracket
1089 notation you see in the above example code. Returns just one big
1090 block of text. The only option is \*(L"multiline\*(R" \*(-- if true, it dumps
1091 the text as the sort of indented structure as seen above; if false
1092 (and it defaults to false), dumps it all on one line (with no
1093 indenting, of course).
1095 For example, starting with the tree from the above example,
1099 \& print $tree\->tree_to_lol_notation, "\en";
1102 prints the following (which I've broken over two lines for sake of
1103 printablitity of documentation):
1106 \& [[[[\*(AqDet:The\*(Aq], [[\*(Aqdog\*(Aq], \*(AqN\*(Aq], \*(AqNP\*(Aq], [["/with rabies\ex5c"],
1107 \& \*(AqPP\*(Aq], \*(AqNP\*(Aq], [[\*(Aqdied\*(Aq], \*(AqVP\*(Aq], \*(AqS\*(Aq],
1113 \& print $tree\->tree_to_lol_notation({ multiline => 1 });
1116 prints the same content, just spread over many lines, and prettily
1118 .ie n .IP "$node\->tree_to_lol" 4
1119 .el .IP "\f(CW$node\fR\->tree_to_lol" 4
1120 .IX Item "$node->tree_to_lol"
1121 Returns that tree (starting at \f(CW$node\fR) represented as a LoL, like what
1122 \&\f(CW$lol\fR, above, holds. (This is as opposed to \f(CW\*(C`tree_to_lol_notation\*(C'\fR,
1123 which returns the viewable code like what gets evaluated and stored in
1124 \&\f(CW$lol\fR, above.)
1126 Lord only knows what you use this for \*(-- maybe for feeding to
1127 Data::Dumper, in case \f(CW\*(C`tree_to_lol_notation\*(C'\fR doesn't do just what you
1129 .IP "the constructor \s-1CLASS\-\s0>simple_lol_to_tree($simple_lol);" 4
1130 .IX Item "the constructor CLASS->simple_lol_to_tree($simple_lol);"
1131 This is like lol_to_tree, except that rule 1 doesn't apply \*(-- i.e.,
1132 all scalars (or really, anything not a listref) in the LoL-structure
1133 end up as named terminal nodes, and only terminal nodes get names
1134 (and, of course, that name comes from that scalar value). This method
1135 is useful for making things like expression trees, or at least
1136 starting them off. Consider that this:
1139 \& $tree = Tree::DAG_Node\->simple_lol_to_tree(
1140 \& [ \*(Aqfoo\*(Aq, [\*(Aqbar\*(Aq, [\*(Aqbaz\*(Aq], \*(Aqquux\*(Aq], \*(Aqzaz\*(Aq, \*(Aqpati\*(Aq ]
1144 converts from something like a Lispish or Iconish tree, if you pretend
1145 the brackets are parentheses.
1147 Note that there is a (possibly surprising) degenerate case of what I'm
1148 calling a \*(L"simple-LoL\*(R", and it's like this:
1151 \& $tree = Tree::DAG_Node\->simple_lol_to_tree(\*(AqLonely\*(Aq);
1154 This is the (only) way you can specify a tree consisting of only a
1155 single node, which here gets the name 'Lonely'.
1156 .ie n .IP "$node\->tree_to_simple_lol" 4
1157 .el .IP "\f(CW$node\fR\->tree_to_simple_lol" 4
1158 .IX Item "$node->tree_to_simple_lol"
1159 Returns that tree (starting at \f(CW$node\fR) represented as a simple-LoL \*(--
1160 i.e., one where non-terminal nodes are represented as listrefs, and
1161 terminal nodes are gotten from the contents of those nodes' "name'
1164 Note that in the case of \f(CW$node\fR being terminal, what you get back is
1165 the same as \f(CW$node\fR\->name.
1167 Compare to tree_to_simple_lol_notation.
1168 .ie n .IP "$node\->tree_to_simple_lol_notation({...options...})" 4
1169 .el .IP "\f(CW$node\fR\->tree_to_simple_lol_notation({...options...})" 4
1170 .IX Item "$node->tree_to_simple_lol_notation({...options...})"
1171 A simple-LoL version of tree_to_lol_notation (which see); takes the
1173 .ie n .IP "$list_r = $node\->draw_ascii_tree({ ... options ... })" 4
1174 .el .IP "\f(CW$list_r\fR = \f(CW$node\fR\->draw_ascii_tree({ ... options ... })" 4
1175 .IX Item "$list_r = $node->draw_ascii_tree({ ... options ... })"
1176 Draws a nice ASCII-art representation of the tree structure
1177 at-and-under \f(CW$node\fR, with \f(CW$node\fR at the top. Returns a reference to the
1178 list of lines (with no \*(L"\en\*(R"s or anything at the end of them) that make
1184 \& print map("$_\en", @{$tree\->draw_ascii_tree});
1187 draw_ascii_tree takes parameters you set in the options hashref:
1189 * \*(L"no_name\*(R" \*(-- if true, \f(CW\*(C`draw_ascii_tree\*(C'\fR doesn't print the name of
1190 the node; simply prints a \*(L"*\*(R". Defaults to 0 (i.e., print the node
1193 * \*(L"h_spacing\*(R" \*(-- number 0 or greater. Sets the number of spaces
1194 inserted horizontally between nodes (and groups of nodes) in a tree.
1197 * \*(L"h_compact\*(R" \*(-- number 0 or 1. Sets the extent to which
1198 \&\f(CW\*(C`draw_ascii_tree\*(C'\fR tries to save horizontal space. Defaults to 1. If
1199 I think of a better scrunching algorithm, there'll be a \*(L"2\*(R" setting
1202 * \*(L"v_compact\*(R" \*(-- number 0, 1, or 2. Sets the degree to which
1203 \&\f(CW\*(C`draw_ascii_tree\*(C'\fR tries to save vertical space. Defaults to 1.
1205 This occasionally returns trees that are a bit cock-eyed in parts; if
1206 anyone can suggest a better drawing algorithm, I'd be appreciative.
1207 .ie n .IP "$node\->copy_tree or $node\->copy_tree({...options...})" 4
1208 .el .IP "\f(CW$node\fR\->copy_tree or \f(CW$node\fR\->copy_tree({...options...})" 4
1209 .IX Item "$node->copy_tree or $node->copy_tree({...options...})"
1210 This returns the root of a copy of the tree that \f(CW$node\fR is a member of.
1211 If you pass no options, copy_tree pretends you've passed {}.
1213 This method is currently implemented as just a call to
1214 \&\f(CW$this\fR\->root\->copy_at_and_under({...options...}), but magic may be
1215 added in the future.
1217 Options you specify are passed down to calls to \f(CW$node\fR\->copy.
1218 .ie n .IP "$node\->copy_at_and_under or $node\->copy_at_and_under({...options...})" 4
1219 .el .IP "\f(CW$node\fR\->copy_at_and_under or \f(CW$node\fR\->copy_at_and_under({...options...})" 4
1220 .IX Item "$node->copy_at_and_under or $node->copy_at_and_under({...options...})"
1221 This returns a copy of the subtree consisting of \f(CW$node\fR and everything
1224 If you pass no options, copy_at_and_under pretends you've passed {}.
1226 This works by recursively building up the new tree from the leaves,
1227 duplicating nodes using \f(CW$orig_node\fR\->copy($options_ref) and then
1228 linking them up into a new tree of the same shape.
1230 Options you specify are passed down to calls to \f(CW$node\fR\->copy.
1231 .ie n .IP "the constructor $node\->copy or $node\->copy({...options...})" 4
1232 .el .IP "the constructor \f(CW$node\fR\->copy or \f(CW$node\fR\->copy({...options...})" 4
1233 .IX Item "the constructor $node->copy or $node->copy({...options...})"
1234 Returns a copy of \f(CW$node\fR, \fBminus\fR its daughter or mother attributes
1235 (which are set back to default values).
1237 If you pass no options, \f(CW\*(C`copy\*(C'\fR pretends you've passed {}.
1239 Magic happens with the 'attributes' attribute: if it's a hashref (and
1240 it usually is), the new node doesn't end up with the same hashref, but
1241 with ref to a hash with the content duplicated from the original's
1242 hashref. If 'attributes' is not a hashref, but instead an object that
1243 belongs to a class that provides a method called \*(L"copy\*(R", then that
1244 method is called, and the result saved in the clone's 'attribute'
1245 attribute. Both of these kinds of magic are disabled if the options
1246 you pass to \f(CW\*(C`copy\*(C'\fR (maybe via \f(CW\*(C`copy_tree\*(C'\fR, or \f(CW\*(C`copy_at_and_under\*(C'\fR)
1247 includes (\f(CW\*(C`no_attribute_copy\*(C'\fR => 1).
1249 The options hashref you pass to \f(CW\*(C`copy\*(C'\fR (derictly or indirectly) gets
1250 changed slightly after you call \f(CW\*(C`copy\*(C'\fR \*(-- it gets an entry called
1251 \&\*(L"from_to\*(R" added to it. Chances are you would never know nor care, but
1252 this is reserved for possible future use. See the source if you are
1255 Note that if you are using \f(CW$node\fR\->copy (whether directly or via
1256 \&\f(CW$node\fR\->copy_tree or \f(CW$node\fR\->copy_at_or_under), and it's not properly
1257 copying object attributes containing references, you probably
1258 shouldn't fight it or try to fix it \*(-- simply override copy_tree with:
1262 \& use Storable qw(dclone);
1263 \& my $this = $_[0];
1264 \& return dclone($this\->root);
1273 \& use Data::Dumper;
1274 \& my $this = $_[0];
1275 \& $Data::Dumper::Purity = 1;
1276 \& return eval(Dumper($this\->root));
1280 Both of these avoid you having to reinvent the wheel.
1282 How to override copy_at_or_under with something that uses Storable
1283 or Data::Dumper is left as an exercise to the reader.
1285 Consider that if in a derived class, you add attributes with really
1286 bizarre contents (like a unique-for-all-time-ID), you may need to
1287 override \f(CW\*(C`copy\*(C'\fR. Consider:
1291 \& my($it, @etc) = @_;
1292 \& $it\->SUPER::copy(@etc);
1293 \& $it\->{\*(AqUID\*(Aq} = &get_new_UID;
1297 \&...or the like. See the source of Tree::DAG_Node::copy for
1299 .ie n .IP "$node\->delete_tree" 4
1300 .el .IP "\f(CW$node\fR\->delete_tree" 4
1301 .IX Item "$node->delete_tree"
1302 Destroys the entire tree that \f(CW$node\fR is a member of (starting at the
1303 root), by nulling out each node-object's attributes (including, most
1304 importantly, its linkage attributes \*(-- hopefully this is more than
1305 sufficient to eliminate all circularity in the data structure), and
1306 then moving it into the class \s-1DEADNODE\s0.
1308 Use this when you're finished with the tree in question, and want to
1309 free up its memory. (If you don't do this, it'll get freed up anyway
1310 when your program ends.)
1312 If you try calling any methods on any of the node objects in the tree
1313 you've destroyed, you'll get an error like:
1316 \& Can\*(Aqt locate object method "leaves_under"
1317 \& via package "DEADNODE".
1320 So if you see that, that's what you've done wrong. (Actually, the
1321 class \s-1DEADNODE\s0 does provide one method: a no-op method \*(L"delete_tree\*(R".
1322 So if you want to delete a tree, but think you may have deleted it
1323 already, it's safe to call \f(CW$node\fR\->delete_tree on it (again).)
1325 The \f(CW\*(C`delete_tree\*(C'\fR method is needed because Perl's garbage collector
1326 would never (as currently implemented) see that it was time to
1327 de-allocate the memory the tree uses \*(-- until either you call
1328 \&\f(CW$node\fR\->delete_tree, or until the program stops (at \*(L"global
1329 destruction\*(R" time, when \fBeverything\fR is unallocated).
1331 Incidentally, there are better ways to do garbage-collecting on a
1332 tree, ways which don't require the user to explicitly call a method
1333 like \f(CW\*(C`delete_tree\*(C'\fR \*(-- they involve dummy classes, as explained at
1334 \&\f(CW\*(C`http://mox.perl.com/misc/circle\-destroy.pod\*(C'\fR
1336 However, introducing a dummy class concept into Tree::DAG_Node would
1337 be rather a distraction. If you want to do this with your derived
1338 classes, via a \s-1DESTROY\s0 in a dummy class (or in a tree-metainformation
1339 class, maybe), then feel free to.
1341 The only case where I can imagine \f(CW\*(C`delete_tree\*(C'\fR failing to totally
1342 void the tree, is if you use the hashref in the \*(L"attributes\*(R" attribute
1343 to store (presumably among other things) references to other nodes'
1344 \&\*(L"attributes\*(R" hashrefs \*(-- which 1) is maybe a bit odd, and 2) is your
1345 problem, because it's your hash structure that's circular, not the
1346 tree's. Anyway, consider:
1349 \& # null out all my "attributes" hashes
1350 \& $anywhere\->root\->walk_down({
1351 \& \*(Aqcallback\*(Aq => sub {
1352 \& $hr = $_[0]\->attributes; %$hr = (); return 1;
1356 \& $anywhere\->delete_tree;
1359 (I suppose \f(CW\*(C`delete_tree\*(C'\fR is a \*(L"destructor\*(R", or as close as you can
1360 meaningfully come for a circularity-rich data structure in Perl.)
1361 .SS "When and How to Destroy"
1362 .IX Subsection "When and How to Destroy"
1363 It should be clear to you that if you've built a big parse tree or
1364 something, and then you're finished with it, you should call
1365 \&\f(CW$some_node\fR\->delete_tree on it if you want the memory back.
1367 But consider this case: you've got this tree:
1377 Let's say you decide you don't want D or any of its descendants in the
1378 tree, so you call D\->unlink_from_mother. This does \s-1NOT\s0 automagically
1379 destroy the tree D\-X-Y. Instead it merely splits the tree into two:
1389 To destroy D and its little tree, you have to explicitly call
1392 Note, however, that if you call C\->unlink_from_mother, and if you don't
1393 have a link to C anywhere, then it \fBdoes\fR magically go away. This is
1394 because nothing links to C \*(-- whereas with the D\-X-Y tree, D links to
1395 X and Y, and X and Y each link back to D. Note that calling
1396 C\->delete_tree is harmless \*(-- after all, a tree of only one node is
1399 So, this is a surefire way of getting rid of all \f(CW$node\fR's children and
1400 freeing up the memory associated with them and their descendants:
1403 \& foreach my $it ($node\->clear_daughters) { $it\->delete_tree }
1406 Just be sure not to do this:
1409 \& foreach my $it ($node\->daughters) { $it\->delete_tree }
1410 \& $node\->clear_daughters;
1413 That's bad; the first call to \f(CW$_\fR\->delete_tree will climb to the root
1414 of \f(CW$node\fR's tree, and nuke the whole tree, not just the bits under \f(CW$node\fR.
1415 You might as well have just called \f(CW$node\fR\->delete_tree.
1416 (Moreavor, once \f(CW$node\fR is dead, you can't call clear_daughters on it,
1417 so you'll get an error there.)
1419 .IX Header "BUG REPORTS"
1420 If you find a bug in this library, report it to me as soon as possible,
1421 at the address listed in the \s-1MAINTAINER\s0 section, below. Please try to
1422 be as specific as possible about how you got the bug to occur.
1425 If you develop a given routine for dealing with trees in some way, and
1426 use it a lot, then if you think it'd be of use to anyone else, do email
1427 me about it; it might be helpful to others to include that routine, or
1428 something based on it, in a later version of this module.
1430 It's occurred to me that you might like to (and might yourself develop
1431 routines to) draw trees in something other than \s-1ASCII\s0 art. If you do so
1432 \&\*(-- say, for PostScript output, or for output interpretable by some
1433 external plotting program \*(-- I'd be most interested in the results.
1435 .IX Header "RAMBLINGS"
1436 This module uses \*(L"strict\*(R", but I never wrote it with \-w warnings in
1437 mind \*(-- so if you use \-w, do not be surprised if you see complaints
1438 from the guts of DAG_Node. As long as there is no way to turn off \-w
1439 for a given module (instead of having to do it in every single
1440 subroutine with a \*(L"local $^W\*(R"), I'm not going to change this. However,
1441 I do, at points, get bursts of ambition, and I try to fix code in
1442 DAG_Node that generates warnings, \fIas I come across them\fR \*(-- which is
1443 only occasionally. Feel free to email me any patches for any such
1444 fixes you come up with, tho.
1446 Currently I don't assume (or enforce) anything about the class
1447 membership of nodes being manipulated, other than by testing whether
1448 each one provides a method \f(CW\*(C`is_node\*(C'\fR, a la:
1451 \& die "Not a node!!!" unless UNIVERSAL::can($node, "is_node");
1454 So, as far as I'm concerned, a given tree's nodes are free to belong to
1455 different classes, just so long as they provide/inherit \f(CW\*(C`is_node\*(C'\fR, the
1456 few methods that this class relies on to navigate the tree, and have the
1457 same internal object structure, or a superset of it. Presumably this
1458 would be the case for any object belonging to a class derived from
1459 \&\f(CW\*(C`Tree::DAG_Node\*(C'\fR, or belonging to \f(CW\*(C`Tree::DAG_Node\*(C'\fR itself.
1461 When routines in this class access a node's \*(L"mother\*(R" attribute, or its
1462 \&\*(L"daughters\*(R" attribute, they (generally) do so directly (via
1463 \&\f(CW$node\fR\->{'mother'}, etc.), for sake of efficiency. But classes derived
1464 from this class should probably do this instead thru a method (via
1465 \&\f(CW$node\fR\->mother, etc.), for sake of portability, abstraction, and general
1468 However, no routines in this class (aside from, necessarily, \f(CW\*(C`_init\*(C'\fR,
1469 \&\f(CW\*(C`_init_name\*(C'\fR, and \f(CW\*(C`name\*(C'\fR) access the \*(L"name\*(R" attribute directly;
1470 routines (like the various tree draw/dump methods) get the \*(L"name\*(R" value
1471 thru a call to \f(CW$obj\fR\->\fIname()\fR. So if you want the object's name to not be
1472 a real attribute, but instead have it derived dynamically from some feature
1473 of the object (say, based on some of its other attributes, or based on
1474 its address), you can to override the \f(CW\*(C`name\*(C'\fR method, without causing
1475 problems. (Be sure to consider the case of \f(CW$obj\fR\->name as a write
1476 method, as it's used in \f(CW\*(C`lol_to_tree\*(C'\fR and \f(CW\*(C`random_network\*(C'\fR.)
1478 .IX Header "SEE ALSO"
1481 Wirth, Niklaus. 1976. \fIAlgorithms + Data Structures = Programs\fR
1482 Prentice-Hall, Englewood Cliffs, \s-1NJ\s0.
1484 Knuth, Donald Ervin. 1997. \fIArt of Computer Programming, Volume 1,
1485 Third Edition: Fundamental Algorithms\fR. Addison-Wesley, Reading, \s-1MA\s0.
1487 Wirth's classic, currently and lamentably out of print, has a good
1488 section on trees. I find it clearer than Knuth's (if not quite as
1489 encyclopedic), probably because Wirth's example code is in a
1490 block-structured high-level language (basically Pascal), instead
1491 of in assembler (\s-1MIX\s0).
1493 Until some kind publisher brings out a new printing of Wirth's book,
1494 try poking around used bookstores (or \f(CW\*(C`www.abebooks.com\*(C'\fR) for a copy.
1495 I think it was also republished in the 1980s under the title
1496 \&\fIAlgorithms and Data Structures\fR, and in a German edition called
1497 \&\fIAlgorithmen und Datenstrukturen\fR. (That is, I'm sure books by Knuth
1498 were published under those titles, but I'm \fIassuming\fR that they're just
1499 later printings/editions of \fIAlgorithms + Data Structures =
1502 .IX Header "MAINTAINER"
1503 David Hand, \f(CW\*(C`<cogent@cpan.org>\*(C'\fR
1506 Sean M. Burke, \f(CW\*(C`<sburke@cpan.org>\*(C'\fR
1507 .SH "COPYRIGHT, LICENSE, AND DISCLAIMER"
1508 .IX Header "COPYRIGHT, LICENSE, AND DISCLAIMER"
1509 Copyright 1998\-2001, 2004, 2007 by Sean M. Burke and David Hand.
1511 This program is free software; you can redistribute it and/or modify it
1512 under the same terms as Perl itself.
1514 This program is distributed in the hope that it will be useful, but
1515 without any warranty; without even the implied warranty of
1516 merchantability or fitness for a particular purpose.
projects / catagits/Gitalist.git / blob