Purpose of trees

Replies to This Discussion

Permalink Reply by David Rutten on January 20, 2015 at 2:48am

I'll try and type something up in the FAQ today. 

Permalink Reply by Darrell Plank on January 20, 2015 at 2:49am

You are incredibly responsive and helpful David.  I appreciate anything and everything you post.  Thanks so much!

Permalink Reply by David Rutten on January 20, 2015 at 2:51pm

Well, it's unfinished, but I started the article.

http://www.grasshopper3d.com/forum/topics/the-why-and-how-of-data-t...

Permalink Reply by Armin Seltz on January 20, 2015 at 4:51am

"we have trees of lists rather than just lists of lists" - I am not sure what you mean by that, but I think they are the same thing. In some languages they are called arrays and elements, spreads and slices, etc. The tree is the hierarchy map of the data inside. It is important, because it dictates how most components use data, when different inputs in 1 component have different data trees.

In the bottom image of yours: You are not trying to get the item 0 and 1 from the actual list of data. The Param Viewer does NOT output the list that you input it, but the list of the indexes in the tree, so what you are trying in the image will fail anyways. Also you have to note that the Param Viewer outputs a list with address {0}, whereas the Series outputs a list with address {0;0}. 

In any case, it took me quite a long time to understand the tree and there is still some things I dont get. Try to flatten whereever possible and then use the List components (they are easier to use because they just work with indexes, ie. numbers, and not paths with the curly brackets) and Graft and Flatten directly on the inputs and outputs where necessary. Also simplify is your friend!

Permalink Reply by Darrell Plank on January 20, 2015 at 9:27am

Thanks Armin!  "we have trees of lists rather than just lists of lists" - what I meant is that trees are just lists of things and lists are just lists of things - every branch is just a list of the branches below it.  In most languages (mathematica, C#, C++, Lisp, Java...) we just have lists and it works out fine.  If you want to build a tree in those languages, you make a list of lists.  But in Grasshopper we seem to have trees for everything but the last level which is a list.  In the Param Viewer only the branches of the tree are shown and that last level, the list, is compressed into a single node in the viewer.  In David's diagram in the "Grasshopper Primer" the branches appear as gray "limbs" on a tree and the lists appear as colorful "fruit" at the end of the branches.  Common sense tells me they ought to be the same thing, but everywhere I look there seems to be a distinction and I don't understand why that distinction is made.

I think you're slightly misinterpreting the output of the panel in my bottom picture.  The 0,1 in the panel are just the indices put there by the panel - the output is a list of [0,0].  The path component turns this into the path {0;0} which I verified.  So as far as I can see, I should be getting the 0'th branch from the root and then the 0'th branch off of that branch.  Are there two levels to this tree?  I don't see how there can't be - one formed by the series and then another level placed by the graft.  The param viewer seems to bear this out as does the panel.  If there are two levels then I'd ought to be able to retrieve the 0'th branch from the first level and the 0'th branch from the second...but I can't.  The output tells me that such a path doesn't exist in the tree.  Does that mean it's only one level?  Does it mean that there is no 0'th branch on one of the levels?  I can't believe that - the branches are numbered from 0 to n.  I just don't know what it means.

Thanks very much for the advice!  I know I can flatten a lot, but really my goal is to be able to understand the trees better so I can understand when to flatten and when to graft.  I don't have any such problem in Mathematica or Lisp which I've "flattened" and "grafted" for years and where trees are just lists of lists, but every time I think I understand what is going on in GH, I do an experiment such as the above and find out I'm missing something.

Permalink Reply by Armin Seltz on January 20, 2015 at 10:37am

Yeah Ok I see what you mean. I guess I never questioned it, but now that you mention it, that IS a bit strange. I have worked with arrays a lot and yeah if there are 3 items at {0;0;0}, {0;0;1} and {0;0;2} getting {0;0} should return all 3 (because they are hierarchicly below it). 

Actually zooming in on the Param Viewer it shows the first branch (the trunk of the tree) to be {0;0}. Therefore the path DOES exist.

Hmm, I think you are right in wondering why that doesn't work. I am intruiged now too :)

Permalink Reply by nikos tzar on January 20, 2015 at 12:02pm

The thing is that a data tree doesn't always have to be uniformly shaped.

What this means is that it could actually contain branched of different lengths.

for example it could have a list in branch {0;0} and also lists in branches {0;0;0}, {0;0;1} and {0;0;2}.

That is why trying to get path {0;0} returns nothing in this case (there are no items in this exact path).

To get all the {0;0;x} branches you have to use the [split tree] component (which accepts masks) with mask input {0;0;?}

Permalink Reply by nikos tzar on January 20, 2015 at 1:17pm

here is an example of a tree with different branch levels:

As you can see, it is possible to get the branch {0;0} because it actually contains some items, but you can't get branch {0;1} because it only contains more branches and no items. To get all branches inside branch {0;1} you have to use [split tree] as in the example above.

Permalink Reply by Darrell Plank on January 20, 2015 at 8:38pm

Okay - I assumed that if I asked for path {0;0} I would get the tree which descended from that branch.  So path's are only valid when they extend all the way to leaves, not for interiors nodes?  Had no idea.  I'll restart the experiments!

That's exactly the sort of information I feel like is important but doesn't seem to be well documented.  In the .NET XmlDocument class, for instance they have the notion of XPaths which are similar to branches - a path of {0;1} (I'm being liberal with XPath syntax here) says take child 0 from the root node and then child 1 from that node and is roughly equivalent to a path {0;1} in GH: take branch 0 from the root and then branch 1, but there's no requirement to have a path extend all the way to a leaf in XmlDocument.  If you stop before a leaf you just get the tree at that node.  Anyway, that's the kind of tree I'm used to and clearly different than the trees of GH - hence my confusion.  Thanks for clearing at least that little mystery up!

Permalink Reply by David Rutten on January 20, 2015 at 3:34pm

Incidentally to answer your questions about:

but nothing seems to explain the reasoning behind the existence of trees and the philosophy for how and when they should be used and when lists should/could be used and precisely what the difference is between them.

You don't have a choice. All data in GH is stored in trees. If the tree only has a single branch, then it represents a simple list. If that list only has a single item, it represents an individual value. The nomenclature is a bit warped in GH1 (data trees have been through a major cleanup effort in GH2), but here's the general idea:

• Items are the actual blobs of individual data. A single number, or a single curve is an item. People also sometimes call these things values, datapoints, variables or elements. I prefer 'item'.
• All items are stored in lists. A list is an ordered collection of zero or more items. The first item is stored at index=0, the second item at index=1 and so on. A list may contain gaps, in that a specific index does not need to be associated with a specific item. Early versions of GH did not allow this, but now it's considered good practise to keep your tree topology as intact as possible in case you need to merge it later.
• Every list is identified by a path. A path is an ordered collection of one or more non-negative integers. Each path in a tree is unique, and the sort order of the paths controls the order in which lists appear in the tree. You cannot manually change this order, it is the law of the land.
• The combination of a list and its associated path is called a branch. This is especially unclear in GH1, where branch and list are often used interchangeably.
• A tree is a sorted collection of zero or more branches.

If you know programming then I can write it down pretty succinctly:

SortedList<Path, List<T>> where T is the type of the items

Permalink Reply by Darrell Plank on January 20, 2015 at 8:56pm

Thanks David.  I've started writing some C# nodes and printing out details so I may be starting to see the light a bit.  ALL items are stored in lists and ALL lists are leaves of trees is what I hear you saying.  I was starting to get that idea but then I tried piping a simple number into a param viewer to test it and I got a big error so I figured I was wrong about that.  Perhaps the answer is that there is a list/tree "above" the number but piping only the number leaves that tree/list behind?  Is another tree/list created in the next node or does the param viewer just throw away that tree/list for what it displays in the case of simple items?

In your example can the type T be a tree or a list?  I guess since all lists have to be identified by a path, that would disallow this.  Ditto I assume for T being a tree - T can only be some sort of item type.

I'm still not quite sure why a series puts out something that can be flattened and produce a different result.  From what you're saying, flattening a series leaves a list which must be a part of a tree so I guess you've still got a tree, but the tree before the flattening has an extra level.  Why is there an extra, seemingly gratuitous level in the output of Series before flattening?  If you ask Linq for a Range() it gives you a IEnumerable of integers, not a tree with an extra layer that could then be flattened out to yield just the IEnumerable.  Why is it different in GH?

I think maybe key to all of this is your statement that a tree is a "collection of branches" and your C# definition of a branch.  Perhaps my problem is that I'm assuming that there are interior nodes to your tree but really there aren't - there's just a collection of branches each of which has a list in it.  The "interior" nodes are really only a fiction by the way the paths are layed out.  This would explain Nikos's clarification above and my confusion.  I assumed that paths could terminate in the interior of the tree and you would get the "node" (i.e., tree) at that path.  If there are no actual interior nodes, then of course that wouldn't work.  I'll try to rethink everything from that context and maybe it will make more sense.

Okay, I'm sorry to have expended so much of your time.  I'm going to go back to writing C# nodes to try to piece all of this out for myself.  You've been more than kind!

Darrell

Permalink Reply by David Rutten on January 21, 2015 at 3:04am

"[...] I tried piping a simple number into a param viewer to test it and I got a big error [...]"

ParamViewer should never give errors, can you post a file so I can replicate?

"Is another tree/list created in the next node or does the param viewer just throw away that tree/list for what it displays in the case of simple items?"

Since everything is stored inside Data Trees, you cannot pass individual items of data from one parameter to another.

"In your example can the type T be a tree or a list?"

It depends a bit. the DataTree<T> class used for scripting components has no constraints on what T can be, however the GH_Structure<T> class (which is the implementation of data trees used everywhere else) requires that T implements the IGH_Goo interface.

"I'm still not quite sure why a series puts out something that can be flattened and produce a different result."

Flattening is an operation which collects all items in the entire tree and puts them all in a single list with the associated path {0}. If the original tree only has a single list then the path is all that changes.

"From what you're saying, flattening a series leaves a list which must be a part of a tree so I guess you've still got a tree, but the tree before the flattening has an extra level.  Why is there an extra, seemingly gratuitous level in the output of Series before flattening?"

This is handled in the 'The messy reality of data trees.' paragraph in the FAQ post. Series outputs a list with path {0;0} because it's a 1:N kind of component, and those always add an extra level onto paths. This is to reduce the chances that a change in input tree topology results in a change in output tree topology:

"If you ask Linq for a Range() it gives you a IEnumerable of integers, not a tree with an extra layer that could then be flattened out to yield just the IEnumerable.  Why is it different in GH?"

Because a Grasshopper Range component can be used to generate a lot of different ranges at the same time, and we need to be able to keep them apart in separate lists.

"The "interior" nodes are really only a fiction by the way the paths are layed out."

That's true. I do not store empty paths that are implied by the existence of more complex paths. The ParamViewer displays them, but only because it reverse-engineers them from the flat list of paths. This is not an unreasonable assumption you've made, usually when the word 'tree' is used with respect to algorithms it would imply a fully nested structure with nodes all the way from the top. And I certainly could have implemented it that way, but I chose a more abstract approach, which saves a little bit of memory and makes modifying paths somewhat easier.

• ‹ Previous
• 1
• 2
• Next ›
• Page