Linear Algebra

Страница в процессе перевода.

LightGraphs.jl provides the following matrix operations on both directed and undirected graphs in the LinAlg submodule:

Full Docs

# LightGraphs.LinAlg — Module

LinAlg

A package for using the type system to check types of graph matrices.

# LightGraphs.LinAlg.Adjacency — Type

Adjacency{T}

The core Adjacency matrix structure. Keeps the vertex degrees around. Subtypes are used to represent the different normalizations of the adjacency matrix. Laplacian and its subtypes are used for the different Laplacian matrices.

Adjacency(lapl::Laplacian) provides a generic function for getting the adjacency matrix of a Laplacian matrix. If your subtype of Laplacian does not provide a field A for the Adjacency instance, then attach another method to this function to provide an Adjacency{T} representation of the Laplacian. The Adjacency matrix here is the final subtype that corresponds to this type of Laplacian.

# LightGraphs.LinAlg.AveragingAdjacency — Type

AveragingAdjacency{T}

The matrix whose action is to average over each neighborhood.

# LightGraphs.LinAlg.AveragingLaplacian — Type

AveragingLaplacian{T}

Laplacian version of the AveragingAdjacency matrix.

# LightGraphs.LinAlg.CombinatorialAdjacency — Type

CombinatorialAdjacency{T,S,V}

The standard adjacency matrix.

# LightGraphs.LinAlg.GraphMatrix — Type

GraphMatrix{T}

An abstract type to allow opertions on any type of graph matrix

# LightGraphs.LinAlg.Noop — Type

Noop

A type that represents no action.

Implementation Notes

The purpose of Noop is to help write more general code for the

different scaled GraphMatrix types.

# LightGraphs.LinAlg.NormalizedAdjacency — Type

NormalizedAdjacency{T}

The normalized adjacency matrix is . If A is symmetric, then the normalized adjacency is also symmetric with real eigenvalues bounded by [-1, 1].

# LightGraphs.LinAlg.NormalizedLaplacian — Type

NormalizedLaplacian{T}

The normalized Laplacian is . If A is symmetric, then the normalized Laplacian is also symmetric with positive eigenvalues bounded by 2.

# LightGraphs.LinAlg.StochasticAdjacency — Type

StochasticAdjacency{T}

A transition matrix for the random walk.

# LightGraphs.LinAlg.StochasticLaplacian — Type

StochasticLaplacian{T}

Laplacian version of the StochasticAdjacency matrix.

# LightGraphs.LinAlg.degrees — Method

degrees(adjmat)

Return the degrees of a graph represented by the CombinatorialAdjacency adjmat.

# LightGraphs.LinAlg.degrees — Method

degrees(graphmx)

Return the degrees of a graph represented by the graph matrix graphmx.

# LightGraphs.LinAlg.symmetrize — Function

symmetrize(A::SparseMatrix, which=:or)

Return a symmetric version of graph (represented by sparse matrix A) as a sparse matrix. which may be one of :triu, :tril, :sum, or :or. Use :sum for weighted graphs.

# LightGraphs.LinAlg.symmetrize — Function

symmetrize(adjmat, which=:or)

Return a symmetric version of graph (represented by CombinatorialAdjacency adjmat) as a CombinatorialAdjacency. which may be one of :triu, :tril, :sum, or :or. Use :sum for weighted graphs.

Implementation Notes

Only works on Adjacency because the normalizations don’t commute with symmetrization.

# LightGraphs.LinAlg.adjacency_matrix — Function

adjacency_matrix(g[, T=Int; dir=:out])

Return a sparse adjacency matrix for a graph, indexed by [u, v] vertices. Non-zero values indicate an edge from u to v. Users may override the default data type (Int) and specify an optional direction.

Optional Arguments

dir=:out: :in, :out, or :both are currently supported.

Implementation Notes

This function is optimized for speed and directly manipulates CSC sparse matrix fields.

# LightGraphs.LinAlg.adjacency_spectrum — Function

adjacency_spectrum(g[, T=Int; dir=:unspec])

Return the eigenvalues of the adjacency matrix for a graph g, indexed by vertex. Default values for T are the same as those in adjacency_matrix.

Optional Arguments

dir=:unspec: Options for dir are the same as those in laplacian_matrix.

Performance

Converts the matrix to dense with memory usage.

Implementation Notes

Use eigs(adjacency_matrix(g); kwargs...) to compute some of the eigenvalues/eigenvectors.

# LightGraphs.LinAlg.incidence_matrix — Function

incidence_matrix(g[, T=Int; oriented=false])

Return a sparse node-arc incidence matrix for a graph, indexed by [v, i], where i is in 1:ne(g), indexing an edge e. For directed graphs, a value of -1 indicates that src(e) == v, while a value of 1 indicates that dst(e) == v. Otherwise, the value is 0. For undirected graphs, both entries are 1 by default (this behavior can be overridden by the oriented optional argument).

If oriented (default false) is true, for an undirected graph g, the matrix will contain arbitrary non-zero values representing connectivity between v and i.

# LightGraphs.LinAlg.laplacian_matrix — Method

laplacian_matrix(g[, T=Int; dir=:unspec])

Return a sparse Laplacian matrix for a graph g, indexed by [u, v] vertices. T defaults to Int for both graph types.

Optional Arguments

dir=:unspec: :unspec, :both, :in, and:outare currently supported. For undirected graphs,dirdefaults to:out; for directed graphs,dirdefaults to:both`.

# LightGraphs.LinAlg.laplacian_spectrum — Function

laplacian_spectrum(g[, T=Int; dir=:unspec])

Return the eigenvalues of the Laplacian matrix for a graph g, indexed by vertex. Default values for T are the same as those in laplacian_matrix.

Optional Arguments

dir=:unspec: Options for dir are the same as those in laplacian_matrix.

Performance

Converts the matrix to dense with memory usage.

Implementation Notes

Use eigs(laplacian_matrix(g); kwargs...) to compute some of the eigenvalues/eigenvectors.

# LightGraphs.LinAlg.spectral_distance — Function

spectral_distance(G₁, G₂ [, k])

Compute the spectral distance between undirected n-vertex graphs G₁ and G₂ using the top k greatest eigenvalues. If k is ommitted, uses full spectrum.

References

JOVANOVIC, I.; STANIC, Z., 2014. Spectral Distances of Graphs Based on their Different Matrix Representations