Build Status codecov

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 the "docs" link 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 approxchol_lap.

The algorithms provide by Laplacians.jl include:

Current Development Version

To get the current version of the master branch, run pkg> add Laplacians#master

Version 1.1.0


Version 1.0.1


Version 1.0.0

This version works with Julia version 1.0.0.

Verson 0.3.1


Version 0.3.0, July 18 (or so), 2017

This is the first version that is compatible with Julia 0.7. Other changes:

Version 0.2.2, December 28, 2017

Fixed two bugs: one in shortestPaths, and one that prevented passing some parameters to approxchol_sddm. Improved the documentation for solving linear equations.

Version 0.2.1, September 18, 2017

Fixed a bug in approxchol_sddm that caused it to be slow.

Version 0.2.0, July 17, 2017

This version is compatabile with Julia 0.6. It will not work with Julia 0.5.X.


Version 0.1.4, June 6, 2017

This is the current version. It is what you retrieve when you run Pkg.add("Laplacians").


Version 0.1.3, June 2, 2017

Major Changes:

Version 0.1.2, April 2, 2017

This is the current version. It is what you retrieve when you run Pkg.add("Laplacians").

Major Changes:

Version 0.1.1, December 26, 2016


Version 0.0.3 / 0.1.0, November 20, 2016

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.

Version 0.0.2, November 19, 2016

This is the version that works with Julia 0.4. It was captured right before the upgrade to Julia 0.5