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.
To get the current version of the master branch, run
Fixed two bugs: one in shortestPaths, and one that prevented passing some parameters to approxCholSddm. Improved the documentation for solving linear equations.
Fixed a bug in
approxCholSddm that caused it to be slow.
This version is compatible with Julia 0.6. It will not work with Julia 0.5.X.
approxCholSddm, a wrapper of
approxCholLapthat solves SDDM systems.
This is the current version. It is what you retrieve when you run
sparsify, an implementation of sparsification by effective resistance sampling, following Spielman and Srivastava.
conditionNumberfor checking how well one graph approximates another.
approxCholLap. Made improvements in this solver.
gtimeoutwhen calling Matlab to use icc, CMG, or LAMG.
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
The development of this package has been supported in part by the National Science Foundation Award CCF-1562041 and by the Office of Naval Research Award N00014-16-1-2374.
9 days ago