edu.umbc.cs.maple.utils
Class SGTUtils

java.lang.Object
  extended by edu.umbc.cs.maple.utils.SGTUtils

public class SGTUtils
extends java.lang.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 (EricEaton@umbc.edu)
University of Maryland Baltimore County

Nested Class Summary
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
SGTUtils()
           
 
Method Summary
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