Monday 24 August 2009

Graph theory and chaos on an extraordinary Friday

It has been such an ordinary Monday it is not worth talking about. On the other hand, Friday, oh we all love Fridays! Nobody really bothers- it is doughnut day, for heaven's sake! So I go with the flow- got to work a little bit late than usual, that is 11 am, and spend half an hour making tea and contemplating on how to improve on a already perfect algorithm. When I finally got to the point where I look at my experimental results, I realized I couldn't be more wrong about it. Thing is, the meaningless combination of numbers I got was supposed to represent a simple graph. Well, almost... it was a graph of some sort, but not a single metric was within 50% of the desired, let alone be a precise match. Here is a bit for the technically oriented among you (please feel free to skip the next paragraph if you are not into graph theory of Java):
~~~~~~ TECHNICAL ~~~~~~
The task is to generate a simple undirected graph with a given degree distribution- initially uniform, Gaussian and exponential, with a potential for easy extension. Also, we should be able to control different graph metrics (mean geodesic path length, clustering coefficient and degree correlation) at least to some extent. My original idea was to generate the degree sequence and construct a graph that corresponds to it. The Erdos-Gallai theorem comes handy here- it provides a necessary and sufficient condition that a sequence of number is a graphic, i.e. the degree distribution of a graph. Problem with that is, I was trying to generate a sequence which precisely describes the degree distribution, and you get stuck somewhere between order and chaos. On one hand, the graph still has to be random, but on the other if you give it “hard” numbers and do not allow fluctuation it is really hard to get anything. Cool, huh? No need to reinvent the wheel though, a quick search and you get your hands on a number of clever AI-inspired algorithms to do the job for you.
Unfortunately, I could not make any further progress on this project, since I accidentally discovered requirements mismatch in my previous project (the programming one). I (very conveniently) ignored the bit that said “let the user play around and interact with the program to see what happens if...” and replaced it with a textual description of the process. Still does the job, but not very educational :D. A bit later on, I realized my listener uses the rather simple SwingUtilities.isRightClick() to decide whether to show the context-sensitive menu or not, BUT there is no such thing as a right click on the Mac. The pop-up trigger is left click with a CTRL_DOWN_MASK bitmask. Well done, Apple, elegant, but don't you think that is convenient to have a normal right click like everyone else does? So right now I have no idea how to get around this little complication, especially given that ctrl+click is already mapped to an action.
~~~~~~END OF TECHNICAL BIT~~~~~~
Apart from that, life is not going bad at all, given that I've been away from my precious girl for six weeks now. Missing her gives me that extra motivation when training, and I particularly need it when I do it on my own. By the way , running is going quite good, I did a total of about 6 kilometres over the weekend and I can feel my getting stronger with every meter. If only English weather didn't have that annoying habit to get in my way all the time!

No comments:

Post a Comment