Package edu.umbc.cs.maple.utils

Class SGTUtils

java.lang.Object

edu.umbc.cs.maple.utils.SGTUtils

public class SGTUtils
extends Object

This class implements utility functions for Spectral Graph Theory methods.

Copyright (c) 2008 Eric Eaton

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Version:

0.1

Author:

Eric Eaton ([email protected])
University of Maryland Baltimore County

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	SGTUtils.KeyEigenvalues	Defines whether the largest or the smallest eigenvalues are the most important (i.e.
static class	SGTUtils.LaplacianType	Defines the type of the graph Laplacian

Constructor Summary

Constructors

Constructor	Description
SGTUtils()

Method Summary

Modifier and Type	Method	Description
static Jama.Matrix	directedWeightedAdjacencyToLaplacian(Jama.Matrix adjacencyMatrix, SGTUtils.LaplacianType laplacianType)	Computes the Laplacian matrix for a directed weighted adjacency matrix A.
static Jama.Matrix	projectFunctionToBasis(Jama.Matrix basisVectors, Jama.Matrix f)	Computes the projection of a function onto another basis.
static Jama.Matrix[]	resolution(Jama.Matrix A, int resolution, SGTUtils.KeyEigenvalues keyEigenvalues)	Computes the specified resolution of matrix A.
static Jama.Matrix[]	resolutionGraphFunction(Jama.Matrix graphLaplacian, Jama.Matrix f, int resolution)	Computes the specified resolution of a function on a graph.
static Jama.Matrix	undirectedWeightedAdjacencyToLaplacian(Jama.Matrix adjacencyMatrix, SGTUtils.LaplacianType laplacianType)	Computes the Laplacian matrix for an undirected weighted adjacency matrix A.
static Jama.Matrix	weightedAdjacencyToLaplacian(Jama.Matrix adjacencyMatrix, SGTUtils.LaplacianType laplacianType)	Computes the Laplacian matrix for a weighted adjacency matrix A.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SGTUtils

public SGTUtils()

Method Detail

weightedAdjacencyToLaplacian

public static Jama.Matrix weightedAdjacencyToLaplacian(Jama.Matrix adjacencyMatrix,
                                                       SGTUtils.LaplacianType laplacianType)

Computes the Laplacian matrix for a weighted adjacency matrix A. Automatically detects whether the adjacency matrix is directed or undirected.

Parameters:

adjacencyMatrix - the adjacency matrix

laplacianType - whether to use the normalized or combinatorial form of the Laplacian

undirectedWeightedAdjacencyToLaplacian

public static Jama.Matrix undirectedWeightedAdjacencyToLaplacian(Jama.Matrix adjacencyMatrix,
                                                                 SGTUtils.LaplacianType laplacianType)

Computes the Laplacian matrix for an undirected weighted adjacency matrix A. Coded from Section 1.4 of Chung's Spectral Graph Theory

Parameters:

adjacencyMatrix - the adjacency matrix

laplacianType - whether to use the normalized or combinatorial form of the Laplacian

directedWeightedAdjacencyToLaplacian

public static Jama.Matrix directedWeightedAdjacencyToLaplacian(Jama.Matrix adjacencyMatrix,
                                                               SGTUtils.LaplacianType laplacianType)

Computes the Laplacian matrix for a directed weighted adjacency matrix A.

Parameters:

adjacencyMatrix - the adjacency matrix

laplacianType - whether to use the normalized or combinatorial form of the Laplacian

resolution

public static Jama.Matrix[] resolution(Jama.Matrix A,
                                       int resolution,
                                       SGTUtils.KeyEigenvalues keyEigenvalues)

Computes the specified resolution of matrix A.

Parameters:

A - the matrix

resolution - the resolution

keyEigenvalues - specifies whether the top LARGEST or SMALLEST eigenvalues should be taken. LARGEST should be the choice for most applications; SMALLEST should be the choice for eigenvectors of the graph Laplacian.

Returns:

three matrices M[3] M[0]: Ak, A at the specified resolution M[1]: Qk, the eigenvectors used to compose Ak M[2]: Lk, the eigenvalues used to compose Ak

resolutionGraphFunction

public static Jama.Matrix[] resolutionGraphFunction(Jama.Matrix graphLaplacian,
                                                    Jama.Matrix f,
                                                    int resolution)

Computes the specified resolution of a function on a graph.

Parameters:

graphLaplacian - the graph Laplacian

f - the function values on the vertices of the graph

resolution - the resolution

Returns:

three matrices M[3] M[0]: fk, f at the specified resolution on the graph M[1]: Qk, the eigenfunctions of the graph Laplacian used in the computation M[2]: Lk, the eigenvalues of the graph Laplacian used in the computation

projectFunctionToBasis

public static Jama.Matrix projectFunctionToBasis(Jama.Matrix basisVectors,
                                                 Jama.Matrix f)

Computes the projection of a function onto another basis.

Parameters:

basisVectors - the basis vectors

f - the function values on the vertices of the graph

Returns:

one matrix f on the basis vectors