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.
MatrixElementOperations
Constructor and Description |
---|
GraphMatrixOperations() |
Modifier and Type | Method and Description |
---|---|
static <V,E> cern.colt.matrix.DoubleMatrix2D |
computeMeanFirstPassageMatrix(edu.uci.ics.jung.graph.Graph<V,E> G,
java.util.Map<E,java.lang.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 <V,E> cern.colt.matrix.DoubleMatrix2D |
computeVoltagePotentialMatrix(edu.uci.ics.jung.graph.UndirectedGraph<V,E> graph)
The idea here is based on the metaphor of an electric circuit.
|
static <V,E> cern.colt.matrix.impl.SparseDoubleMatrix2D |
createVertexDegreeDiagonalMatrix(edu.uci.ics.jung.graph.Graph<V,E> graph)
Returns a diagonal matrix whose diagonal entries contain the degree for
the corresponding node.
|
static <V,E> cern.colt.matrix.impl.SparseDoubleMatrix2D |
graphToSparseMatrix(edu.uci.ics.jung.graph.Graph<V,E> g)
Returns an unweighted (0-1) adjacency matrix based on the specified graph.
|
static <V,E> cern.colt.matrix.impl.SparseDoubleMatrix2D |
graphToSparseMatrix(edu.uci.ics.jung.graph.Graph<V,E> g,
java.util.Map<E,java.lang.Number> nev)
Returns a SparseDoubleMatrix2D whose entries represent the edge weights for the
edges in
g , as specified by nev . |
static <V> cern.colt.matrix.DoubleMatrix1D |
mapTo1DMatrix(java.util.Map<V,java.lang.Number> map)
Converts a Map of (Vertex, Double) pairs to a DoubleMatrix1D.
|
static <V,E> edu.uci.ics.jung.graph.Graph<V,E> |
matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix,
org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
org.apache.commons.collections4.Factory<V> vertexFactory,
org.apache.commons.collections4.Factory<E> edgeFactory)
Creates a graph from a square (weighted) adjacency matrix.
|
static <V,E> edu.uci.ics.jung.graph.Graph<V,E> |
matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix,
org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
org.apache.commons.collections4.Factory<V> vertexFactory,
org.apache.commons.collections4.Factory<E> edgeFactory,
java.util.Map<E,java.lang.Number> nev)
Creates a graph from a square (weighted) adjacency matrix.
|
static <V,E> edu.uci.ics.jung.graph.Graph<V,E> |
square(edu.uci.ics.jung.graph.Graph<V,E> g,
org.apache.commons.collections4.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. |
public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> square(edu.uci.ics.jung.graph.Graph<V,E> g, org.apache.commons.collections4.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 squaredpublic static <V,E> edu.uci.ics.jung.graph.Graph<V,E> matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix, org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections4.Factory<V> vertexFactory, org.apache.commons.collections4.Factory<E> edgeFactory, java.util.Map<E,java.lang.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> edu.uci.ics.jung.graph.Graph<V,E> matrixToGraph(cern.colt.matrix.DoubleMatrix2D matrix, org.apache.commons.collections4.Factory<? extends edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections4.Factory<V> vertexFactory, org.apache.commons.collections4.Factory<E> edgeFactory)
matrix
as a JUNG Graph
public static <V,E> cern.colt.matrix.impl.SparseDoubleMatrix2D graphToSparseMatrix(edu.uci.ics.jung.graph.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(edu.uci.ics.jung.graph.Graph<V,E> g, java.util.Map<E,java.lang.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(edu.uci.ics.jung.graph.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(edu.uci.ics.jung.graph.UndirectedGraph<V,E> graph)
graph
- an undirected graph representing an electrical circuitpublic static <V> cern.colt.matrix.DoubleMatrix1D mapTo1DMatrix(java.util.Map<V,java.lang.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(edu.uci.ics.jung.graph.Graph<V,E> G, java.util.Map<E,java.lang.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