How do "you" make a tree in perl

Replies are listed 'Best First'.
Re: How do "you" make a tree in perl by perrin (Chancellor) on Sep 29, 2004 at 00:44 UTC
I use Tree::DAG_Node.	[reply]
Re^2: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 02:46 UTC
Personally I am not a fan of Tree::DAG_Node, which is why I wrote Tree::Simple. IMO, It tries to do too much in one module, and I really don't like the idea that it doesn't have any tests associated with it (except to test that the module loads). I am hesitant to write Visitors to convert from one Tree:: module to mine, as it sort of feels rude to do so. -stvn	[reply]
Re^3: How do "you" make a tree in perl by cchampion (Curate) on Sep 29, 2004 at 09:37 UTC
Tree::DAG_Node may look like overshooting, but it does what it promises, i.e. a simple way of dealing with complex tree structures. I share your chagrin about lack of tests, but having seen that knowledgeable people like merlyn and perrin use it, I feel confident that it must not be as bad as you may think. A simple example that makes me love this module: `#!/usr/bin/perl -w use strict; use Tree::DAG_Node; my $tree = [ [ 'Node1' ], [ [ 'GrandChild1' ], [ 'GrandChild2' ], 'Node2' ], 'Root' ]; my $dagnode= Tree::DAG_Node->lol_to_tree($tree); print map {"$_\n"} @{ $dagnode->draw_ascii_tree }; __END__ And the output is: \| <Root> /-----------------\ \| \| <Node1> <Node2> /-------------\ \| \| <GrandChild1> <GrandChild2>` [download] There is also a nice Introduction to Tree::DAG_Node in Tutorials.	[reply] [d/l]
Re^4: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 15:12 UTC
Re^3: How do "you" make a tree in perl by hossman (Prior) on Sep 29, 2004 at 05:15 UTC
I am hesitant to write Visitors to convert from one Tree:: module to mine, as it sort of feels rude to do so. I wouldn't worry about it that much, there's nothing wrong with providing good tools and a a flexible API. If it eases your conscience, provide code to convert both ways.	[reply]
Re^4: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 14:06 UTC
Re: How do "you" make a tree in perl by dragonchild (Archbishop) on Sep 29, 2004 at 01:05 UTC
HTML::Template uses AoH(oAoH) for loops (and loops of loops). While not a tree in the classical sense, that data structure is tree-ish, I suppose. When I do use trees, I tend to put them in the database and let Oracle figure them out using CONNECT BY. Being right, does not endow the right to be rude; politeness costs nothing. Being unknowing, is not the same as being stupid. Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence. Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better. I shouldn't have to say this, but any code, unless otherwise stated, is untested	[reply]
Re^2: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 02:41 UTC
HTML::Template's TMPL_LOOP structures is a good one, thanks. I had not really thought of that one, even though I use HTML::Template all the time. I was thinking about writing some Visitors for reading trees out of databases too, but I doubt I will have enough time to really do that before my next project starts. BTW - I like the new sig. -stvn	[reply]
Re: How do "you" make a tree in perl by FoxtrotUniform (Prior) on Sep 29, 2004 at 02:22 UTC
If you want to be "tricky", you can pack a binary heap into a one-dimensional list: `my $heap = ['Root', 'Child1', 'Child2', 'Grandchild1', Grandchild2'];` [download] See heapsort for a stereotypical use of binary heaps. They're not as general as n-ary trees (being strictly binary and left-balanced), but they might make an interesting example. For further fun and games with low-level-hacking data structures, pack a binheap into a string, with either null-separated or fixed-width fields: `# "\0" is a null, right? my $ns_heap = "R\0C1\0C2\0GC1\0GC2\0"; my $fw_heap = "R\0\0C1\0C2\0GC1GC2";` [download] Again, this is almost gratuitously ugly, but might make a "fun" example. `-- F o x t r o t U n i f o r m Found a typo in this node? /msg me % man 3 strfry`	[reply] [d/l] [select]
Re^2: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 02:51 UTC
I think that you and I tend to have somewhat similar ideas of "fun". However, this is a little more esoteric then I was looking for ;-) -stvn	[reply]
Re^3: How do "you" make a tree in perl by FoxtrotUniform (Prior) on Sep 29, 2004 at 05:39 UTC
(T)his is a little more esoteric then I was looking for ;-) That shows good sense. On the subject of heaps, it would be neat to see a `->heapify` method of some sort, especially if you supported binomial and/or fibonacci heaps (which are algorithmically very cool). That wouldn't be very `::Simple`, but it might be useful (and fun to implement). `-- F o x t r o t U n i f o r m Found a typo in this node? /msg me % man 3 strfry`	[reply] [d/l] [select]
Re^4: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 15:14 UTC
Re: How do "you" make a tree in perl by SpanishInquisition (Pilgrim) on Sep 29, 2004 at 13:30 UTC
This is mostly a duplicate ... I tried to refine my post below and clicked submit versus edit, please refer to that one...	[reply]
Re^2: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 15:46 UTC
NOTE: This node is in response to a node which the author deleted (see above), sorry if it doesn't make sense out of context, not much I can do about it now. Doing fancy traversal thingies. Tree::Simple::Visitor provides a pre-order traversal, Tree::Simple::VisitorFactory provides a post-order traversal as well as breadth-first traversal. All have been thoroughly tested with approx. 90%+ code coverage. If you need a binary tree, I also wrote Tree::Binary, which has pre-order, post-order, in-order and breadth-first traversal Visitor objects as well. Here I'd write a specialized Node class,... Tree::Simple makes no assumptions about your node, you can store anything you like in the node value slot (provided of course its a scalar value or reference). All Tree::Simple really does is create the structural relationship between itself and its children and its parents. no visitor factories or view classes or other mega-designed stuff (I don't believe in such things ... To each their own, it is your choice. But I disagree that these things are "mega-designed". They are smart patterns, written down by very smart people because they found that enough other smart people they knew followed them (or something similar to them). Patterns may feel like "over-design" at times, but the fact is that they do make a lot of sense in a lot of cases to a lot of people. I wouldn't dismiss them so readily if I were you. Also keep in mind, that my intention was not to "over-design", but to try and keep seperate concerns seperate. If you don't need it, you should not have to use it (compile it, pollute your namespace with it, etc.) And really, the Visitor factory is really pretty small, 23 lines of code, and 3 methods. Its really just a way to prevent having to write long module names. The View classes (i assume you are talking about Tree::Simple::View) are very simple to use, you can get a full expanding and collapsing DHTML tree in approx. 1 line of code using it. The goal here is not to get the Software Design of the Year award, but to make it easy for the user to get the most functionality with the least code. I'm a control freak. Me too, thats why I wrote Tree::Simple instead of used Tree::DAG_Node. Anyhow, I rarely need to do this for commercial/work type programs, this is usually a "for fun" type of endeavor, and when I do things for fun, I like to do as much as possible myself. I agree, it is rarely as much "fun" to use a module, as it is to figure it out on your own. If you are writing a tree class, already did :) it might be nice to have restricted modes for trees of fixed/variable node-size, This can easily be done with a subclass of Tree::Simple. ... red-black trees, ... I think this is better done as it's own module, rather than try to squeeze it in with a basic n-ary tree. and heaps. Again, better as another module IMO. Although as I suggested to FoxTrotUniform above, maybe that would work as a Visitor too. To be honest, my experience with heaps is limited. You may also want to have optional up-pointers. Tree::Simple has a `getParent` method already. For my needs, this was critical to have. You might also want to generalize your base class nodes for graph usage. Well there is Graph out there already (which I have not examined all that closely). And while a tree is really just a specialized graph, I think maybe it would be over-generalizing it to go that far. I would suspect that in the end the base class would not be able to effectively serve all the specialized types of graphs out there. You might like classes that run minimax with alpha-beta pruning on a tree. I wrote Tree::Binary::Search, which has both a min and a max function. And while that may be useful in some n-ary tree situations, I think it is best not included in the base class, but in a Visitor :) But it sounds to me you aren't trying to make a Tree::Simple, you are trying to make a Forrest::VeryComplex. Tree::Simple is intentionally very basic, which is why all the Visitor classes. They allow me to offer complex functionality without polluting Tree::Simple with too many methods and responsibilities. Decide what you want, and do it. I don't think a Tree::Simple should concern anyone about visitor patterns, factories, and views, but that's just me. But my goal is not to just "do what I want to do", but to offer others code they can use. You need not concern yourself with visitors, factories and views in order to use Tree::Simple. You can just use Tree::Simple and forget about all the other stuff. However, then you need to implement all that functionality on your own. They are just additional tools to make my (and maybe your) life easier. I usually shudder when I see design pattern terminology. I avoid it like the plague. Well, this is your choice. -stvn	[reply] [d/l]
Re: How do "you" make a tree in perl by SpanishInquisition (Pilgrim) on Sep 29, 2004 at 13:47 UTC
Actually, I write my own tree and graph modules to suit the task ... I'm a control freak. That, and I don't usually like tweaking other people's modules when they don't do exacty what I want (style issues) and datastructures are important enough that you should understand how all of them in your program are implemented. Too many people these days learn programming by way of languages where all of the datastructure work is done for them, so they really just become users of tools instead of people that can think for themselves... Anyhow, on the topic of "what do I do", while nested hashes are ok for serialization, they are too unsafe due to the possiblity of coding errors (I prefer syntax errors to runtime errors), so I'll usually do something specialized and optomzied to the task. This probably involves having some objects behave as Nodes, which is where we need mixins (subclassing Node is wrong!) ... which is not really covered cleanly in Perl 5.x I also abhor the design pattern FAD so I avoid things such as VisitorFactories, as I get this silly image of a factory with Tourists popping out of the loading dock -- that's not what OO is supposed to be about. I think you've got a Forrest::Complex there instead of a Tree::Simple. No reason to rant against Tree::DAG_Node about line count (line count wars are always petty) in your POD when you have a design such as this requiring so many modules for a "Tree::Simple" class. (edited slightly to tone down design pattern rant)	[reply]
Re^2: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 16:15 UTC
Too many people these days learn programming by way of languages where all of the datastructure work is done for them, so they really just become users of tools instead of people that can think for themselves... I agree with you that people need to learn the basics too, but I disagree that being a "user of tools" is a bad thing. I think if you look at all of mankinds great acheivements (especially in the modern era), you will find that many (if not all of them) would not have been possible if people did not stand on the shoulders of others to get there. It is the sharing of knowledge and tools which got us to where we are today as a species (I will make no judgements as to whether that is a good place or a bad place). This probably involves having some objects behave as Nodes, which is where we need mixins (subclassing Node is wrong!) I like mix-ins too, but I am not sure they are always better than subclassing (which is what I think your implying here, but I may be wrong). I also abhor the design pattern FAD so I avoid things such as VisitorFactories, as I get this silly image of a factory with Tourists popping out of the loading dock -- that's not what OO is supposed to be about. I don't agree that it is a FAD, and all that being a "FAD" implies. But that is your perogative. I think you've got a Forrest::Complex there instead of a Tree::Simple Maybe if you take into account all the other Tree::Simple::* classes, but that is all optional. And while I am not really 100% happy with the ::Simple name, and have many times regreted calling it that, it is too late to change now as I have a number of users of the module already, that that is not fair to them. No reason to rant against Tree::DAG_Node about line count (line count wars are always petty) in your POD I just re-read that, and I realize I am not being clear. My problem with Tree::DAG_Node is that it only has one test, and that is to test if the module loads without errors. It is pretty well known and accepted that the number of bugs increases alongside the number of lines of code. So to me having 1500+ lines of virtually untested code is not acceptable, I am (badly) contrasting this with the 250+ lines of code in Tree::Simple, which comes with approx. 400+ tests and has 97% code coverage. -stvn	[reply]
Re^3: How do "you" make a tree in perl by SpanishInquisition (Pilgrim) on Sep 29, 2004 at 17:47 UTC
You may be confusing lack of an integrated Test::More with a lack of testing. While automated testing in a CPAN module is awesome, the omission does not mean the author did not test it. In fact, to assume only automated testing is sufficient is an equivalent evil. I like mix-ins too, but I am not sure they are always better than subclassing (which is what I think your implying here, but I may be wrong). You are indeed. I am referring to the common falacy of subclassing Car as a Node just because you need a Tree of Cars. I'm not sure having Car as a data element in a Tree is exactly right either, though it is more passable. As for design patterns not being a FAD, you have to think about when they started to come into acceptance and whether such technology existed "pre design patterns" and if there is software today that is sufficiently more advanced because of them. My answer to these questions are no -- the design patterns are not bad because they are not useful, they are bad because they are BLATANTLY OBVIOUS way of restarting what computer scientists have done for a long time. Eric and the GoF are guilty of blatant plagarism -- and all those that worship them are doing millions of programmers a great disservice. We do not need to buy a specific book that gives us legos to build software from -- I'm a HUGE advocate of solid design and planning, but I also believe in sensible breakdown of components without a lot of sludge gumming up the gears. And, as you say, "that is my perogative". Why do I say this? Why do I shun design patterns? Because I love software design. People that really love software design can see what they are doing is just dumbing down Software design into a bunch of duplo blocks. Don't implement a "Facade pattern" because you read it was good in a book. I am not a simple user of someone else's duplo blocks -- this is the rapidly disappearing line between computer science -- this is the commodization of programming -- (or to the same: this is the reason all of our jobs will go to India as soon as we all think alike and exactly the same -- safe programming languages whether COBOL or Java, coupled with politically correct design patterns, signal the doom of the world). Implement an interface because you know what an interface is and because it is needed. Call an abstraction layer and abstraction layer. No need to claim that only PhD's can write books on good software and only lofty " architects" can design good software ... this just hurts us all. Why make a quasi-religion out of common sense? And why make simple things too complicated? Part of good software design is knowing when to stop. I chose not to build on to these ivory towers (castles?) and keep things simple where I can. Others may chose not to. That's fine. But they should not profess that this is the only way or that the design pattern people are somehow "smarter" than the rest of us because they retranslated common sense into lofty holier-than-thou textbooks that are politically incorrect to disagree with.	[reply]
Re^4: How do "you" make a tree in perl by stvn (Monsignor) on Sep 29, 2004 at 18:03 UTC
Re^5: How do "you" make a tree in perl by SpanishInquisition (Pilgrim) on Sep 29, 2004 at 18:18 UTC
Re: How do "you" make a tree in perl by Jaap (Curate) on Sep 29, 2004 at 21:28 UTC
Well, now that you 're asking... I usually find myself wanting to store a tree in a database. When i request a leaf by ID, i want to get the path, and when i get a leaf by path, i want to know its id. Also, it's nice to know the previous/next (sibling) of a leaf. I currently store the tree in a table like so: `id parent node 1 0 Root 2 1 Fruit 3 2 Apple 4 2 Pear 5 2 Banana 6 1 Vegetable 7 6 Spinach` [download] I think you get the idea. The items usually aren't sorted like they are in the example above.	[reply] [d/l]
Re: How do "you" make a tree in perl by Anonymous Monk on Sep 30, 2004 at 00:25 UTC
To answer your question, I usually use nested arrayrefs when I implement trees in basic Perl data structures and the second of the two "complex relational" structures when I'm storing them in databases. FWIW, a few months ago I was looking for a good Tree::* module that I could quickly adapt for a project I was working on. I looked at your Tree::Simple and ultimately decided against it and went with Tree::MultiNode instead. I just liked Tree::MultiNode's API better, although I would say Tree::Simple looks like it is the more mature of the two.I admit that what initially turned me off on Tree::Simple was the use of StudlyCaps for method names, but I was also attracted to Tree::MultiNode since it is an implementation of Sedgewick's algorithms which I was familiar with. Anyway, I just re-read the Tree::Simple POD on search.cpan.org, and I noticed that you compare and contrast Tree::Simple to every other Tree::* module out there except Tree::MultiNode. Sorry to go off on this tangent...	[reply]
Re^2: How do "you" make a tree in perl by stvn (Monsignor) on Sep 30, 2004 at 03:52 UTC
Anyway, I just re-read the Tree::Simple POD on search.cpan.org, and I noticed that you compare and contrast Tree::Simple to every other Tree::* module out there except Tree::MultiNode. Sorry to go off on this tangent... Yes, that section needs rewriting, initially I was only trying to list Tree:: module which were registered. I think I will surely redo that section in the next release. -stvn	[reply]