Package edu.umbc.cs.maple.utils

Class 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

    • 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