|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectedu.uci.ics.jung.algorithms.GraphMatrixOperations
public class GraphMatrixOperations
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.
MatrixElementOperations
Constructor Summary | |
---|---|
GraphMatrixOperations()
|
Method Summary | |
---|---|
static DoubleMatrix2D |
computeMeanFirstPassageMatrix(Graph G,
Object edgeWeightKey,
DoubleMatrix1D stationaryDistribution)
Computes the all-pairs mean first passage time for the specified graph, given an existing stationary probability distribution. |
static DoubleMatrix2D |
computeVoltagePotentialMatrix(UndirectedGraph graph)
The idea here is based on the metaphor of an electric circuit. |
static SparseDoubleMatrix2D |
createVertexDegreeDiagonalMatrix(Graph G)
Returns a diagonal matrix whose diagonal entries contain the degree for the corresponding node. |
static SparseDoubleMatrix2D |
graphToSparseMatrix(Graph g)
|
static 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 SparseDoubleMatrix2D |
graphToSparseMatrix(Graph g,
Object edgeWeightKey)
Returns a SparseDoubleMatrix2D which represents the edge weights of the input Graph. |
static DoubleMatrix1D |
mapTo1DMatrix(Map M)
Converts a Map of (Vertex, Double) pairs to a DoubleMatrix1D. |
static Graph |
matrixToGraph(DoubleMatrix2D matrix)
Creates a graph from a square (weighted) adjacency matrix. |
static Graph |
matrixToGraph(DoubleMatrix2D matrix,
NumberEdgeValue nev)
Creates a graph from a square (weighted) adjacency matrix. |
static Graph |
matrixToGraph(DoubleMatrix2D matrix,
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 |
---|
public GraphMatrixOperations()
Method Detail |
---|
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 squared
public static Graph matrixToGraph(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(DoubleMatrix2D matrix, String weightKey)
weightKey
- the user data key to use to store or retrieve the edge weights
matrix
as a JUNG Graph
public static Graph matrixToGraph(DoubleMatrix2D matrix)
matrixToGraph(matrix, (NumberEdgeValue)null)
.
matrix
as a JUNG Graph
matrixToGraph(DoubleMatrix2D, NumberEdgeValue)
public static SparseDoubleMatrix2D graphToSparseMatrix(Graph g, Object edgeWeightKey)
public static SparseDoubleMatrix2D graphToSparseMatrix(Graph g)
public static 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 SparseDoubleMatrix2D createVertexDegreeDiagonalMatrix(Graph G)
public static DoubleMatrix2D computeVoltagePotentialMatrix(UndirectedGraph graph)
graph
- an undirected graph representing an electrical circuit
public static DoubleMatrix1D mapTo1DMatrix(Map M)
public static DoubleMatrix2D computeMeanFirstPassageMatrix(Graph G, Object edgeWeightKey, 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
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |