[FEAT] KD-Tree

[eloimaduell]

Feature Request

Not sure if this is a feature request or just a comment / question on how I'm using graaf or how should I use it.
I'm not a super expert on C++20, so the code it's not easy to read/understand for me...

I'd like to be able to navigate the Minimum Spanning Tree resulted from Prim's... I'm used to deal those kind of graphs by a "tree" data structure (KD-tree?) where i can start navigating from a leaf of the tree and then I can go to adjacent vertexs and navigate it in a custom way. Maybe this is already possible with graaf, or maybe it's totally non-sense, again, i'm not an expert on graph theory.

I'm using graaf to make some experiments related to a laser+sound show that we're developping in my studio : https://www.playmodes.com/home/astres/ . We're pointing and mapping a laser scanner to the night stars and we draw on top of them. As the sky is always moving, we have some methods to get the star coordinates inside the field of view of the laser, then i create a Delaunay triangulation and build an undirected graps from it, then I apply the EMST to get a "figure/graph" that contains all the stars and some edges, as this is a way that we create generative constellations.

Why is this important?

In my case it's important that the Resulting Minimum Spannig Tree it's easy to navigate in a custom way, accessing to leafs and then moving on to the tree structure. But, as said, maybe this is a very "personal" approach that doesn't apply to the scope of this library....

Describe the solution you'd like

that I can get as a result of the Prim's algoritm a Kd-Tree data structure.

Describe alternatives you've considered

As far as I can tell, the info I can get from a Prim's MST are a vector of the vertices and a vector a vector of the edges, without any morphologic information.

Additional context

Are you willing to contribute?

I'm not able to code in such a way as you do in graaf, sorry.

Checklist

Please check the following before submitting the issue:

• [ x] I have searched for similar feature requests in the issues.
• [ x?] This feature is not already implemented in the library.
• [ 1/2] I have provided a clear and concise description of the feature request.
• [ x] I have explained why this feature is important and how it benefits the library and users.
• I am willing to contribute to the development of this feature (if applicable).

Please note that feature requests are subject to review and may or may not be implemented in the library.

[github-actions]

Hi there! Thank you for creating your first issue on the Graaf library, we will look into it shortly. In the mean time, please make sure the issue has the correct labels set.

[bobluppes]

Hi @eloimaduell, thank you for sharing this feature request with us. I had a closer look at your project and it looks awesome! Really cool to hear about your experimentations with Graaf, we would love to work together on this feature as I think your project is the perfect use case for our library.

I'd like to be able to navigate the Minimum Spanning Tree resulted from Prim's... I'm used to deal those kind of graphs by a "tree" data structure (KD-tree?) where i can start navigating from a leaf of the tree and then I can go to adjacent vertexs and navigate it in a custom way.

In general any graaf::graph can be traversed in a "custom" way. For examplex, see the BFS and DFS implementations in algorithm/graph_traversal. However, this requires the return value of Prim's algorithm to be a graph class, which it currently is not. I think it should be possible (and desirable) to change the return type of this algorithm such that it can be more easily consumed.

I am not too familiar with KD-tree's myself, but I wonder if this is something which can be "implemented" on a normal tree data structure by assigning special node and edge values. Maybe by restricting a node to two child nodes (binary tree) and assigning Euclidian distances as edge values?

For your project, would it work if we implement a tree data structure (which is a specialization of a graaf::graph) and return that from Prim's algorithm? That would allow you to do a custom traversal starting at either the leaves or root of the tree.

[eloimaduell]

Hi @bobluppes ! Thanks for taking in consideration our needs ! So glad !!
I'm not 100% sure what is the best way to implement such feature, but I'm quite sure that having a tree data structure as a result of applying algorithms would allow us to do custom traversal's or other ideas that we have in mind in the context of our project. I stated kd-tree, but I guess whatever data structure (not sure if kd-tree is limited to binary trees? so that each vertex can only have maximum 2 adjacent vertices, where we would like to be able whatever number of adjacencies given any vertex) that can host vertices, edges and methods to travel throught it should be enough. In our case we would need to choose where do we start to navigate / traverse the graph, and from there having adjacency list of each vertex should be fair enough. Could we help in something for this hack/feature ? Let us know if we can help in anyway ... Open to have a direct communication too through email or so ...

[eloimaduell]

Hi again, so today playing with the result of Prim's, trying to understand what is the order that the edges are returned, i found no specific order...

As you might see on this screencapture, I'm painting the vertices of an EMST and also the edges in the order that I get them from the Prim's result. And it seems that the order of the edges doesn't follow any "usual" traversing order right ?

I imagine that with the new feature that you have proposed those algorithms returning a tree structure (as a specialization of a graaf::graph as you mentioned), we might be able to apply traversal algorithms (for example to a resulting EMST tree) and develop new traversing algorithms right ?

[bobluppes]

Thank you for the elaborate reply!

In terms of working on this, I would propose that I implement a (prototypical) tree class which we can return from Prim's algorithm. If you are available to collaborate I think it does make sense to take a closer look at your use case, as I want to make sure that this feature closely fits your needs (and hopefully future use cases as well 😄). You are more than welcome to join our discord and we can discuss your use case further if you are interested.

Logistic wise, introducing these changes means bumping a major version. So depending on how you include the Graaf dependency in your project I would provide a separate build artifact for you to try out. Once we are confident that the changed interfaces are mature enough I will include it in the next release of Graaf.

[bobluppes]

Hi again, so today playing with the result of Prim's, trying to understand what is the order that the edges are returned, i found no specific order...

Very cool to see your experimentations with the library! There actually is a specific order in which these edges are returned, but it is an implementation detail of the algorithm. As such I would not depend on it. But as you also stated, the order is not very useful now anyway.

I imagine that with the new feature that you have proposed those algorithms returning a tree structure (as a specialization of a graaf::graph as you mentioned), we might be able to apply traversal algorithms (for example to a resulting EMST tree) and develop new traversing algorithms right ?

Indeed! What I am currently thinking of is to implement a tree class which derives from graph. Apart from the usual methods (most notably get_neighbors), it then also provides the means to access the root and leaf nodes of the tree. In general I think this should allow us to implement any traversal algorithm on the result.

[eloimaduell]

Just joined the Discord channel :) Let's continue there maybe ? I'm ok on working in a protoype way ... whatever it's more convenient for you. I can collaborate trying to express what might work for our use case, trying, debugging etc ... I'm using XCode and my projects are usually build as Openframeworks (http://www.openframeworks.cc) does ... As Graaf is header only it was quite easy to include the sources and it just worked. You know much more about the proper way to develop this feature and how to make it match you repo ... I'm ok if you send files and I just try them ... or whatevert ... let me know what might be better or more convenient for you and I'll try it. Excited !!

[github-actions]

Marking this issue as stale. It will not be automatically closed.

Even though the maintainers of Graaf may not always have time to take a look in a timely fashion, your contributions are much appreciated.
Please allow some time for @bobluppes to take a closer look.