My assumptions were wrong? So much surprise...

So following on from the development of the Visual MGF framework, I have spent the past 3 days playing with investigating the abilities of the application and how much I can change, and inevitably, how does whatever I change affect the layouts of the graphs.

The biggest changes so far come from adding variables to give priority to one of the cooling schedules (to either repulsive or attractive forces). Changing this has allowed me to find some preliminary values which provide good global layout more often for most graphs (a problem described in previous posts). The bad global layout had to be for a reason though (treating the symptoms is only one thing), so investigation led me to think "lets spice the pretty pictures up with some colour".

So, a few hours later, here I am with the ability to colour the graphs, highlighting each of the matchings of vertices. So highlighting the two collections of vertices which make the coarsest graph, gives the following picture (for the graph 55grid/3025).

Notice that one of the "partitions" is much larger than the other, this sometimes happens due to the random nature of the matching process. You may also notice the crease in the layout between the two collections - interestingly this has been observed previously when I first implemented Walshaws multilevel with standard grid approximation, and shows that the global repulsive force is not pushing the two collections apart (and as such, the two collections overrun and crease). This suggests either changing the value of the spring length (k) to something more appropriate or copying the fix on the previous work and changing the strength of repulsive forces.

Either way, that is only slightly interesting. The more interesting, and sadly more disturbing news comes from observing some of the matchings that occur. The following image shows matchings on the same graph but in at a different (coarser) level in the multilevel scheme.

The image shows that some matchings include a large number of vertices stretching out across the graph. Previously I have made the assumption that matching connected vertices means the graph should be matched into reasonably uniform partitions. Apparently, this is not the case, and as such, the global layout is often skewed so that the larger partitions occupy more space than others.

This is due to abandoning the priority given to lesser connected vertices. Changing this should provide more appropriate partitions and generate a more uniform global layout. Shows the use of this blog, I only just thought of that as being a problem - might have ignored it otherwise, so thank you blogger!