Getting Settled

This week has been a blast, I have done quite a lot of reading, experimenting with matrices and understanding the coarsening and uncoarsening algorithms, most noticeably my latest research topic has been to find how to see if a graph (set of vertices and edges) is disconnected or not.

This topic did not show itself before, however, its importance has been realised. If a graph is disconnected (so have a graph of two main disconnected partitions for example), the global forces on one can or can not affect the other, so most philosophers have designed their algorithm for either only fully-connected graphs or disconnected graphs.

The aim of my research here (well not research, but my mental action) was to find a method of looking through a graph's data and finding how many disconnected graphs exist, if any. This is relatively easy until you have to take into account the efficiency, which more than often results as O(E^2) where E is the number of edges. This was less efficient than my supervisors algorithm of O(E), and instead of reading up (y'know, like I probably should have done) I decided to try and get the algorithm to this efficiency alone.

After a long battle with it, and the introduction to the Chaco file for holding information regarding vertices and their adjacent neighbours, I have (hopefully) managed to get it to O(E). The theory being, when a chaco file is read, the vertices are given a graph number indicating which graph they belong to. If all the vertices are connected, then they are all for graph 1, however if they are not, they are given different graphs. Describing it here does not do the theory justice, however, I will add my sudo code here when I have transcribed it from my scibbles of notes (with my working Java source code).

Other events this week include helping the University's Computing and Mathematical Sciences Mentor team, with tasks such as helping the new students find their way around, giving them information and handing out sweets. Another event, also involving the CMS Mentors, was helping new CMS students use the computer labs, and advising them when needed, which included a brief introduction to NetBeans and programming Java (much like I expect I will be dealing with in my tutoring).

This is all a bit rushed so expect corrections and additions when I read over this!

Thanks for reading and remember, work is fun!