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

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