This repository includes code for our 2018 Graph Algorithm Building Blocks (GABB) workshop paper Spectral Graph Drawing: Building Blocks and Performance Analysis. Our approaches are based on spectral graph drawing algorithms developed by Yehuda Koren, described in this paper.
The C++ linear algebra library Eigen and the LodePNG PNG image encoder and decoder are required to compile the code. Run the bootstrap.sh script to get the required files from Eigen and LodePNG. We used Eigen version 3.3.2 for the results in the paper, but the latest version also works fine. Note that bootstrap.sh uses the commandline utilities curl, tar, mv, and rm. If you do not have these utilities, then please get the files using git or wget or your web browser.
A Makefile is included for building spectralDrawing.cpp (the main file with the algorithms) and two other standalone utilities (mtx2csr.cpp for converting a Matrix Market file to an intermediate binary format; graph_draw.c for taking vertex coordinates and drawing graph edges). We tested the code on Linux (Manjaro, gcc 8.2.1) and Windows 10 + MinGW (gcc 7.2.0).
To summarize, just doing
./bootstrap.sh
make
should work on most environments.
If you are unable to run the bootstrap.sh script or get some errors, please execute the following commands to get Eigen and LodePNG.
curl -O https://bitbucket.org/eigen/eigen/get/3.3.7.tar.gz
tar -zvxf 3.3.7.tar.gz
mv eigen-eigen-*/Eigen .
rm -rf eigen-eigen-* 3.3.7.tar.gz
curl -O https://raw.githubusercontent.com/lvandeve/lodepng/master/lodepng.h
curl -O https://raw.githubusercontent.com/lvandeve/lodepng/master/lodepng.cpp
mv lodepng.cpp lodepng.c
Our code will only use some header files from the Eigen directory.
To build the three required executables without using make (or mingw32-make.exe on Windows), execute the following commands:
g++ -std=c++11 -I. -Wall -O2 -fopenmp -o embed spectralDrawing.cpp
g++ -I. -Wall -O2 -o mtx2csr mtx2csr.cpp
gcc -std=c99 -Wall -O2 -o draw draw_graph.c lodepng.c
Get a sparse matrix in Matrix Market format. The SuiteSparse Matrix Collection is a great resource.
curl -O https://sparse.tamu.edu/MM/Pothen/barth5.tar.gz
tar -zvxf barth5.tar.gz
Convert the file to intermediate binary representation.
./mtx2csr barth5/barth5.mtx barth5/barth5.csr
Execute the graph drawing code, choosing the desired variant. In the example below, we choose coarsening, no High Dimensional Embedding, and Koren+Tutte refinement.
./embed barth5/barth5.csr 1 0 3
Create a PNG file.
./draw barth5/barth5.csr barth5/barth5.csr_c1_h0_r3_eps0.nxyz barth5/barth5_c1_h0_r3.png
The included script run_all.sh automates this process.
For small graphs (< 10,000 vertices), SVG images look much nicer. Example SVG and PNG files with drawings of the barth5 graph are included in this repository. A short video barth5.mp4 shows intermediate steps in creating the drawing.
Please cite our paper.
Shad Kirmani and Kamesh Madduri, "Spectral Graph Drawing: Building Blocks and Performance Analysis," in Proc. Workshop on Graph Algorithms Building Blocks (GABB), May 2018. https://doi.org/10.1109/IPDPSW.2018.00053.