remylau/gsparse

gSparse: C++ Library for Graph Sparsification

gSparse

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.

Sparsification Algorithm(s)

gSparse currently supports the following algorithm(s).

• Spectral Sparsification by Effective Resistance

Installation

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.

Parallelization

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.

Relation to FastEffectiveResistance

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.

Examples

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;
}

Documentation

The API reference page contains the documentation of gSparse generated by Doxygen, including all the background knowledge, example code and class APIs.

License

gSparse is an open source project licensed under MIT License.