jcoverage | summary | package | file

Coverage details for edu.uci.ics.jung.algorithms.GraphMatrixOperations

LineHitsSource
1 /*
2  * Copyright (c) 2003, the JUNG Project and the Regents of the University of
3  * California All rights reserved. This software is open-source under the BSD
4  * license; see either "license.txt" or http://jung.sourceforge.net/license.txt
5  * for a description.
6  */
7 package edu.uci.ics.jung.algorithms;
8  
9 import java.util.Iterator;
10 import java.util.Map;
11 import java.util.Set;
12  
13 import cern.colt.matrix.DoubleMatrix1D;
14 import cern.colt.matrix.DoubleMatrix2D;
15 import cern.colt.matrix.impl.DenseDoubleMatrix1D;
16 import cern.colt.matrix.impl.SparseDoubleMatrix2D;
17 import cern.colt.matrix.linalg.Algebra;
18 import edu.uci.ics.jung.graph.Edge;
19 import edu.uci.ics.jung.graph.Graph;
20 import edu.uci.ics.jung.graph.UndirectedGraph;
21 import edu.uci.ics.jung.graph.Vertex;
22 import edu.uci.ics.jung.graph.decorators.ConstantEdgeValue;
23 import edu.uci.ics.jung.graph.decorators.Indexer;
24 import edu.uci.ics.jung.graph.decorators.NumberEdgeValue;
25 import edu.uci.ics.jung.graph.decorators.UserDatumNumberEdgeValue;
26 import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;
27 import edu.uci.ics.jung.graph.impl.DirectedSparseGraph;
28 import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
29 import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;
30 import edu.uci.ics.jung.utils.GraphUtils;
31 import edu.uci.ics.jung.utils.UserData;
32  
33 /**
34  * Contains methods for performing the analogues of certain matrix operations on
35  * graphs.
36  * <p>
37  * These implementations are efficient on sparse graphs, but may not be the best
38  * implementations for very dense graphs.
39  * <P>
40  * Anticipated additions to this class: methods for taking products and inverses
41  * of graphs.
42  *
43  * @author Joshua O'Madadhain
44  * @see MatrixElementOperations
45  */
460public class GraphMatrixOperations
47 {
48     /**
49      * Returns the graph that corresponds to the square of the (weighted)
50      * adjacency matrix that the specified graph <code>g</code> encodes. The
51      * implementation of MatrixElementOperations that is furnished to the
52      * constructor specifies the implementation of the dot product, which is an
53      * integral part of matrix multiplication.
54      *
55      * @param g
56      * the graph to be squared
57      * @return the result of squaring g
58      */
59     public static Graph square(Graph g, MatrixElementOperations meo)
60     {
61         // create new graph of same type
621        Graph G2 = (Graph) g.newInstance();
631        Set V = g.getVertices();
641        for (Iterator it = V.iterator(); it.hasNext();)
65         {
6610            Vertex v = (Vertex) it.next();
6710            v.copy(G2);
68         }
691        Iterator vertices = V.iterator();
7011        while (vertices.hasNext())
71         {
7210            Vertex v = (Vertex) vertices.next();
7310            Iterator preds = v.getPredecessors().iterator();
7425            while (preds.hasNext())
75             {
7615                Vertex src = (Vertex) preds.next();
77                 // get vertex in G2 with same ID
7815                Vertex d2_src = (Vertex) src.getEqualVertex(G2);
79                 // get the edge connecting src to v in G
8015                Edge e1 = src.findEdge(v);
8115                Iterator succs = v.getSuccessors().iterator();
8236                while (succs.hasNext())
83                 {
8421                    Vertex dest = (Vertex) succs.next();
85                     // get vertex in G2 with same ID
8621                    Vertex d2_dest = (Vertex) dest.getEqualVertex(G2);
87                     // get edge connecting v to dest in G
8821                    Edge e2 = v.findEdge(dest);
89                     // collect data on path composed of e1 and e2
9021                    Object pathData = meo.computePathData(e1, e2);
9121                    Edge e = d2_src.findEdge(d2_dest);
92                     // if no edge from src to dest exists in G2, create one
9321                    if (e == null)
9418                        e = GraphUtils.addEdge(G2, d2_src, d2_dest);
9521                    meo.mergePaths(e, pathData);
96                 }
97             }
98         }
991        return G2;
100     }
101  
102     /**
103      * Creates a graph from a square (weighted) adjacency matrix. If
104      * <code>nev</code> is non-null then
105      * the weight is stored as a Double as specified by the implementation
106      * of <code>nev</code>. If the matrix is symmetric, then the graph will
107      * be constructed as a sparse undirected graph; otherwise,
108      * it will be constructed as a sparse directed graph.
109      *
110      * @return a representation of <code>matrix</code> as a JUNG
111      * <code>Graph</code>
112      */
113     public static Graph matrixToGraph(DoubleMatrix2D matrix, NumberEdgeValue nev)
114     {
1154        if (matrix.rows() != matrix.columns())
116         {
1170            throw new IllegalArgumentException("Matrix must be square.");
118         }
1194        int size = matrix.rows();
1204        boolean isSymmetric = true;
12114        outer: for (int i = 0; i < size; i++)
122         {
123116            for (int j = 0; j < size; j++)
124             {
125106                if (matrix.getQuick(i, j) != matrix.getQuick(j, i))
126                 {
1273                    isSymmetric = false;
1283                    break outer;
129                 }
130             }
131         }
132         
133         Graph graph;
1344        if (isSymmetric)
1351            graph = new UndirectedSparseGraph();
136         else
1373            graph = new DirectedSparseGraph();
138         
1394        GraphUtils.addVertices(graph, size);
1404        Indexer id = Indexer.getIndexer(graph);
14134        for (int i = 0; i < size; i++)
142         {
143280            for (int j = 0; j < size; j++)
144             {
145250                double value = matrix.getQuick(i, j);
146250                if (value != 0)
147                 {
14857                    Vertex vI = (Vertex) id.getVertex(i);
14957                    Vertex vJ = (Vertex) id.getVertex(j);
15057                    Edge e = null;
15157                    if (isSymmetric)
152                     {
15330                        if (i <= j)
15415                            e = graph.addEdge(new UndirectedSparseEdge(vI, vJ));
155                     }
156                     else
157                     {
15827                        e = graph.addEdge(new DirectedSparseEdge(vI, vJ));
159                     }
16057                    if (e != null && nev != null)
16136                        nev.setNumber(e, new Double(value));
162                 }
163             }
164         }
1654        return graph;
166     }
167     
168     /**
169      * Creates a graph from a square (weighted) adjacency matrix.
170      * If the weight key is non-null then
171      * the weight is stored as a Double in the given edge's user data under the
172      * specified key name. If the matrix is symmetric, then the graph will
173      * be constructed as a sparse undirected graph; otherwise
174      * it will be constructed as a sparse directed graph.
175      *
176      * @param weightKey the user data key to use to store or retrieve the edge weights
177      * @return a representation of <code>matrix</code> as a JUNG <code>Graph</code>
178      */
179     public static Graph matrixToGraph(DoubleMatrix2D matrix, String weightKey)
180     {
1814        if (weightKey == null)
1821            return matrixToGraph(matrix, (NumberEdgeValue)null);
183         else
184         {
1853            UserDatumNumberEdgeValue nev = new UserDatumNumberEdgeValue(weightKey);
1863            nev.setCopyAction(UserData.SHARED);
1873            return matrixToGraph(matrix, nev);
188         }
189     }
190  
191     
192     
193     /**
194      * Creates a graph from a square (weighted) adjacency matrix.
195      * Equivalent to <code>matrixToGraph(matrix, (NumberEdgeValue)null)</code>.
196      *
197      * @return a representation of <code>matrix</code> as a JUNG <code>Graph</code>
198      *
199      * @see #matrixToGraph(DoubleMatrix2D, NumberEdgeValue)
200      */
201     public static Graph matrixToGraph(DoubleMatrix2D matrix)
202     {
2030        return matrixToGraph(matrix, (NumberEdgeValue)null);
204     }
205     
206     /**
207      * Returns a SparseDoubleMatrix2D which represents the edge weights of the
208      * input Graph.
209      *
210      * @return SparseDoubleMatrix2D
211      */
212     public static SparseDoubleMatrix2D graphToSparseMatrix(Graph g,
213             Object edgeWeightKey)
214     {
2155        if (edgeWeightKey == null)
2161            return graphToSparseMatrix(g);
217         else
2184            return graphToSparseMatrix(g, new UserDatumNumberEdgeValue(edgeWeightKey));
219     }
220     
221     public static SparseDoubleMatrix2D graphToSparseMatrix(Graph g)
222     {
2231        return graphToSparseMatrix(g, new ConstantEdgeValue(1));
224     }
225     
226     /**
227      * Returns a SparseDoubleMatrix2D whose entries represent the edge weights for the
228      * edges in <code>g</code>, as specified by <code>nev</code>.
229      *
230      * <p>The <code>(i,j)</code> entry of the matrix returned will be equal to the sum
231      * of the weights of the edges connecting the vertex with index <code>i</code> to
232      * <code>j</code>.
233      *
234      * <p>If <code>nev</code> is <code>null</code>, then a constant edge weight of 1 is used.
235      *
236      * @param g
237      * @param nev
238      */
239     public static SparseDoubleMatrix2D graphToSparseMatrix(Graph g, NumberEdgeValue nev)
240     {
2416        if (nev == null)
2421            nev = new ConstantEdgeValue(1);
2436        int numVertices = g.getVertices().size();
2446        SparseDoubleMatrix2D matrix = new SparseDoubleMatrix2D(numVertices,
245                 numVertices);
2466        Indexer id = Indexer.getIndexer(g);
24751        for (int i = 0; i < numVertices; i++)
248         {
24945            Vertex v = (Vertex)id.getVertex(i);
25045            for (Iterator o_iter = v.getOutEdges().iterator(); o_iter.hasNext(); )
251             {
252108                Edge e = (Edge)o_iter.next();
253108                Vertex w = e.getOpposite(v);
254108                int j = id.getIndex(w);
255108                matrix.set(i, j, matrix.getQuick(i,j) + nev.getNumber(e).doubleValue());
256             }
257         }
2586        return matrix;
259     }
260  
261     /**
262      * Returns a diagonal matrix whose diagonal entries contain the degree for
263      * the corresponding node.
264      *
265      * @return SparseDoubleMatrix2D
266      */
267     public static SparseDoubleMatrix2D createVertexDegreeDiagonalMatrix(Graph G)
268     {
2691        int numVertices = G.getVertices().size();
2701        SparseDoubleMatrix2D matrix = new SparseDoubleMatrix2D(numVertices,
271                 numVertices);
2721        Indexer id = Indexer.getIndexer(G);
2731        for (Iterator v_iter = G.getVertices().iterator(); v_iter.hasNext();)
274         {
27511            Vertex v = (Vertex) v_iter.next();
27611            matrix.set(id.getIndex(v), id.getIndex(v), v.degree());
277         }
2781        return matrix;
279     }
280  
281     /**
282      * The idea here is based on the metaphor of an electric circuit. We assume
283      * that an undirected graph represents the structure of an electrical
284      * circuit where each edge has unit resistance. One unit of current is
285      * injected into any arbitrary vertex s and one unit of current is extracted
286      * from any arbitrary vertex t. The voltage at some vertex i for source
287      * vertex s and target vertex t can then be measured according to the
288      * equation: V_i^(s,t) = T_is - T-it where T is the voltage potential matrix
289      * returned by this method. *
290      *
291      * @param graph
292      * an undirected graph representing an electrical circuit
293      * @return the voltage potential matrix
294      * @see "P. Doyle and J. Snell, 'Random walks and electric networks,', 1989"
295      * @see "M. Newman, 'A measure of betweenness centrality based on random
296      * walks', pp. 5-7, 2003"
297      */
298     public static DoubleMatrix2D computeVoltagePotentialMatrix(
299             UndirectedGraph graph)
300     {
3011        int numVertices = graph.numVertices();
302         //create adjacency matrix from graph
3031        DoubleMatrix2D A = GraphMatrixOperations.graphToSparseMatrix(graph,
304                 null);
305         //create diagonal matrix of vertex degrees
3061        DoubleMatrix2D D = GraphMatrixOperations
307                 .createVertexDegreeDiagonalMatrix(graph);
3081        DoubleMatrix2D temp = new SparseDoubleMatrix2D(numVertices - 1,
309                 numVertices - 1);
310         //compute D - A except for last row and column
31111        for (int i = 0; i < numVertices - 1; i++)
312         {
313110            for (int j = 0; j < numVertices - 1; j++)
314             {
315100                temp.set(i, j, D.get(i, j) - A.get(i, j));
316             }
317         }
3181        Algebra algebra = new Algebra();
3191        DoubleMatrix2D tempInverse = algebra.inverse(temp);
3201        DoubleMatrix2D T = new SparseDoubleMatrix2D(numVertices, numVertices);
321         //compute "voltage" matrix
32211        for (int i = 0; i < numVertices - 1; i++)
323         {
324110            for (int j = 0; j < numVertices - 1; j++)
325             {
326100                T.set(i, j, tempInverse.get(i, j));
327             }
328         }
3291        return T;
330     }
331  
332     /**
333      * Converts a Map of (Vertex, Double) pairs to a DoubleMatrix1D.
334      */
335     public static DoubleMatrix1D mapTo1DMatrix(Map M)
336     {
3370        int numVertices = M.size();
3380        DoubleMatrix1D vector = new DenseDoubleMatrix1D(numVertices);
3390        Set vertices = M.keySet();
3400        Indexer id = Indexer.getIndexer(((Vertex) vertices.iterator().next())
341                 .getGraph());
3420        for (Iterator v_iter = vertices.iterator(); v_iter.hasNext();)
343         {
3440            Vertex v = (Vertex) v_iter.next();
3450            int v_id = id.getIndex(v);
3460            if (v_id < 0 || v_id > numVertices)
3470                throw new IllegalArgumentException("Vertex ID not "
348                         + "supported by mapTo1DMatrix: outside range [0,n-1]");
3490            vector.set(v_id, ((Double) M.get(v)).doubleValue());
350         }
3510        return vector;
352     }
353  
354     /**
355      * Computes the all-pairs mean first passage time for the specified graph,
356      * given an existing stationary probability distribution.
357      * <P>
358      * The mean first passage time from vertex v to vertex w is defined, for a
359      * Markov network (in which the vertices represent states and the edge
360      * weights represent state->state transition probabilities), as the expected
361      * number of steps required to travel from v to w if the steps occur
362      * according to the transition probabilities.
363      * <P>
364      * The stationary distribution is the fraction of time, in the limit as the
365      * number of state transitions approaches infinity, that a given state will
366      * have been visited. Equivalently, it is the probability that a given state
367      * will be the current state after an arbitrarily large number of state
368      * transitions.
369      *
370      * @param G
371      * the graph on which the MFPT will be calculated
372      * @param edgeWeightKey
373      * the user data key for the edge weights
374      * @param stationaryDistribution
375      * the asymptotic state probabilities
376      * @return the mean first passage time matrix
377      */
378     public static DoubleMatrix2D computeMeanFirstPassageMatrix(Graph G,
379             Object edgeWeightKey, DoubleMatrix1D stationaryDistribution)
380     {
3811        DoubleMatrix2D temp = GraphMatrixOperations.graphToSparseMatrix(G,
382                 edgeWeightKey);
3835        for (int i = 0; i < temp.rows(); i++)
384         {
38520            for (int j = 0; j < temp.columns(); j++)
386             {
38716                double value = -1 * temp.get(i, j)
388                         + stationaryDistribution.get(j);
38916                if (i == j)
3904                    value += 1;
39116                if (value != 0)
39216                    temp.set(i, j, value);
393             }
394         }
3951        Algebra algebra = new Algebra();
3961        DoubleMatrix2D fundamentalMatrix = algebra.inverse(temp);
3971        temp = new SparseDoubleMatrix2D(temp.rows(), temp.columns());
3985        for (int i = 0; i < temp.rows(); i++)
399         {
40020            for (int j = 0; j < temp.columns(); j++)
401             {
40216                double value = -1.0 * fundamentalMatrix.get(i, j);
40316                value += fundamentalMatrix.get(j, j);
40416                if (i == j)
4054                    value += 1;
40616                if (value != 0)
40716                    temp.set(i, j, value);
408             }
409         }
4101        DoubleMatrix2D stationaryMatrixDiagonal = new SparseDoubleMatrix2D(temp
411                 .rows(), temp.columns());
4121        int numVertices = stationaryDistribution.size();
4135        for (int i = 0; i < numVertices; i++)
4144            stationaryMatrixDiagonal.set(i, i, 1.0 / stationaryDistribution
415                     .get(i));
4161        DoubleMatrix2D meanFirstPassageMatrix = algebra.mult(temp,
417                 stationaryMatrixDiagonal);
4181        return meanFirstPassageMatrix;
419     }
420 }

jcoverage | summary | package | file

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.