Class 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.

    See Also:
    MatrixElementOperations
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method 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.
      • 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 <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. 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 <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. If nev is non-null then it will be used to store the edge weights.

        Notes on implementation:

        • The matrix indices will be mapped onto vertices in the order in which the vertex factory generates the vertices. This means the user is responsible
        • The type of edges created (directed or undirected) depends entirely on the graph factory supplied, regardless of whether the matrix is symmetric or not. The Colt Property.isSymmetric method may be used to find out whether the matrix is symmetric prior to making this call.
        • The matrix supplied need not be square. If it is not square, then the
        Returns:
        a representation of matrix as a JUNG Graph
      • matrixToGraph

        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)
        Creates a graph from a square (weighted) adjacency matrix.
        Returns:
        a representation of matrix as a JUNG Graph
      • graphToSparseMatrix

        public 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.
        Type Parameters:
        V - the vertex type
        E - the edge type
        Parameters:
        g - the graph to convert to a matrix
      • graphToSparseMatrix

        public 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.

        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 <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.

        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).

        Returns:
        SparseDoubleMatrix2D
      • computeVoltagePotentialMatrix

        public 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. 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 <V> cern.colt.matrix.DoubleMatrix1D mapTo1DMatrix​(java.util.Map<V,​java.lang.Number> map)
        Converts a Map of (Vertex, Double) pairs to a DoubleMatrix1D.

        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.).

      • computeMeanFirstPassageMatrix

        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)
        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
        edgeWeights - the edge weights
        stationaryDistribution - the asymptotic state probabilities
        Returns:
        the mean first passage time matrix