Skip to content
Implementations of Koren's graph drawing algorithms
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
.travis.yml
CODE_OF_CONDUCT.md
LICENSE
Makefile
README.md
barth5_103.gif
barth5_103.mp4
barth5_103.png
barth5_103.svg
bootstrap.sh
draw_graph.c
mtx2csr.cpp
run_all.sh
spectralDrawing.cpp

README.md

Spectral Graph Drawing

Build Status Codacy Badge

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.

Getting Started

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

Usage

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.

Citing this work

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.

You can’t perform that action at this time.