|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object edu.uci.ics.jung.algorithms.matrix.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.
MatrixElementOperations
Constructor Summary | |
---|---|
GraphMatrixOperations()
|
Method Summary | ||
---|---|---|
static
|
computeMeanFirstPassageMatrix(Graph<V,E> G,
Map<E,Number> edgeWeights,
cern.colt.matrix.DoubleMatrix1D stationaryDistribution)
Computes the all-pairs mean first passage time for the specified graph, given an existing stationary probability distribution. |
|
static
|
computeVoltagePotentialMatrix(UndirectedGraph<V,E> graph)
The idea here is based on the metaphor of an electric circuit. |
|
static
|
createVertexDegreeDiagonalMatrix(Graph<V,E> graph)
Returns a diagonal matrix whose diagonal entries contain the degree for the corresponding node. |
|
static
|
graphToSparseMatrix(Graph<V,E> g)
Returns an unweighted (0-1) adjacency matrix based on the specified graph. |
|
static
|
graphToSparseMatrix(Graph<V,E> g,
Map<E,Number> nev)
Returns a SparseDoubleMatrix2D whose entries represent the edge weights for the edges in g , as specified by nev . |
|
static
|
mapTo1DMatrix(Map<V,Number> map)
Converts a Map of (Vertex, Double) pairs to a DoubleMatrix1D. |
|
static
|
matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix,
org.apache.commons.collections15.Factory<? extends Graph<V,E>> graphFactory,
org.apache.commons.collections15.Factory<V> vertexFactory,
org.apache.commons.collections15.Factory<E> edgeFactory)
Creates a graph from a square (weighted) adjacency matrix. |
|
static
|
matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix,
org.apache.commons.collections15.Factory<? extends Graph<V,E>> graphFactory,
org.apache.commons.collections15.Factory<V> vertexFactory,
org.apache.commons.collections15.Factory<E> edgeFactory,
Map<E,Number> nev)
Creates a graph from a square (weighted) adjacency matrix. |
|
static
|
square(Graph<V,E> g,
org.apache.commons.collections15.Factory<E> edgeFactory,
MatrixElementOperations<E> 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 <V,E> Graph<V,E> square(Graph<V,E> g, org.apache.commons.collections15.Factory<E> edgeFactory, MatrixElementOperations<E> 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 <V,E> Graph<V,E> matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix, org.apache.commons.collections15.Factory<? extends Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, Map<E,Number> nev)
nev
is non-null then it will be used to store the edge weights.
Notes on implementation:
Property.isSymmetric
method may be used to find out whether the matrix
is symmetric prior to making this call.
matrix
as a JUNG
Graph
public static <V,E> Graph<V,E> matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix, org.apache.commons.collections15.Factory<? extends Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory)
matrix
as a JUNG Graph
public static <V,E> cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(Graph<V,E> g)
V
- the vertex typeE
- the edge typeg
- the graph to convert to a matrixpublic static <V,E> cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(Graph<V,E> g, Map<E,Number> 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 <V,E> cern.colt.matrix.impl.SparseDoubleMatrix2D createVertexDegreeDiagonalMatrix(Graph<V,E> graph)
NOTE: the vertices will be traversed in the order given by the graph's vertex
collection. If you want to be assured of a particular ordering, use a graph
implementation that guarantees such an ordering (see the implementations with Ordered
or Sorted
in their name).
public static <V,E> cern.colt.matrix.DoubleMatrix2D computeVoltagePotentialMatrix(UndirectedGraph<V,E> graph)
graph
- an undirected graph representing an electrical circuit
public static <V> cern.colt.matrix.DoubleMatrix1D mapTo1DMatrix(Map<V,Number> map)
Note: the vertices will appear in the output array in the order given
by map
's iterator. If you want a particular ordering, use a Map
implementation that provides such an ordering (SortedMap, LinkedHashMap
, etc.).
public static <V,E> cern.colt.matrix.DoubleMatrix2D computeMeanFirstPassageMatrix(Graph<V,E> G, Map<E,Number> edgeWeights, 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 calculatededgeWeights
- the edge weightsstationaryDistribution
- the asymptotic state probabilities
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |