Line | Hits | Source |
---|---|---|
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 | */ | |
46 | 0 | public 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 | |
62 | 1 | Graph G2 = (Graph) g.newInstance(); |
63 | 1 | Set V = g.getVertices(); |
64 | 1 | for (Iterator it = V.iterator(); it.hasNext();) |
65 | { | |
66 | 10 | Vertex v = (Vertex) it.next(); |
67 | 10 | v.copy(G2); |
68 | } | |
69 | 1 | Iterator vertices = V.iterator(); |
70 | 11 | while (vertices.hasNext()) |
71 | { | |
72 | 10 | Vertex v = (Vertex) vertices.next(); |
73 | 10 | Iterator preds = v.getPredecessors().iterator(); |
74 | 25 | while (preds.hasNext()) |
75 | { | |
76 | 15 | Vertex src = (Vertex) preds.next(); |
77 | // get vertex in G2 with same ID | |
78 | 15 | Vertex d2_src = (Vertex) src.getEqualVertex(G2); |
79 | // get the edge connecting src to v in G | |
80 | 15 | Edge e1 = src.findEdge(v); |
81 | 15 | Iterator succs = v.getSuccessors().iterator(); |
82 | 36 | while (succs.hasNext()) |
83 | { | |
84 | 21 | Vertex dest = (Vertex) succs.next(); |
85 | // get vertex in G2 with same ID | |
86 | 21 | Vertex d2_dest = (Vertex) dest.getEqualVertex(G2); |
87 | // get edge connecting v to dest in G | |
88 | 21 | Edge e2 = v.findEdge(dest); |
89 | // collect data on path composed of e1 and e2 | |
90 | 21 | Object pathData = meo.computePathData(e1, e2); |
91 | 21 | Edge e = d2_src.findEdge(d2_dest); |
92 | // if no edge from src to dest exists in G2, create one | |
93 | 21 | if (e == null) |
94 | 18 | e = GraphUtils.addEdge(G2, d2_src, d2_dest); |
95 | 21 | meo.mergePaths(e, pathData); |
96 | } | |
97 | } | |
98 | } | |
99 | 1 | 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 | { | |
115 | 4 | if (matrix.rows() != matrix.columns()) |
116 | { | |
117 | 0 | throw new IllegalArgumentException("Matrix must be square."); |
118 | } | |
119 | 4 | int size = matrix.rows(); |
120 | 4 | boolean isSymmetric = true; |
121 | 14 | outer: for (int i = 0; i < size; i++) |
122 | { | |
123 | 116 | for (int j = 0; j < size; j++) |
124 | { | |
125 | 106 | if (matrix.getQuick(i, j) != matrix.getQuick(j, i)) |
126 | { | |
127 | 3 | isSymmetric = false; |
128 | 3 | break outer; |
129 | } | |
130 | } | |
131 | } | |
132 | ||
133 | Graph graph; | |
134 | 4 | if (isSymmetric) |
135 | 1 | graph = new UndirectedSparseGraph(); |
136 | else | |
137 | 3 | graph = new DirectedSparseGraph(); |
138 | ||
139 | 4 | GraphUtils.addVertices(graph, size); |
140 | 4 | Indexer id = Indexer.getIndexer(graph); |
141 | 34 | for (int i = 0; i < size; i++) |
142 | { | |
143 | 280 | for (int j = 0; j < size; j++) |
144 | { | |
145 | 250 | double value = matrix.getQuick(i, j); |
146 | 250 | if (value != 0) |
147 | { | |
148 | 57 | Vertex vI = (Vertex) id.getVertex(i); |
149 | 57 | Vertex vJ = (Vertex) id.getVertex(j); |
150 | 57 | Edge e = null; |
151 | 57 | if (isSymmetric) |
152 | { | |
153 | 30 | if (i <= j) |
154 | 15 | e = graph.addEdge(new UndirectedSparseEdge(vI, vJ)); |
155 | } | |
156 | else | |
157 | { | |
158 | 27 | e = graph.addEdge(new DirectedSparseEdge(vI, vJ)); |
159 | } | |
160 | 57 | if (e != null && nev != null) |
161 | 36 | nev.setNumber(e, new Double(value)); |
162 | } | |
163 | } | |
164 | } | |
165 | 4 | 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 | { | |
181 | 4 | if (weightKey == null) |
182 | 1 | return matrixToGraph(matrix, (NumberEdgeValue)null); |
183 | else | |
184 | { | |
185 | 3 | UserDatumNumberEdgeValue nev = new UserDatumNumberEdgeValue(weightKey); |
186 | 3 | nev.setCopyAction(UserData.SHARED); |
187 | 3 | 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 | { | |
203 | 0 | 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 | { | |
215 | 5 | if (edgeWeightKey == null) |
216 | 1 | return graphToSparseMatrix(g); |
217 | else | |
218 | 4 | return graphToSparseMatrix(g, new UserDatumNumberEdgeValue(edgeWeightKey)); |
219 | } | |
220 | ||
221 | public static SparseDoubleMatrix2D graphToSparseMatrix(Graph g) | |
222 | { | |
223 | 1 | 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 | { | |
241 | 6 | if (nev == null) |
242 | 1 | nev = new ConstantEdgeValue(1); |
243 | 6 | int numVertices = g.getVertices().size(); |
244 | 6 | SparseDoubleMatrix2D matrix = new SparseDoubleMatrix2D(numVertices, |
245 | numVertices); | |
246 | 6 | Indexer id = Indexer.getIndexer(g); |
247 | 51 | for (int i = 0; i < numVertices; i++) |
248 | { | |
249 | 45 | Vertex v = (Vertex)id.getVertex(i); |
250 | 45 | for (Iterator o_iter = v.getOutEdges().iterator(); o_iter.hasNext(); ) |
251 | { | |
252 | 108 | Edge e = (Edge)o_iter.next(); |
253 | 108 | Vertex w = e.getOpposite(v); |
254 | 108 | int j = id.getIndex(w); |
255 | 108 | matrix.set(i, j, matrix.getQuick(i,j) + nev.getNumber(e).doubleValue()); |
256 | } | |
257 | } | |
258 | 6 | 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 | { | |
269 | 1 | int numVertices = G.getVertices().size(); |
270 | 1 | SparseDoubleMatrix2D matrix = new SparseDoubleMatrix2D(numVertices, |
271 | numVertices); | |
272 | 1 | Indexer id = Indexer.getIndexer(G); |
273 | 1 | for (Iterator v_iter = G.getVertices().iterator(); v_iter.hasNext();) |
274 | { | |
275 | 11 | Vertex v = (Vertex) v_iter.next(); |
276 | 11 | matrix.set(id.getIndex(v), id.getIndex(v), v.degree()); |
277 | } | |
278 | 1 | 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 | { | |
301 | 1 | int numVertices = graph.numVertices(); |
302 | //create adjacency matrix from graph | |
303 | 1 | DoubleMatrix2D A = GraphMatrixOperations.graphToSparseMatrix(graph, |
304 | null); | |
305 | //create diagonal matrix of vertex degrees | |
306 | 1 | DoubleMatrix2D D = GraphMatrixOperations |
307 | .createVertexDegreeDiagonalMatrix(graph); | |
308 | 1 | DoubleMatrix2D temp = new SparseDoubleMatrix2D(numVertices - 1, |
309 | numVertices - 1); | |
310 | //compute D - A except for last row and column | |
311 | 11 | for (int i = 0; i < numVertices - 1; i++) |
312 | { | |
313 | 110 | for (int j = 0; j < numVertices - 1; j++) |
314 | { | |
315 | 100 | temp.set(i, j, D.get(i, j) - A.get(i, j)); |
316 | } | |
317 | } | |
318 | 1 | Algebra algebra = new Algebra(); |
319 | 1 | DoubleMatrix2D tempInverse = algebra.inverse(temp); |
320 | 1 | DoubleMatrix2D T = new SparseDoubleMatrix2D(numVertices, numVertices); |
321 | //compute "voltage" matrix | |
322 | 11 | for (int i = 0; i < numVertices - 1; i++) |
323 | { | |
324 | 110 | for (int j = 0; j < numVertices - 1; j++) |
325 | { | |
326 | 100 | T.set(i, j, tempInverse.get(i, j)); |
327 | } | |
328 | } | |
329 | 1 | 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 | { | |
337 | 0 | int numVertices = M.size(); |
338 | 0 | DoubleMatrix1D vector = new DenseDoubleMatrix1D(numVertices); |
339 | 0 | Set vertices = M.keySet(); |
340 | 0 | Indexer id = Indexer.getIndexer(((Vertex) vertices.iterator().next()) |
341 | .getGraph()); | |
342 | 0 | for (Iterator v_iter = vertices.iterator(); v_iter.hasNext();) |
343 | { | |
344 | 0 | Vertex v = (Vertex) v_iter.next(); |
345 | 0 | int v_id = id.getIndex(v); |
346 | 0 | if (v_id < 0 || v_id > numVertices) |
347 | 0 | throw new IllegalArgumentException("Vertex ID not " |
348 | + "supported by mapTo1DMatrix: outside range [0,n-1]"); | |
349 | 0 | vector.set(v_id, ((Double) M.get(v)).doubleValue()); |
350 | } | |
351 | 0 | 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 | { | |
381 | 1 | DoubleMatrix2D temp = GraphMatrixOperations.graphToSparseMatrix(G, |
382 | edgeWeightKey); | |
383 | 5 | for (int i = 0; i < temp.rows(); i++) |
384 | { | |
385 | 20 | for (int j = 0; j < temp.columns(); j++) |
386 | { | |
387 | 16 | double value = -1 * temp.get(i, j) |
388 | + stationaryDistribution.get(j); | |
389 | 16 | if (i == j) |
390 | 4 | value += 1; |
391 | 16 | if (value != 0) |
392 | 16 | temp.set(i, j, value); |
393 | } | |
394 | } | |
395 | 1 | Algebra algebra = new Algebra(); |
396 | 1 | DoubleMatrix2D fundamentalMatrix = algebra.inverse(temp); |
397 | 1 | temp = new SparseDoubleMatrix2D(temp.rows(), temp.columns()); |
398 | 5 | for (int i = 0; i < temp.rows(); i++) |
399 | { | |
400 | 20 | for (int j = 0; j < temp.columns(); j++) |
401 | { | |
402 | 16 | double value = -1.0 * fundamentalMatrix.get(i, j); |
403 | 16 | value += fundamentalMatrix.get(j, j); |
404 | 16 | if (i == j) |
405 | 4 | value += 1; |
406 | 16 | if (value != 0) |
407 | 16 | temp.set(i, j, value); |
408 | } | |
409 | } | |
410 | 1 | DoubleMatrix2D stationaryMatrixDiagonal = new SparseDoubleMatrix2D(temp |
411 | .rows(), temp.columns()); | |
412 | 1 | int numVertices = stationaryDistribution.size(); |
413 | 5 | for (int i = 0; i < numVertices; i++) |
414 | 4 | stationaryMatrixDiagonal.set(i, i, 1.0 / stationaryDistribution |
415 | .get(i)); | |
416 | 1 | DoubleMatrix2D meanFirstPassageMatrix = algebra.mult(temp, |
417 | stationaryMatrixDiagonal); | |
418 | 1 | return meanFirstPassageMatrix; |
419 | } | |
420 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |