To get the latest version of sparc, clone from github via:
> git clone https://github.com/gyalla/sparc.git
SPARC makes use of the following packages:
which requires blas and lapack, as well as a fortran and c++ compiler. Use the 'make dep' target in the Makefile to aid in installation. After building BOOST and ARPACK, edit the variables BOOST_DIR and ARPACK_DIR at the top of the Makefile to point to the root path for each package. Additionally, make sure the blas and lapack libraries are specified correctly.
After building the required packages, issue a make command in the root directory to see all available targets, i.e.,
> make Available make targets: all : build main program check : build and run test suite doc : build documentation (doxygen page) dep : build dependencies
There is also the following PHONY targets in the Makefile: clean, clobber. Note, only the Makefile in the root directory should be called directly. To build sparc, run
> make all
To verify that the software is working properly, a test option is provided to run a short suite of functionality tests against the local build. To run, issue a 'make check' to initiate the tests. If succesful, output similar to the following will be generated:
> make check ---------------------------------------------------------------------- Running Simple Graph Test ---------------------------------------------------------------------- Initalizing graph from: simple_graph.dat Successfully computed neighbors Successfully computed adjacency matrix in CSC format Successfully computed graph laplacian in CSC format Successfully computed smallest two eigenvalues PASSED: Simple Graph Test ---------------------------------------------------------------------- Running Complex Graph Test ---------------------------------------------------------------------- Initalizing graph from: complex_graph.dat Successfully computed adjacency matrix in CSC format Successfully computed graph laplacian in CSC format --->Graph coloring computed (Time: 6.7e-05) --->Maximal matching computed (Time: 1.2e-05) --->Parent graph computed (Time: 9e-06) --->Graph coloring computed (Time: 2.1e-05) --->Maximal matching computed (Time: 1.8e-05) --->Parent graph computed (Time: 4e-06) --->Computing adjacency matrix (Time: 0) --->Computing graph laplacian (Time: 0) --->Getting second eigenvector with Arpack++ (Time: 0) --->Getting index Map (Time: 0) PASSED: Complex Graph Test ---------------------------------------------------------------------- Running Complex Graph Test ---------------------------------------------------------------------- Initalizing graph from: corner_cases_graph.dat Successfully computed adjacency matrix in CSC format Successfully computed graph laplacian in CSC format PASSED: Corner Cases Graph Test ---------------------------------------------------------------------- Running Graph Coarsening Test ---------------------------------------------------------------------- Initalizing graph from: coarsen_test.dat Successfully colored graph in 2.9e-05 sec Successfully computed maximal matching in 9e-06 sec --->Graph coloring computed (Time: 3.7e-05) --->Maximal matching computed (Time: 6e-06) --->Parent graph computed (Time: 6e-06) Successfully coarsened graph in 6.6e-05 sec PASSED: Coarsening Test ---------------------------------------------------------------------- Running OpenMP Test ---------------------------------------------------------------------- Setting num_threads to 1 Rerunning coarsen test with multiple threads ... ---------------------------------------------------------------------- Running Graph Coarsening Test ---------------------------------------------------------------------- Initalizing graph from: coarsen_test.dat Successfully colored graph in 2.8e-05 sec Successfully computed maximal matching in 9e-06 sec --->Graph coloring computed (Time: 2.7e-05) --->Maximal matching computed (Time: 7e-06) --->Parent graph computed (Time: 6e-06) Successfully coarsened graph in 5.6e-05 sec PASSED: Coarsening Test Initalizing graph from: complex_graph.dat --->Graph coloring computed (Time: 3.7e-05) --->Maximal matching computed (Time: 9e-06) --->Parent graph computed (Time: 7e-06) --->Computing adjacency matrix (Time: 0) --->Computing graph laplacian (Time: 0) --->Getting second eigenvector with Arpack++ (Time: 0) --->Getting index Map (Time: 0) PASSED: OpenMP Test ---------------------------------------------------------------------- Running Matrix Manipulation Test ---------------------------------------------------------------------- Initalizing graph from: matrixOperations.dat Successfully computed sub matrices in CSC format Successfully divide vector in CSC format Successfully performed Matvec --->Approximate Matvec Time: 1e-06 --->Converged in 43 iterations. Residual = 8.7564e-15 Successfully solved system with iterative solver Successfully reordered vector PASSED: Matrix Operations Test
The main way to interact with sparc is through the command line. Running a './sparc -h' command will show the following message:
> ./sparc -h
Usage: ./sparc [OPTIONS] [ARGUMENT]
Allowed Options:
-h [ --help ] show this mesage and exit
-f [ --graphFile ] arg (required) file containing initial graph data
-t [ --telFile ] arg (=NONE) file containing teleportation vector data
-a [ --alpha ] arg (=0.5) Set probability praramer alpha
-c [ --coarse_levels ] arg (=0) Set coarsen levels
-n [ --noSB ] Don't do spectral bisection. Just solve
pagerank problem with original graph.
-p [ --nprocs ] arg (=1) Set number of procs
An example run would look like:
> ./sparc -f data/facebook_combined.txt -c 4
This specifies to solve the page rank problem using the data from 'facebook_combined.txt' with spectral bisection after four levels of coarsening. A uniform teleportation vector is used by default.
Another example would be
> ./sparc -f data/facebook_combined.txt -t data/VinFile10Facebook.dat -a 0.1
This specifies to solve the page rank problem using data from 'facebook_combined.txt' with spectral bisection without any coarsening and to use the information in 'VinFile10Facebook.dat' as the teleportation vector, and a probability parameter of 0.1.
The results will be written to the output/ directory and can be plotted using the post processing scripts.
Note, the first line of the data file must contain the number of nodes and edges, e.g.,
4039 88234 0 1 0 2 0 3 ... ... (88234) ... 4023 4038 4026 4030 4027 4031 4027 4032 4027 4038 4031 4038