9 days ago
Laplacians is a package containing graph algorithms, with an emphasis on tasks related to spectral and algebraic graph theory. It contains (and will contain more) code for solving systems of linear equations in graph Laplacians, low stretch spanning trees, sparsifiation, clustering, local clustering, and optimization on graphs.
All graphs are represented by sparse adjacency matrices. This is both for speed, and because our main concerns are algebraic tasks. It does not handle dynamic graphs. It would be very slow to implement dynamic graphs this way.
The documentation may be found by clicking on one of the "docs" links above.
This includes instructions for installing Julia, and some tips for how to start using it. It also includes guidelines for Dan Spielman's collaborators.
For some examples of some of the things you can do with Laplacians, look at
If you want to solve Laplacian equations, we recommend the KMPLapSolver. For SDD equations, we recommend the KMPSDDSolver.
The algorithms provide by Laplacians.jl include:
akpw, a heuristic for computing low stretch spanning trees written by Daniel Spielman, inspired by the algorithm from the paper "A graph-theoretic game and its application to the k-server problem" by Alon, Karp, Peleg, and West, SIAM Journal on Computing, 1995.
edgeElimLap: a fast heuristic for solving Laplacians equations written by Daniel Spielman, based on the paper "Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple" by Rasmus Kyng and Sushant Sachdeva, FOCS 2016.
KMPSDDSolver: linear equation solvers based on the paper "Approaching optimality for solving SDD systems" by Koutis, Miller, and Peng, SIAM Journal on Computing, 2014.
samplingLapSolver, based on the paper "Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple" by Rasmus Kyng and Sushant Sachdeva, FOCS 2016.
wtedChimeragraph generators for testing graph algorithms, by Daniel Spielman.
prna version of PageRank Nibble based on "Using PageRank to Locally Partition a Graph", Internet Mathematics and
LocalImprovebased on "Flow-Based Algorithms for Local Graph Clustering" by Zeyuan Allen-Zhu and Lorenzo Orecchia, SODA 2014.
To get the current version of the master branch, run
This is the current version. It is what you retrieve when you run
edgeElimLap- a fast Laplacian solver.
Versions 0.0.3 and 0.1.0 are the same. These versions works with Julia 0.5.
Warning: the behavior of chimera and wtedChimera differs between Julia 0.4 and Julia 0.5 because randperm acts differently in these.
This is the version that works with Julia 0.4. It was captured right before the upgrade to Julia 0.5