Home > Back-end >  How to use Boost's Kruskal MST algorithm on CGAL's Triangulation_3?
How to use Boost's Kruskal MST algorithm on CGAL's Triangulation_3?

Time:11-08

I've been trying to puzzle out how to form edge descriptors for a CGAL Triangulation_3 such that I can use Boost's implementation of Kruskal's Minimum Spanning Tree on that Triangulation.

I have been reading through the reference documentation for a Triangulation_2 (provided enter image description here

You can zoom in on the implications here: VertexListGraph and EdgeListGraph.

I found that I could possibly provide my own implementation for edge descriptors through an adjacency list as shown in Boost's example for a Kruskal MST, but got lost and confused at this step, and didn't know if that would be a sufficient approach.

It would be fine to show your attempt as a question, because it would help us know where you are stuck. Right now there is really no code to "go at", so I'll happily await a newer, more concrete question.

CodePudding user response:

Do you want the graph of vertices and edges, or the graph of the dual, that is the tetrahedra would be BGL vertices and the faces between tetrahedra would be BGL edges?
For both it is not that hard to write the specialization of the graph traits class and the some free functions to navigate. Get inspired by the code for the 2D version for the graph_traits

  • Related