32leaves.net

Spectral graph drawing

Whenever I attend a lecture about some topic, I tend to gather some more information about that particular field than the lecture itself provides. This time it’s about graph theory. While I was reading about graph drawing algorithms, I stumbled upon something called spectral graph theory [2]. In order to get the idea of what this is all about, I started looking thru the presentation on spectral graph theory [2] and reading a few [15] papers [8] on this topic.
Note: Please forgive me my formal imprecision. If anyone feels “offended” by this, she might want to read the papers instead.
The basic idea behind all this theory is to compute the eigenvectors [5] of the laplacian matrix [6] of a graph. Then sort the eigenvalues in ascending order (thus the eigenvectors are sorted, too). Then if

    \[v_0,\dots,v_n\]

are the eigenvectors and

    \[\lambda_0,\dots,\lambda_n\]

the according eigenvalues of the laplacian matrix of the graph

    \[G = (\{k_0,\dots,k_n\}, E)\]

sorted that

    \[\lambda_m \leq \lambda_{m+1}\]

,

    \[0<m<n\]

, the position vector for vertex

    \[k_i\]

is

    \[\begin{bmatrix}v_1(i) \\ v_2(i)\end{bmatrix}\]

where

    \[v_k(i)\]

denotes the

    \[i\]

th component of the eigenvector

    \[v_k\]

.

Due to reasons explained in the papers [15] [8] this method of graph drawing tends to draw the graph planarily [9]. Thus large graphs (especially mesh graphs) tend to look pretty good if drawn like this.
Heaving understood the theory (at least most of it), I wanted to try things out. So I got some test data [10], wrote a small ruby script which converted the PARTY format [11] (or at least a subset of it) into a text-based matrix format, so that Octave [12] was able to read the ajency matrices [13] of the graphs. Let

    \[D\]

denote the degree matrix [14] of the graph and

    \[A\]

the adjency matrix, then the laplacian matrix is

    \[L=D-A\]

. Now we may calculate the eigenvectors of

    \[D\]

. The Octave code below loads some graph’s adjency matrix in text format and calculates the (first three) eigenvectors of the laplacian matrix (basically taken from [15]):

1
2
3
4
load graph.txt;
A = sparse(graph);
L = diag(sum(A)) - A;
[v,d] = eigs(L, 3, 'sm');

Then I plotted the graph using gnuplot (to be more precise: using gplot, Octaves built-in graph plotting functionality). The result was already pretty pleasing:

crack_graph

But I wanted things to look better, so I wrote a MEX file [16] which plotts graphs using OpenCV [17].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include "mex.h"
#include <opencv/cv.h>
#include <opencv/highgui.h>

#define SCALE  40000
#define IN_ADJ prhs[0]
#define IN_XY  prhs[1]

#define min(x,y) ((x) < (y) ? (x) : (y))
#define max(x,y) ((x) > (y) ? (x) : (y))
#define XY(i)    (int)((xyOffset + xy[i]) * SCALE)

void mexFunction (int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) {
   
    if(nrhs < 2) mexErrMsgTxt("expects two parameters: adjency matrix (sparse, n times n), xy vector (n times 2)");
    if(! mxIsSparse(IN_ADJ)) mexErrMsgTxt("Adjency matrix must be sparse");
    if(mxGetM(IN_ADJ) != mxGetN(IN_ADJ)) mexErrMsgTxt("Adjency matrix must be square");
    int n = mxGetN(IN_ADJ);
    int nz = mxGetNzmax(IN_ADJ);
   
    if(mxGetN(IN_XY) != 2 || mxGetM(IN_XY) != n) mexErrMsgTxt("XY vector must be (n times 2)");

    double *xy = mxGetPr(IN_XY);
    double *adj = mxGetPr(IN_ADJ);
   
    // get dimensions
    int i, j;
    double xyOffset = 0, maxX = 0, maxY = 0;
    for(i = 0; i < n; i++) {
        if(xy[i] < xyOffset) xyOffset = xy[i];
        if(xy[i] > maxX) maxX = xy[i];
    }
    for(i = n; i < 2*n; i++) {
        if(xy[i] < xyOffset) xyOffset = xy[i];
        if(xy[i] > maxY) maxY = xy[i];
    }
    xyOffset = -xyOffset;
    maxX += xyOffset;
    maxY += xyOffset;
   
    mexPrintf("img size: %i x %i, xyOffset: %f, maxX: %f, maxY: %f\n", (int)(maxX * SCALE), (int)(maxY * SCALE), xyOffset, maxX, maxY);
    IplImage *img = cvCreateImage(cvSize((int)(maxX * SCALE), (int)(maxY * SCALE)), IPL_DEPTH_8U, 3);

    int *ir = mxGetIr(IN_ADJ);
    int *jc = mxGetJc(IN_ADJ);
   
    int total = 0;
    CvPoint p1, p2;
   
    for (i=0; i<n; i++)  {
        p1.x = XY(i);
        p1.y = XY(n + i);
       
        int starting_row_index = jc[i];
        int stopping_row_index = jc[i+1];
        if (starting_row_index == stopping_row_index) continue;
        else {
            for (j = starting_row_index; j < stopping_row_index; j++)  {
                p2.x = XY(ir[j]);
                p2.y = XY(n + ir[j]);
               
                cvLine(img, p1, p2, cvScalar(255,128,255,0), 1, CV_AA, 0);
               
            //  mexPrintf("\t(%d,%d) = %g || (%i %i) -- (%i %i)\n", ir[j]+1, i+1, adj[total++], p1.x, p1.y, p2.x, p2.y);
            }
        }
    }
   
    if(!cvSaveImage("/tmp/gr.png", img)) mexErrMsgTxt("Unable to write /tmp/gr.png");
    cvNamedWindow("mainWin", CV_WINDOW_AUTOSIZE);
    cvShowImage("mainWin", img );
    cvWaitKey(20);
   
}

That code was used to produce the following graphs (except for the blue one, my WordPress simply can’t exclude images in a gallery):

With something looking that cool in my hands, I simply had to create posters out of that. So I postprocessed two graph images and ordered prints (the two black and white images). That stuff is fun, and extremly interessting. I’ll for sure do some further investigation on this topic.

References

One Response to “Spectral graph drawing”

  1. Malik says:

    I tried to compile your code using OpenCV, but unfortunately it does not working since mex.h is no defined.

Leave a Reply

Fork me on GitHub