STAG C++
Spectral Toolkit of Algorithms for Graphs

The STAG library is an easytouse C++ library providing several spectral algorithms for graphs. STAG is built on the Eigen library for representing sparse matrices and so it may be useful to also refer to the Eigen documentation.
To include the STAG library in your C++ project, you should first install the following dependencies.
You should refer to their documentation for installation instruction, although the following should work on a standard Linux system.
You should download the latest version of the STAG library. For example:
Then, you can build and install STAG with cmake.
Adding the following to your CMakeLists.txt
will make the STAG library available to your project.
You may find it helpful to refer to the example STAG project.
There are four methods for creating a stag::Graph object:
The STAG library can easily construct several standard graphs such as the cycle graph, the complete graph, and the barbell graph. See graph.h for the full list and their documentation.
You can construct a named graph with the following code.
You can construct a stag::Graph object with any sparse adjacency matrix using the default constructor.
There are many other ways to construct the sparse adjacency matrix. Please refer to the Eigen Documentation.
The STAG library can read and write graphs to a simple edgelist file format. In an edgelist file, each row corresponds to one edge in the graph and lists the indices of the edges endpoints, and optionally the weight of the edge.
For example, here is a simple edgelist file.
This represents a graph on three vertices with three edges. For example, the first row corresponds to an edge between vertices 0 and 1 with weight 0.5. For more information on the file formats supported by STAG, see Graph File Formats.
To load a STAG graph from an edgelist file, you can use the following code.
The STAG library can also save a graph to an edgelist file.
The random.h module provides several methods for generating ErdosRenyi graphs and random graphs drawn from the stochastic block model.
The cluster.h module provides two clustering methods which are applicable for a wide variety of applications.
Spectral clustering is a popular and simple graph clustering algorithm. STAG provides a simple spectral clustering interface which is demonstrated in the following example.
The stag::spectral_cluster method returns a vector giving the cluster label of each vertex in the graph.
Given a vertex of the underlying graph as input, a local clustering algorithm finds a cluster around the input vertex. The algorithm runs in time proportional to the size of the returned cluster and independent of the size of the entire graph.
Local clustering is provided by the stag::local_cluster method which can be used as in the following example.
Notice that the local clustering method requires an estimate of the volume of the target cluster. This parameter does not impose a hard constraint on the algorithm and so an approximate volume is enough.
The stag::local_cluster method returns a vector containing the ID of each vertex in the local cluster.
For working with very large graphs, consider using the stag::AdjacencyListLocalGraph object for local clustering. This will read the graph from disk in a local way and reduces the memory requirement.