How to implement algorithms such as QEM

[Mochimazii]

hi，I am trying to implement the QEM with cinolib, here is my question I stored vid pair to collapse in the priority queue like this

struct contract {
    double cost, x, y, z;
    unit vid1, vid2;
}

I noticed that when deleting elements, the switch_id function will execute, causing the element id switch with last id, rendering the contract operation related to the last vid invalid. How can i solve this problem

[mlivesu]

correct. when you delete mesh elements the ids will change, so you can no longer trust that information. there are multiple ways to overcome this issue. The first one that comes to my mind is to keep an external vector that maps initial vertex ids with current vertex ids. At the beginning of the algorithm the vector is just the identity function (i.e., v[i] = i for each vertex i in your mesh). Any time you delete a vertex by edge contraction you need to update this information, by decreasing all the vertex ids that are higher than the id of the vertex just deleted (and maybe setting to -1 the value of the vertex being deleted). With this additional structure any time you pop an edge from your priority queue you just need to check the current id in the map/vector

[Mochimazii]

got it, thanks very much for your reply.