More on the graph method

So I thought a little more about how the graph method (number 3 in the list in the last post) works when you are doing edge contractions. In an edge contraction, each pair of faces on opposite sides of the contracted edge gets merged into one face. That means that if the two faces had different edges marked, then you have to switch one of them so it matches the other edge. This can be simulated in the graph method by having an extra node for each of these pairs that has out-degree 2, one going to each of one of the possible switches. The trickier thing is dealing with the fact that there are multiple of these forced switches at the same time. Suppose that on one of the cells we have to do a given marking switch due to the edge contraction, then we propagate it back until eventually we hit another marking switch that we had to make due to the same edge contraction. This means that we have made both of those changes at one time.

When you put it all together this gives an algorithm for the problem:

1. When you create the mesh and initial markings, also create the graph. You also have to update the graph each time you refine, coarsen, or change the markings - but this only affects the cells where the markings were changed so it takes (on average) constant time.

2. When you contract an edge, make a list of all the pairs of opposing faces that don't have edge markings that correspond.

3. While that list still has elements in it:
3a. Do the search process starting from one of the elements in the list (chosen arbitrarily), searching for either (a) one of the other elements in the list or (b) a node with out-degree 0.
3b. Make the edge switches called for by the result of the search, updating the graph as necessary.
3c. Remove the chosen element form the list. Also if the search process ended at one of the other elements in the list, remove that element as well.

This by itself is probably not the best algorithm we can come up with because it is likely to change the same cells over and over, and also looks that each required change one by one rather than considering them all at the same time. But it is a simple algorithm that provides a baseline that we can use as a point of comparison to evaluate more sophisticated options. Probably the next thing I will do is implement this algorithm (not necessarily in the TentPitcher codebase, just a prototype implementation in Python or something) to see how well it works.