gSparse: C++ Library for Graph Sparsification
gSparse is a C++ library for Graph Sparsification. It is built on top of Eigen, an open source linear algebra library.
gSparse currently supports the following algorithm(s).
gSparse is implemented as a header-only C++ library, whose only dependency, Eigen, is also header-only.
When compiling gSparse, the compiler must be able to find the gSparse and Eigen header files. This can be done by specifying compiler's include path to Eigen and gSparse source directories.
gSparse requires Compiler with C++11 support or above.
As gSparse utilizes Eigen3 for its matrix operations, it is possible to enable multi-threading on these operations by simply setting compiler's option. See Eigen and multi-threading.
FastER is a software written in MATLAB for calculating Graph Effective Resistance. gSparse leverages the algorithm of FastER for Spectral Sparsification in C++. However, gSparse is not a direct port of FastER because it provides a different interface and it does not depend on CMG Solver.
Below is an example that demonstrates the gSparse to sparsify a graph from CSV files
#include <gSparse/gSparse.hpp>
#include <iostream>
int main()
{
// Create a CSV Reader and specify the file location
gSparse::GraphReader csvReader = std::make_shared<gSparse::GraphCSVReader>("edgeList.csv", "weightList.csv",",");
// Create an Undirected Graph. gSparse::Graph object is a shared_ptr.
gSparse::Graph graph = std::make_shared<gSparse::UndirectedGraph>(csvReader);
// Display original edge count
std::cout<<"Original Edge Count: " << graph->GetEdgeCount() << std::endl;
// Creating Sparsifier Object
gSparse::SpectralSparsifier::ERSampling sparsifier(graph);
// Set Hyper-parameters
// Approximate the Effective Weight Resistance (Faster)
// C = 4 and Epsilon = 0.5
sparsifier.SetERPolicy(gSparse::SpectralSparsifier::APPROXIMATE_ER);
sparsifier.SetC(4.0);
sparsifier.SetEpsilon(0.5);
// Compute Effective Weight Resistance
sparsifier.Compute();
// Perform Sparsification
auto sparseGraph1 = sparsifier.GetSparsifiedGraph();
std::cout<<"Sparised Edge Count (ApproxER): " << sparseGraph1->GetEdgeCount() << std::endl;
return EXIT_SUCCESS;
}The API reference page contains the documentation of gSparse generated by Doxygen, including all the background knowledge, example code and class APIs.
gSparse is an open source project licensed under MIT License.