An algorithm for drawing general undirected graphs
LINE and Circle drawing techniques using OpenGL
I present here the standard way of drawing lines and circles and then using them to do something crazzy! Well It was a part of my computer graphics assignment and I thought it would be really nice if I blog about it a bit.
So the tasks involved are:
Implementation an automatic graph drawing algorithm for general undirected graphs. The final positions of the points of graph will be denoted by small circle and the edges will be shown as straight lines. The lines will be drawn using Bresenham’s line drawing algorithm and circles will be drawn using midpoint algorithm.
Finally, implemented the Journal paper “An algorithm for drawing general undirected graphs” by Tomihisa Kamada and Satoru Kawai. The paper talks about drawing undirected graphs using virtual dynamic systems in which every two vertices are connected by a “spring”.
Task 1: Implement Bresenham’s line drawing algorithm for any arbitrary line segment.
This algorithm is implemented in the linedraw function that is written in the code here the exact same algorithm is implemented that we have done in the class and the current and final x,y positions are chosen by left click of the mouse button using the key listners of GLUT lib.
Task 2: Implement Midpoint circle drawing algorithm.
We have implement the bresenham's algorithm of circle drawing again, we focus only on one octant and rest is drawn by the swap method. here again the circles are drawn on the left click of a mouse.
Task 3: Implement the above given algorithm (from the paper) and use the line drawing routine from Task 1 and circle drawing routine from Task 2 to make the edges and nodes respectively. It is desired that the input nodes can be given interactively on the screen.
what is happening in the code is that we first start by plotting points on the GLUT canvas, these points are selected and a circle is drwan around them using the midpoint circle drawing algorithm. Next on a single right click, the control is now shifted to selectng the start and end points of the bresenham's line drawing algorithm. After the user has drawn the necessary lines he/she performs a right click and the algorithm is executed and the output of iterations is shown. note, in the first right click we perfom 30 iterations together at one go to give the desired results quickly. We start our algorithm with the kamada function. We have a set of points and a graph connectivity, the information of which is stored in the dist[N][N] array, where N is the number of points plotted. Initially all the elements that have same position are assigned 0, i.e. dist, dist..dist[n][n] are all zeros; other array elements are assigned some high value (considered infinite) as 1000; after this the control is given to the flyod function to calculate the flyod shortest path for each of these points in dist matrix here happens the reduction of the weights/delta values of the dist matrix, basically it finds the direct and indirect connectivity between the points. Now the vertices that have a direct connectivity are given the value 1; for example if there is a connectivity between the points AB, BC, CD & DB (not between AC), then in the matris dist the position corresponding to these points will have a value 1 and rest will be 1000; next the indirect connectivity is checked and given a weight of 2 beacause there are two edges that needs to be traversed to get to the start point to end. Like in the above example there is no connectivity between A-C but there exists an indirect connectivity, i.e. from AB to AC; hence the matris positon corresponding to 'A' row/column and 'C' row/column will get a value 2 (earlier 1000). Similarlly the entire dist matrix is refined with new deltas that correspond to coeffecints that give us the connectivity between all the points. dist would look something like this:
* A B C D
A 0 1 2 1
B 1 0 1 1
C 2 1 0 1
D 1 1 1 0
After finding the flyod shortest algorithm matrix, we find the 'l' & 'k' values as given in the paper, we compute these for each of the points present seperately using: lij = L * dij L = Lo / max(dij) kij = K / (dij*dij) K and Lo have been given some constant value by us. After computing l and k values we go on to find delta; for that we need to compute the dex, dey values which are found directly by calling seperaate finddex and finddey methods which implement the set of equations mentioned in the paper by using basic for loops and arithemetic operators with the condition on k & m. the progress is then as per the paper and we find the maxdelta from the deltas computedd above. now is the core part of the algorithm wherein we compare this maxdelta value with a predefined constant EPSILON. EPSILON is the judgment factor of accuracy/correctness/error free parameter that is set to a random small value. this parameter controls the stiffness or turbidity of the graph; so while our deltamax and currentdelta values are more than EPSILON we say that iterations will happen to reach an optimum energy value for each coordindate. to update the coordinates on satisfying the EPSILON condition, two new parameters needs to be computed, these are nothing but the second order derivates of energy which are denote by the variables. to do that we break the equations of the paper into smaller computations of 'aa' 'bb' 'cc' 'dd' 'ee'. finally we compute the double derivative in terms of these intermediate computed values. Now the x and y coordinates are updated as: currentx+=dx; currenty+=dy; corner[current].x=currentx; corner[current].y=currenty; All this is done for each of the points plotted by the user.
Okay now lets see the video for it: