public class GraphMatrixOperations
extends java.lang.Object
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.
MatrixElementOperations
Constructor and Description |
---|
GraphMatrixOperations() |
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. |
public static Graph square(Graph g, MatrixElementOperations meo)
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.g
- the graph to be squaredpublic static Graph matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix, NumberEdgeValue nev)
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.matrix
as a JUNG
Graph
public static Graph matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix, java.lang.String weightKey)
weightKey
- the user data key to use to store or retrieve the edge weightsmatrix
as a JUNG Graph
public static Graph matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix)
matrixToGraph(matrix, (NumberEdgeValue)null)
.matrix
as a JUNG Graph
matrixToGraph(DoubleMatrix2D, NumberEdgeValue)
public static cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(Graph g, java.lang.Object edgeWeightKey)
public static cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(Graph g)
public static cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(Graph g, NumberEdgeValue nev)
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.
g
- nev
- public static cern.colt.matrix.impl.SparseDoubleMatrix2D createVertexDegreeDiagonalMatrix(Graph G)
public static cern.colt.matrix.DoubleMatrix2D computeVoltagePotentialMatrix(UndirectedGraph graph)
graph
- an undirected graph representing an electrical circuitpublic static cern.colt.matrix.DoubleMatrix1D mapTo1DMatrix(java.util.Map M)
public static cern.colt.matrix.DoubleMatrix2D computeMeanFirstPassageMatrix(Graph G, java.lang.Object edgeWeightKey, cern.colt.matrix.DoubleMatrix1D stationaryDistribution)
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.
G
- the graph on which the MFPT will be calculatededgeWeightKey
- the user data key for the edge weightsstationaryDistribution
- the asymptotic state probabilities