Advice for data container / structure

[alexas]

Hello

I have some sort of branched data structure, see the image:
https://ibb.co/TPMMfYb
Basically every branch is the std::vector with set of coordinates in 3d space.

Every branch must maintain its relation with other branches. By selecting any branch, I would like to:
- be able to identify the whole structure, i.e. copy all vectors that belongs to this structure the selected branch belongs to
- be able to divide the structure in any place, so the both parts would preserve the structure,

I would like to get any advice what container could be most useful for this. I am trying to do this with nested vectors, but it becomes too complicated soon

Thanks,

[jonnin]

I would say that "so far" with only these basic requirements you need
- a container of stuff
- a container viewer class

the container can be a STL container or something you cook up, but its basically a pile of your 'node' classes which appear to contain the 3-d vector data + a pointer back to the owning container. That sounds odd written down.. but say you put all those nodes in a vector, then vec[0] is a node. that node had the 3d data as a field, and another field that is a vector<node>* that is a pointer back to the 'vec' variable, see? that gets you home, so any branch (node) can get to the whole original data structure.

the viewer is similar. the viewer is a container of pointers (back into the vec container) to the nodes. It may be a struct, with the pointer and something else like a pointer back to the viewer container, so if you split the original into 2 parts, then split one of the parts into 2 more parts... you can track all those splits in the viewer objects you create via the pointers back to themselves.

that means your splitting function needs to work on both the original container and the viewer container, but no other function will need to cross that line.

I know that all sounds complicated on paper but in reality you are just storing groups of pointers back to the original container that splits the data up as you need it, without really moving it or copying it or any of that.

it seems likely that if you have a split, you need a join.

[alexas]

Hmm thanks. Unfortunately yes, for me it sounds complicated.
What if I need the copies, not the pointer to original ones?

[newbieg]

I was expecting the classical argument between Search Trees and Hashtables to pop up. https://youtu.be/hqIjbDR0gWk?t=284
But I have also heard many today try to keep everything in vectors because it's easier to pass it to the GPU that way, and the GPU handles rotating/transforming the objects... So is the GPU going to come into play on your system?

Are you planning on using OpenGL or DirectX? Or is the plan to keep everything in CPU?

https://www.youtube.com/watch?v=ZlNnrpM0TRg
https://www.youtube.com/watch?v=vlD_KOrzGDc

[kbw]

Isn't this good enough?

struct Node {
    std::vector<Node*> nodes;
};

[alexas]

I still did not reach that level , at the moment everything will run on CPUs.

Hashtable, i.e. unordered_map looks like really suitable choice, just now need some good thoughts how it should be implemented to represent that bush-tree like structure.

[alexas]

@kbw:

Could you please give a link to some example, how actually it can be used? Have little experience in such,

[jonnin]

I can't decide... is there a valarray use here, something like
https://en.cppreference.com/w/cpp/numeric/valarray/indirect_array

to split it up for you? This is also very like what I was trying to say with the 'view' idea.
it has a micro example.

[kbw]

@kbw:

Could you please give a link to some example, how actually it can be used? Have little experience in such,

Your "branched data structure" just looks like a tree with many trees hanging off each branch.

A binary tree would be something:

template <typename T>
struct BinaryTreeNode {
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    T data;
}; 

Your's just has lots of nodes hanging off each node, more specifically, each node has an ordered set of nodes. So each node can be defined as:

template <typename T>
struct Node {
    T data;
    std::vector<Node*> nodes;
};

You then have to define data and methods around that, and probably package the whole thing in a class. But that's an exercise for the reader.

Your data would be, and start of pointing to nothing:

Node<T>* head = nullptr;

As for methods, that depends on how you want to use it. For example, find might be:

template <typename T>
Node<T>* find(Node<T>* tree, const T& data) {
    if (!tree) return nullptr;
    for (auto node : tree->nodes) {
        if (node->data == data)
            return node;
        if (Node<T>* ret = find(node, data))
            return ret;
    }
    return nullptr;
}

[newbieg]

I'm leaning toward the search tree approach too since you want to retain order and connection to parent nodes.
Anyone know any graph theory that might help here? I'm a bit too rusty on that stuff.

[alexas]

@kbw:

I am trying my best to grasp this. I am always very slow when I see recursive things with pointers, unfortunately ( or at least it looks like that).
Ok so each node hold pointers to other nodes + the data object which belongs to that particular pointer.
so let's assume I have the group of the 4 objects: std::vector<Branch> group = {a,b,c,d).
The a should link to b and c, while c should link to d.
I would need at least to understand how to set them, and how to get them, from there I maybe could be able to move forward.

struct Node 
{
    int index;
    Branch* ptr_branch;
    std::vector<Node*> nodes;
};

//so the class description could be:
class Branches
{    
     unsigned long long _identifier;
    Node _node;
    std::vector<Branch> _branches; // I specifically need to have like that, i.e. the actual 
                                                     objects must be in the separate vector
}

// Never worked with structures/pointers that links to itself. How exactly should I set_node and get_node?

[jonnin]

there is missing info... how do you know its the structure you said, vs a link to b, and b has c and d both as children?
there is a rule to set this for a binary search tree, but I am not convinced that is what you have. Do you have rules to decide how to build it? You must!

[newbieg]

I think we need some more details of what you're wanting to do. Here's some macro thoughts, a bit off topic but things that might be interesting as follow up.

If you are thinking about raytracing or collision detection between 3d objects, then I think BVH (Bounding volume hierarchy) might be worth researching.
https://en.wikipedia.org/wiki/Bounding_volume_hierarchy
https://www.youtube.com/watch?v=BK5x7IUTIyU

If the user is likely to modify the data model, you might want to think about behavioral/command patterns, which would allow undo and redo actions while building the data. (https://www.youtube.com/watch?v=ILgiCy6IXLw).

Do you need to determine if one graph is the same as another but moved and rotated? Or perhaps if a portion of one graph is matched in a portion of another? Perhaps identify if both graphs are in fact partials of a more complete object? -> https://www.youtube.com/watch?v=BK5x7IUTIyU

Can we get some more information about what the goals are for the program and the data?
What types of actions are you expecting to take with the 3d points?
Are these points static or likely to move over time?
What do these points actually represent?
Does the distance between the points have any functional meaning?

[kbw]

I confess, I don't really understand how various nodes can be related in your "branch" strategy.

Can you provide some context, possible describe what you're trying to achieve? Maybe that'll help.

[newbieg]

@kbw: without further information, I think your first post is the best approach. Allow each node a vector of children nodes.
https://www.youtube.com/watch?v=qH6yxkw0u78
Just create a basic tree and get things running, optimize from there as needed.