edu.uci.ics.jung.algorithms

Class GraphMatrixOperations

java.lang.Object

edu.uci.ics.jung.algorithms.GraphMatrixOperations

public class GraphMatrixOperations
extends java.lang.Object

Contains methods for performing the analogues of certain matrix operations on graphs.

These implementations are efficient on sparse graphs, but may not be the best implementations for very dense graphs.

Anticipated additions to this class: methods for taking products and inverses of graphs.

Author:

Joshua O'Madadhain

See Also:

MatrixElementOperations

Constructor Summary

Constructors

Constructor and Description
GraphMatrixOperations()

Method Summary

Methods

Modifier and Type	Method and Description
static cern.colt.matrix.DoubleMatrix2D	computeMeanFirstPassageMatrix(Graph G, java.lang.Object edgeWeightKey, cern.colt.matrix.DoubleMatrix1D stationaryDistribution) Computes the all-pairs mean first passage time for the specified graph, given an existing stationary probability distribution.
static cern.colt.matrix.DoubleMatrix2D	computeVoltagePotentialMatrix(UndirectedGraph graph) The idea here is based on the metaphor of an electric circuit.
static cern.colt.matrix.impl.SparseDoubleMatrix2D	createVertexDegreeDiagonalMatrix(Graph G) Returns a diagonal matrix whose diagonal entries contain the degree for the corresponding node.
static cern.colt.matrix.impl.SparseDoubleMatrix2D	graphToSparseMatrix(Graph g)
static cern.colt.matrix.impl.SparseDoubleMatrix2D	graphToSparseMatrix(Graph g, NumberEdgeValue nev) Returns a SparseDoubleMatrix2D whose entries represent the edge weights for the edges in g, as specified by nev.
static cern.colt.matrix.impl.SparseDoubleMatrix2D	graphToSparseMatrix(Graph g, java.lang.Object edgeWeightKey) Returns a SparseDoubleMatrix2D which represents the edge weights of the input Graph.
static cern.colt.matrix.DoubleMatrix1D	mapTo1DMatrix(java.util.Map M) Converts a Map of (Vertex, Double) pairs to a DoubleMatrix1D.
static Graph	matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix) Creates a graph from a square (weighted) adjacency matrix.
static Graph	matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix, NumberEdgeValue nev) Creates a graph from a square (weighted) adjacency matrix.
static Graph	matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix, java.lang.String weightKey) Creates a graph from a square (weighted) adjacency matrix.
static Graph	square(Graph g, MatrixElementOperations meo) Returns the graph that corresponds to the square of the (weighted) adjacency matrix that the specified graph g encodes.

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphMatrixOperations

public GraphMatrixOperations()

Method Detail

square

public static Graph square(Graph g,
           MatrixElementOperations meo)

Returns the graph that corresponds to the square of the (weighted) adjacency matrix that the specified graph g encodes. The implementation of MatrixElementOperations that is furnished to the constructor specifies the implementation of the dot product, which is an integral part of matrix multiplication.

Parameters:

g - the graph to be squared

Returns:

the result of squaring g

matrixToGraph

public static Graph matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix,
                  NumberEdgeValue nev)

Creates a graph from a square (weighted) adjacency matrix. If nev is non-null then the weight is stored as a Double as specified by the implementation of nev. If the matrix is symmetric, then the graph will be constructed as a sparse undirected graph; otherwise, it will be constructed as a sparse directed graph.

Returns:

a representation of matrix as a JUNG Graph

matrixToGraph

public static Graph matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix,
                  java.lang.String weightKey)

Creates a graph from a square (weighted) adjacency matrix. If the weight key is non-null then the weight is stored as a Double in the given edge's user data under the specified key name. If the matrix is symmetric, then the graph will be constructed as a sparse undirected graph; otherwise it will be constructed as a sparse directed graph.

Parameters:

weightKey - the user data key to use to store or retrieve the edge weights

Returns:

a representation of matrix as a JUNG Graph

matrixToGraph

public static Graph matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix)

Creates a graph from a square (weighted) adjacency matrix. Equivalent to matrixToGraph(matrix, (NumberEdgeValue)null).

Returns:

a representation of matrix as a JUNG Graph

See Also:

matrixToGraph(DoubleMatrix2D, NumberEdgeValue)

graphToSparseMatrix

public static cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(Graph g,
                                                             java.lang.Object edgeWeightKey)

Returns a SparseDoubleMatrix2D which represents the edge weights of the input Graph.

Returns:

SparseDoubleMatrix2D

graphToSparseMatrix

public static cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(Graph g)

graphToSparseMatrix

public static cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(Graph g,
                                                             NumberEdgeValue nev)

Returns a SparseDoubleMatrix2D whose entries represent the edge weights for the edges in g, as specified by nev.

The (i,j) entry of the matrix returned will be equal to the sum of the weights of the edges connecting the vertex with index i to j.

If nev is null, then a constant edge weight of 1 is used.

Parameters:

g -

nev -

createVertexDegreeDiagonalMatrix

public static cern.colt.matrix.impl.SparseDoubleMatrix2D createVertexDegreeDiagonalMatrix(Graph G)

Returns a diagonal matrix whose diagonal entries contain the degree for the corresponding node.

Returns:

SparseDoubleMatrix2D

computeVoltagePotentialMatrix

public static cern.colt.matrix.DoubleMatrix2D computeVoltagePotentialMatrix(UndirectedGraph graph)

The idea here is based on the metaphor of an electric circuit. We assume that an undirected graph represents the structure of an electrical circuit where each edge has unit resistance. One unit of current is injected into any arbitrary vertex s and one unit of current is extracted from any arbitrary vertex t. The voltage at some vertex i for source vertex s and target vertex t can then be measured according to the equation: V_i^(s,t) = T_is - T-it where T is the voltage potential matrix returned by this method. *

Parameters:

graph - an undirected graph representing an electrical circuit

Returns:

the voltage potential matrix

See Also:

"P. Doyle and J. Snell, 'Random walks and electric networks,', 1989", "M. Newman, 'A measure of betweenness centrality based on random walks', pp. 5-7, 2003"

mapTo1DMatrix

public static cern.colt.matrix.DoubleMatrix1D mapTo1DMatrix(java.util.Map M)

Converts a Map of (Vertex, Double) pairs to a DoubleMatrix1D.

computeMeanFirstPassageMatrix

public static cern.colt.matrix.DoubleMatrix2D computeMeanFirstPassageMatrix(Graph G,
                                                            java.lang.Object edgeWeightKey,
                                                            cern.colt.matrix.DoubleMatrix1D stationaryDistribution)

Computes the all-pairs mean first passage time for the specified graph, given an existing stationary probability distribution.

The mean first passage time from vertex v to vertex w is defined, for a Markov network (in which the vertices represent states and the edge weights represent state->state transition probabilities), as the expected number of steps required to travel from v to w if the steps occur according to the transition probabilities.

The stationary distribution is the fraction of time, in the limit as the number of state transitions approaches infinity, that a given state will have been visited. Equivalently, it is the probability that a given state will be the current state after an arbitrarily large number of state transitions.

Parameters:

G - the graph on which the MFPT will be calculated

edgeWeightKey - the user data key for the edge weights

stationaryDistribution - the asymptotic state probabilities

Returns:

the mean first passage time matrix