Second (to none) Log: I will not be dealing with coordinated graphs!

Welcome back to another episode of Carls Cooking Colosseum, todays specialities are pretty pictures of something that can be mistaken for work. Since my last blog entry, I have concentrated my efforts on physical and existential work as a ground for my future research.

A Start

A static 3D cube using cartesian coordinate's was created. An easy start but necessary to get used to programming with JOGL again. Each vertex's coordinates were calculated beforehand and hardcoded in, represented as spheres. Edges are implemented using cylinders and moved into place manually. This was then improved to have an algorithm to program anything providing their coordinates were input into an ArrayList (a form of vertex list).

This is a very simplistic model/algorithm and is probably as far from real graph drawing as you can get, however, it enabled me to think of how parts of a fully functional algorithm may work, such as the input of data which is not convered in the paper "A multilevel algorithm for force directed graph drawing".

Input of Vertices and Edges

In the model above, vertices are stored as an instance of a Vertex class (created by myself and not sun.security.provider.certpath.Vertex;) and edges as Edge (again made by myself). Verteices are created by inputing their coordinates, and edges, by inputing the two adjacent vertices (so completely based on a coordinate system as mentioned before).
Since this implementation, research suggests that the most likely form of input for vertices and edges is a form of matrix. Which type of matrix is used for graph-drawing is yet to be researched and discussed with my supervisor, but for now, an incidence matrix will be used (http://en.wikipedia.org/wiki/Incidence_matrix).

Dynamic

After creating a static model, I have begun to think about ways of making graphs dynamic (move and update in real time, such as nodes being added or taken away). At first thought, a java animator can be used with a thread to update every few milliseconds, or a polling system to update whenever a new node is added. The paper by Todd L. Veldhuizen "Dyanmic Multilevel Graph Visualisation" mentions use of a 'key frame' which is updated and displayed for every change, though this is not fully understood. Once again further research is needed (I'm starting to understand why this is called a Research Degree).

Additional Reading
Having now created a play toy to test my newly discovered powers upon, my next port of call is several more papers;

• "Graph Drawing by Force-directed placement" - Fruchterman and Reingold 1991
• "An Efficient Heuristic Procedure for Partitioning Graphs" - Kernighan and Lin 1970
• "Efficient and High Quality Force-Directed Graph Drawing" - Yifan Hu 2005
• "A childs guide to drawing" - Old McDonald 1876 (if i get stuck badly)
  

As promised, the pretty pictures:

The easiest of easiest; a 3 dimensional wire cube plotted out.

The same cube, plotted using an algorithm and a drawLine() method to draw lines between two plotted points (as opposed to just moving a cylinder there by trial and improvement). It looks worse but until I find a new way, this will have to do.



A random 3D graph to test coarsening on, until I got stuck with the way I was inputing data and realised that I won't be dealing with coordinated graphs. I may still test coarsening on it to see what affect multi-leveling can have on a coordinated graph system.

Once again, thats all folks! Look out for my next update!