Remove all functions that use eigs from LightGraphs

[sbromberger]

JuliaLang/julia#27616 moves IterativeEigensolvers from stdlib to https://github.com/JuliaLinearAlgebra/Arpack.jl. In keeping with our decision to reduce the number of third-party libraries upon which LightGraphs is dependent, I think we need to move things that depend on this new library out of the LightGraphs core. Fortunately, this only appears to be functions that use eigs. Unfortunately, it's used in several (seemingly unrelated) places:

src/centrality/eigenvector.jl
src/linalg/spectral.jl
src/graphcut/normalized_cut.jl

and various tests.

[jpfairbanks]

yeah that is consistent with the minimalist approach taken so far. Base is moving things into separate packages and it makes sense to follow that lead.

[sbromberger]

Does it make sense to just start from ground zero and create a LightGraphsBase package with the interface and some really core functions?

[jpfairbanks]

I would like to follow the DiffEQ model and have a lightgraphsbase with lightgraphs having the bulk of the usual functionality pre-installed. The introductory docs should point new users to the main package and developers who want only the datastructure can use LGBase

[sbromberger]

I would like to follow the DiffEQ model

This sounds like it'd work well, but having never used DiffEq, I can't say for sure. @ChrisRackauckas to the white courtesy phone, please?

[ChrisRackauckas]

The nice part about having a Base package is you disconnect the interface from the package proper. Giving a nice interface for "what a graph means" doesn't necessarily need an implementation (Graphs.jl). Or course, you usually need an implementation for it to be useful (hence LightGraphs.jl), but this allows authors of other packages to keep their dependencies low since they can just require the implementation-less version of the library and dispatch / use the traits without actually requiring a graph implementation. Then you can sup up your own implementations to your heart's content without worrying about cluttering the API and downstream package requirements.

[sbromberger]

@ChrisRackauckas thanks. The challenge we've had in the past with lots of (sub/dependent) packages is keeping them all in sync. Maintenance burden isn't linear in this case; it's something more like exponential. How do you deal with that in DiffEq?

[ChrisRackauckas]

As long as you aren't modifying it a lot (or only adding new functions/traits), then there's no "lock step". There was "DiffEqMageddon" in January where we changed the basic function interface, but other than that we haven't really had to propagate up changes since the very beginning when I first was figuring out how to do it.

Oh, there is a special case of DelayDiffEq and OrdinaryDiffEq, where the second package mirrors the first and compiles itself into itself for its interpolation function but keeps the two integrators staggard, but again that's a special case.

[sbromberger]

@jpfairbanks is planning on creating our own version of eigs so that we don't have to rely on Arpack.jl. In the meantime, I've committed #919 that makes tests pass (with the external dependency).

[matbesancon]

coming a bit late to the discussion, but is creating our version of eigs an easier way? Arpack seems like an ok dependence to have otherwise.

[sbromberger]

Arpack seems like an ok dependence to have otherwise.

Except that it's currently the reason LightGraphs won't build on Macs when Julia's built from source (JuliaLinearAlgebra/Arpack.jl#5). I think this is a good example of how even the most innocuous-seeming dependencies introduce fragility. All we need is eigs (and we have another option, which is to pull functions using it out into another package, which is IMO an appropriate thing to do given the movement of linear algebra functions from Base into other packages).

[matbesancon]

Got it, so moving stuff to LGBase.jl will be the core interface and LG will be the "visible" one that users import directly (like JuMP or DifferentialEquations)? This seems fine for me

[sbromberger]

Closing out - we're relying on Arpack for 0.14 but will be exploring @haampie's IRAM.jl as a native Julia option.