Playing with GH_Structure

unhandled

#1

Hi,

I’d like to convert a GH_Structure into a common tree (not GH DataTree) reflecting paths structure --> a subpath of a given path into the GH_Structure would be a subnode of a node into my equivalent tree.

For example, if the GH_Structure contains paths {0},{1},{1,0},{1,1},{2,0}, I’d like the tree to have three top nodes : {0},{1} and {2,0}, and two subnodes of the node {1} : {1,0} and {1,1}.

Is there any simple method to generate such a tree from a GH_Structure? I found the GH_Path.IsAncestor function and I feel it can be used recursively but so far I didn’t manage to put things together.

Thanks for your help


(David Rutten) #2

There’s no easy way in the sense that it’s already possible. You’ll have to write the code for it. It’s typically not that difficult to make trees in programming though, so you’re going to have to start deciding what sort of details you’re looking for. Is it supposed to be super fast? Is your tree structure going to be mutable or not? Do you want the leaf nodes to store lists of data, or do you want one node per item?


(Nathan 'jesterKing' Letwory) #3

Do these functions apply to your situation?


#4

Hi @DavidRutten, thanks for your quick answer, as usual.

so you’re going to have to start deciding what sort of details you’re looking for

Only GH_Paths themselves, I think I can define childhood by decomposing them into Indices

Is it supposed to be super fast

Not really

Is your tree structure going to be mutable or not

Not needed, I just want to be able to enumerate through, in a logical top > down order, and get the “distance” to the top node for every node.

Do you want the leaf nodes to store lists of data, or do you want one node per item?

One node per item will be fine since there can never be two identical paths in the same Structure, from my understanding.

It’s typically not that difficult to make trees in programming though

I am sure it’s not, but since I learnt programming by making GH scripts, I may have big knowledge gaps in programming, I beg for your indulgence :slight_smile:

Would you suggest any specific structure to create this path tree?

@nathanletwory, unfortunately no, I barely understand Python but it looks like this component only enumerates paths and put them into a list, but doesn’t provide any relationship between them.


#6

Ok, so for those who would like to do the same thing, here is how I eventually managed. This code looks definately not optimal and it’s not bulletproof but it worked for my specific needs.

First, I created some extensions methods for GH_Path, in a separate class :

public static class GH_PathExtension
    {
        /// Compare two paths, returns true if the initial path is an immediate child of the parent path (like {0,1,42} being a child of {0,1})
        public static bool IsImmediateChild(this GH_Path path, GH_Path parentPath)
        {
            if(path == null) { return false; }
            int generation = 0;
            if (!path.IsAncestor(parentPath, ref generation)) { return false; }
            if (generation == 1) { return true; }
            return false;
        }


    /// Count the number of ancestors (distance to top node) for a given path into a GH_Structure
    public static int NumberOfAncestors<T>(this GH_Path path, GH_Structure<T> structure) where T:IGH_Goo
    {
      if(structure == null || structure.DataCount == 0) { return 0; }
        int i = 0;
      foreach(GH_Path structPth in structure.Paths)
        {
            int j = -1;
            if(path.IsAncestor(structPth, ref j)){ i += 1; }
        }
        return i;
    }
}

Then, I created a node that we are going to use into a tree :

public class PathNode
{
    public GH_Path Path { get; set; }
    public List<PathNode> Children { get; set; }

    public PathNode(GH_Path path)
    {
        Path = path;
        Children = new List<PathNode>();
    }

    /// <summary>
    /// Go through the tree and add a new path-node as a child of the correct parent node
    /// </summary>
    /// <param name="root">root node</param>
    /// <param name="path">path to add as a node</param>
    /// <returns>true if succesfuly added, false otherwise</returns>
    public static bool TraverseAndAdd(PathNode root, GH_Path path)
    {
        if (path.IsImmediateChild(root.Path))
        {
            root.Children.Add(new PathNode(path));
            return true;
        }
        else
        {
            foreach (PathNode child in root.Children)
            {
                if (TraverseAndAdd(child, path)) { return true; }
            }
        }
        return false;
    }
}

At last, you can build the path tree out of any GH_Structure. Keep in mind that we only defined a method for adding nodes as children of existing nodes, never as parents. Therefore, the initial path list should be ordered in a way that ‘parent’ nodes are always inserted into the tree before children. I did that by ordering the list by the ‘number of ancestors’ : paths with the least ancestors go first. I am not sure this will work all the time.

    /// Build a path tree from a given GH_Structure.
    public static List<PathNode> BuildPathTree<T>(GH_Structure<T> structure) where T:IGH_Goo
    {
        List<PathNode> root = new List<PathNode>();

        foreach (GH_Path path in structure.Paths.OrderBy(x => x.NumberOfAncestors(structure)).ToList()) // order paths by the number of ancestors
        {
            if (path.NumberOfAncestors(structure) == 0) { root.Add(new PathNode(path)); }
            else
            {
                bool found = false;
                foreach(PathNode rootNode in root)
                {
                    if (PathNode.TraverseAndAdd(rootNode, path)){
                        found = true;
                        break; }
                }
              if (!found) { throw new Exception("Something went wrong, you shoudn't have a node with an ancestor with no parent node already in the tree."); }
            }
        }
        return root;
    }

Then, you can easily use this ‘PathNode’ Tree to get paths in a logical top-down order --> paths with no parents first, then their childs, then their grand childs, and so on.

Hope this helps :slight_smile: