matvec issues

[sbromberger]

@jpfairbanks

Pkg.test("LightGraphs") is throwing warnings here:

running /Users/seth/.julia/v0.4/LightGraphs/test/graphmatrices.jl ...
WARNING: replacing module TestLightGraphs

and doesn't seem to be returning. Is there a reason TestLightGraphs is its own module?

Also, CombinatorialAdjacency(g) doesn't seem to work as I'd expect (that is, at all).

[sbromberger]

See https://github.com/JuliaGraphs/LightGraphs.jl/pull/126

[sbromberger]

All fixed except for my understanding of how to use this, which is still broken :)

[jpfairbanks]

I published it to the Package index yesterday. The usage is if you have an algorithm that can be expressed in terms of the eigenvalues/eigenvectors of a matrix, and that matrix is a function of the adjacency matrix of the graph.

function alg(M::AbstractMatrix)
     do something with M
     ...
end

f(x) = I - x
alg(f(adjacency_matrix(g)))

Now you can apply that algorithm directly to the graph without making an intermediary matrix.

For example algebraic connectivity from the textbook definition:

function algebraic_connectivity(g::Graph)
    L = Laplacian(CombinatorialAdjacency(g))
    eval = eigs(L, nev=2, which=:SR, ritzvec=false)
    return eval
end

which will not copy the graph.

The reason I wrote the package was to allow myself to write functions that used one implementation if it got the NormalizedLaplacian and different implementation if it got the CombinatorialAdjacency matrix. Since the underlying storage was still a SparseMatrix, there was no real change in performance. I just wanted the safety of allowing Julia to check that the input was a Laplacian and not an Adjacency matrix.

[sbromberger]

I'm starting to understand this a bit better, but I'm still confused since

julia> g = PathGraph(10)
{10, 9} undirected graph

julia> CombinatorialAdjacency(g)
ERROR: MethodError: `convert` has no method matching convert(::Type{GraphMatrices.CombinatorialAdjacency{T,S,V}}, ::LightGraphs.Graph)
This may have arisen from a call to the constructor GraphMatrices.CombinatorialAdjacency{T,S,V}(...),
since type constructors fall back to convert methods.
Closest candidates are:
  call{T}(::Type{T}, ::Any)
  convert(::Type{GraphMatrices.CombinatorialAdjacency{T,S,V}}, ::GraphMatrices.Adjacency{T})
  convert{T}(::Type{T}, ::T)
  ...
 in call at essentials.jl:56

Where is the method for CombinatorialAdjacency(g::Graph) defined?

[jpfairbanks]

It is in test/graphmx.jl

    import GraphMatrices.CombinatorialAdjacency
    import GraphMatrices.SparseMatrix

    function CombinatorialAdjacency(A)
        D = float(indegree(A, vertices(A)))
        return CombinatorialAdjacency{Float64, typeof(A), typeof(D)}(A,D)
    end

It casts to Float64 because the StochasticAdjacency, AveragingAdjacency, and NormalizedAdjacency need to be able to divide by the degree vector D. You could pass a type parameter in order to use Float32, Float64, but to keep it simple I chose to cast to Float64.

[sbromberger]

is there a reason we shoudn't move this into src/ ?

Also, indegree(A, vertices(A) can be simplified to indegree(A).

[jpfairbanks]

No reason as long as it is conditioned on graph matrices installed

[sbromberger]

Got it. I don't think we need all those tests either since the only function that we're integrating is CombinatorialAdjacency(). Can you take a look at https://github.com/JuliaGraphs/LightGraphs.jl/pull/129 and let me know what you think?

[sbromberger]

I think we've resolved this - feel free to reopen if you'd like to discuss more.