In a bid to keep future posts as short as possible, I am trying to update this more often. As far as can be told, the algorithm for determining disjoint graphs works with what I now to believe O(|V| + |E|) at worst. Too much time has been spent on this so moving on.
I very much enjoy Fruchterman and Reingold's method of modelling particle physics, and thought about how I could utilise some physics myself, such as Entropy as a cooling method and global force acting on every vertex, instead of the annealing method used by Walshaw and Veldhuizen. This obviously needs more research and may prove to be less efficient, then again, it may not, we cant know until we try (or see if anyone else has done it).
Need to do more research on Todd L. Veldhuizen's Dynamic Multilevel Graph Visualisation to see how his algorithm acts on large changes higher in the vertex list (so whilst others are added, what happens if a large number of original vertices dissapears).
Wednesday, 29 September 2010
Tuesday, 28 September 2010
Another Day, Another Planet
A shorter blog entry this time if it can be helped, having found a method of checking if graphs are connected or not and keeping the efficiency of said algorithm to a minimum O(|V|) at best, the next step included some testing to check if it works, and so, some assumptions have to be made in order for success.
1. The file input should be in the "Chaco" format (NB to self and advise to readers: find original source for this file type, might be useful)
2. The file input is read in the correct order, so the first vertex read in is vertex 1, 2nd is 2 and so on. Disruption of this order may cause some undesired or unexpected issues (as far as can be told, if the rule above holds, this should not be an issue as chaco files tend to be in the correct order)
3. The vertices are in order, so for part of a disjoint graph Ga = Va; Va { v1, v2, v3 } and Gb = Vb; Vb { v4, v5, v6}, the vertices are in some kind of order, whereas if Va { v1, v4, v2} and Vb {v3, v5, v6}, this may cause some unexpected issues.
More on these assumptions and rules after some more research and testing. The algorithm I'm using is actually a variant of the breadth-first search algorithm. I am also aware of Menger's theorem.
NB: Yesterday (Monday 27th was my first Tutorial, 2hours with group 6, and 2hours with group 10), not of interest to you readers but its always good to have somewhere to look up things in case something goes missing.
1. The file input should be in the "Chaco" format (NB to self and advise to readers: find original source for this file type, might be useful)
2. The file input is read in the correct order, so the first vertex read in is vertex 1, 2nd is 2 and so on. Disruption of this order may cause some undesired or unexpected issues (as far as can be told, if the rule above holds, this should not be an issue as chaco files tend to be in the correct order)
3. The vertices are in order, so for part of a disjoint graph Ga = Va; Va { v1, v2, v3 } and Gb = Vb; Vb { v4, v5, v6}, the vertices are in some kind of order, whereas if Va { v1, v4, v2} and Vb {v3, v5, v6}, this may cause some unexpected issues.
More on these assumptions and rules after some more research and testing. The algorithm I'm using is actually a variant of the breadth-first search algorithm. I am also aware of Menger's theorem.
NB: Yesterday (Monday 27th was my first Tutorial, 2hours with group 6, and 2hours with group 10), not of interest to you readers but its always good to have somewhere to look up things in case something goes missing.
Wednesday, 22 September 2010
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!
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!
Wednesday, 15 September 2010
"Oh dear! Oh dear! I shall be too late!"
A bad start to a degree but we all miss some deadlines. The reason for my lateness is due to the business of the past few days, so work had been put on hold, however, it is now continued and all is right with the universe again.
Monday(Excuse 1) [13/09/2010]
Mondays schedule started early, with a 5.00am wake-up and a nice 2hour 30minutes journey to Greenwich. A general meeting between tutors and more admin work were carried out throughout the day. The good news is, I now have a work-related laptop (instead of using my own), I will be moving into University Maintained Accommodation this coming week and I am now officially a "staff" member (though I use this term loosely).
Though the activities of the day only took 3-4hours, the travel took up much of the day so I could only spend my limited amount of time research a paper by Yufan Hu (more details regarding this in the next blog entry).
http://math.nist.gov/MatrixMarket/ - a new link found by the paper which will answer many of my questions and may give me some useful testing data.
Tuesday(Excuse 2) [14/09/2010]
Once again an early get-up, for today, is the day, I learn to teach. A wonderful 7hour day (+4hours for travel), at least they supply tea and coffee. Some very cool techniques to help with teaching i.e. using different methods to reach different learners and the importance in good assessment.
The course was very useful to me and has made me a little more confident about what Im walking in to, having faced my fear (of having a class turn against me and maul me to death), whats the worst that can happen.
Though this is not directly related to my research, I am telling you this as an excuse as to why there has been limited progress. On that note, I have read more of the Yufan Hu paper and have found a few more relevant papers, with ideas on where I could specialise my research (however preliminary and unsure they are).
Wedneday(Today! a.k.a Excuse 3) [15/09/2010]
Today was spent mostly at home, however, once again (you guessed it), only a limited amount of work was carried out. This is mostly due to the preparation of moving to Greenwich and clearing my current accommodation of my stuff.
In Conclusion
So far, this week has been very bad for research, but very good for other semi-related tasks as I can now tutor classes, I have access to staff teaching material, my CMS account is activated and as far as I have proven, my emails are correctly sent to me.
The next two days are planned for reading and possibly some coding, so we will see how it goes. My next update will be aimed for Friday evening, if not, See you next Monday!
Monday(Excuse 1) [13/09/2010]
Mondays schedule started early, with a 5.00am wake-up and a nice 2hour 30minutes journey to Greenwich. A general meeting between tutors and more admin work were carried out throughout the day. The good news is, I now have a work-related laptop (instead of using my own), I will be moving into University Maintained Accommodation this coming week and I am now officially a "staff" member (though I use this term loosely).
Though the activities of the day only took 3-4hours, the travel took up much of the day so I could only spend my limited amount of time research a paper by Yufan Hu (more details regarding this in the next blog entry).
http://math.nist.gov/MatrixMarket/ - a new link found by the paper which will answer many of my questions and may give me some useful testing data.
Tuesday(Excuse 2) [14/09/2010]
Once again an early get-up, for today, is the day, I learn to teach. A wonderful 7hour day (+4hours for travel), at least they supply tea and coffee. Some very cool techniques to help with teaching i.e. using different methods to reach different learners and the importance in good assessment.
The course was very useful to me and has made me a little more confident about what Im walking in to, having faced my fear (of having a class turn against me and maul me to death), whats the worst that can happen.
Though this is not directly related to my research, I am telling you this as an excuse as to why there has been limited progress. On that note, I have read more of the Yufan Hu paper and have found a few more relevant papers, with ideas on where I could specialise my research (however preliminary and unsure they are).
Wedneday(Today! a.k.a Excuse 3) [15/09/2010]
Today was spent mostly at home, however, once again (you guessed it), only a limited amount of work was carried out. This is mostly due to the preparation of moving to Greenwich and clearing my current accommodation of my stuff.
In Conclusion
So far, this week has been very bad for research, but very good for other semi-related tasks as I can now tutor classes, I have access to staff teaching material, my CMS account is activated and as far as I have proven, my emails are correctly sent to me.
The next two days are planned for reading and possibly some coding, so we will see how it goes. My next update will be aimed for Friday evening, if not, See you next Monday!
Thursday, 9 September 2010
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;
Once again, thats all folks! Look out for my next update!
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)
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.
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!
Tuesday, 7 September 2010
Beginning of the End of the World (BEW BEW)
Hi, I'm currently studying Dynamic Graph Layout and Visualisation and have created this blog for you to follow and track my progress, beginning to end. The official start for my research course was 1st September 2010, so im already several days behind (blog-wise) so for now, I will add the additional days to this post.
Firstly, a little about me and my work, I am a research student at the University of Greenwich, Maritime Greenwich Campus, in London and have just finished a Bachelors in Computer Science with a 2.1 grade (not great as I was expecting a 1st but we cant all be winners). I'm a video game enthusiast, have an obsession for cats (like most of us internet-dwellers) and I like penny-sweets.
My work is to research into graph layout algorithms, starting with Chris Walshaw's "A Multilevel Algorithm for Force-Directed Graph-Drawing" and Todd L. Veldhuizen's "Dynamic Multilevel Graph Visualization".
Now for my previous entries;
[01/09/2010] - Day Zero
First day as a Research Student took me to Greenwich to meet with my supervisors Dr Chris Walshaw and Dr Alan Soper. I was also introduced to some of the members of staff I may or will be working with, and was able to complete my registration for the course. My new email address and user account was also created (though this needs to be checked), the Research Students and Supervisors handbook printed and the Research Student Log and Professional Development Portfolio also printed. I was also given permission to work from home due to my term-time accommodation not being ready.
Work-wise, I was directed to read through several existing research papers and begin modelling the algorithms for graph drawing (starting with the multilevel force directed approach).
[06/09/2010] - Week Zero
Third day of work, and the start of my first full week in research. Home workstation and software set-up and configured and all research papers required, printed for easy reading. Both Walshaw and Veldhuizen papers have been read (over and over) and physical work has begun.
Following my normal approach to work, I have decided to start at the bottom and work my way to the top, my first attempt being an application to draw a 3D cube frame where each vertex is represented by a sphere and edges, by a cylinder. There is no algorithm in use for now but the aim for this program is to refresh my JOGL programming skills. This should take less than a day.
[07/09/2010] - Project BlogBook.. I mean LogBlog... I mean...
This is literally to identify that this is the day I have started my blog/log book. Articles will/should be submited every few days (maximum 5 working days). Paper articles may also be written and will be attached to the next digital article.
Thats all folks, see you next blog post.
Firstly, a little about me and my work, I am a research student at the University of Greenwich, Maritime Greenwich Campus, in London and have just finished a Bachelors in Computer Science with a 2.1 grade (not great as I was expecting a 1st but we cant all be winners). I'm a video game enthusiast, have an obsession for cats (like most of us internet-dwellers) and I like penny-sweets.
My work is to research into graph layout algorithms, starting with Chris Walshaw's "A Multilevel Algorithm for Force-Directed Graph-Drawing" and Todd L. Veldhuizen's "Dynamic Multilevel Graph Visualization".
Now for my previous entries;
[01/09/2010] - Day Zero
First day as a Research Student took me to Greenwich to meet with my supervisors Dr Chris Walshaw and Dr Alan Soper. I was also introduced to some of the members of staff I may or will be working with, and was able to complete my registration for the course. My new email address and user account was also created (though this needs to be checked), the Research Students and Supervisors handbook printed and the Research Student Log and Professional Development Portfolio also printed. I was also given permission to work from home due to my term-time accommodation not being ready.
Work-wise, I was directed to read through several existing research papers and begin modelling the algorithms for graph drawing (starting with the multilevel force directed approach).
[06/09/2010] - Week Zero
Third day of work, and the start of my first full week in research. Home workstation and software set-up and configured and all research papers required, printed for easy reading. Both Walshaw and Veldhuizen papers have been read (over and over) and physical work has begun.
Following my normal approach to work, I have decided to start at the bottom and work my way to the top, my first attempt being an application to draw a 3D cube frame where each vertex is represented by a sphere and edges, by a cylinder. There is no algorithm in use for now but the aim for this program is to refresh my JOGL programming skills. This should take less than a day.
[07/09/2010] - Project BlogBook.. I mean LogBlog... I mean...
This is literally to identify that this is the day I have started my blog/log book. Articles will/should be submited every few days (maximum 5 working days). Paper articles may also be written and will be attached to the next digital article.
Thats all folks, see you next blog post.
Subscribe to:
Posts (Atom)