# Coverage details for edu.uci.ics.jung.algorithms.importance.MarkovCentrality

Line | Hits | Source
--- | --- | ---
1 |  | `/*`
2 |  | `* Copyright (c) 2003, the JUNG Project and the Regents of the University`
3 |  | `* of California`
4 |  | `* All rights reserved.`
5 |  | `*`
6 |  | `* This software is open-source under the BSD license; see either`
7 |  | `* "license.txt" or`
8 |  | `* http://jung.sourceforge.net/license.txt for a description.`
9 |  | `*/`
10 |  | `package edu.uci.ics.jung.algorithms.importance;`
11 |  | ``
12 |  | `import java.util.Iterator;`
13 |  | `import java.util.List;`
14 |  | `import java.util.Set;`
15 |  | ``
16 |  | `import cern.colt.matrix.DoubleMatrix1D;`
17 |  | `import cern.colt.matrix.DoubleMatrix2D;`
18 |  | `import cern.colt.matrix.impl.DenseDoubleMatrix1D;`
19 |  | `import cern.colt.matrix.impl.SparseDoubleMatrix1D;`
20 |  | `import edu.uci.ics.jung.algorithms.GraphMatrixOperations;`
21 |  | `import edu.uci.ics.jung.graph.ArchetypeVertex;`
22 |  | `import edu.uci.ics.jung.graph.DirectedGraph;`
23 |  | `import edu.uci.ics.jung.graph.Element;`
24 |  | `import edu.uci.ics.jung.graph.Vertex;`
25 |  | `import edu.uci.ics.jung.graph.decorators.Indexer;`
26 |  | `import edu.uci.ics.jung.utils.MutableDouble;`
27 |  | `import edu.uci.ics.jung.utils.UserData;`
28 |  | ``
29 |  | `/**`
30 |  | `* @author Scott White and Joshua O'Madadhain`
31 |  | `* @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"`
32 |  | `*/`
33 |  | `public class MarkovCentrality extends RelativeAuthorityRanker {`
34 |  | `public final static String MEAN_FIRST_PASSAGE_TIME = "jung.algorithms.importance.mean_first_passage_time";`
35 |  | `private DoubleMatrix1D mRankings;`
36 |  | `private Indexer mIndexer;`
37 |  | ``
38 |  | `public MarkovCentrality(DirectedGraph graph, Set rootNodes) {`
39 | 0 | `this(graph,rootNodes,null);`
40 | 0 | `}`
41 |  | ``
42 | 1 | `public MarkovCentrality(DirectedGraph graph, Set rootNodes, String edgeWeightKey) {`
43 | 1 | `super.initialize(graph, true, false);`
44 | 1 | `setPriors(rootNodes);`
45 | 1 | `if (edgeWeightKey == null)`
46 | 1 | `assignDefaultEdgeTransitionWeights();`
47 |  | `else`
48 | 0 | `setUserDefinedEdgeWeightKey(edgeWeightKey);`
49 | 1 | `normalizeEdgeTransitionWeights();`
50 |  | ``
51 | 1 | `mIndexer = Indexer.getIndexer(graph);`
52 | 1 | `mRankings = new SparseDoubleMatrix1D(graph.numVertices());`
53 | 1 | `}`
54 |  | ``
55 |  | `/**`
56 |  | `* @see edu.uci.ics.jung.algorithms.importance.AbstractRanker#getRankScoreKey()`
57 |  | `*/`
58 |  | `public String getRankScoreKey() {`
59 | 0 | `return MEAN_FIRST_PASSAGE_TIME;`
60 |  | `}`
61 |  | ``
62 |  | `/**`
63 |  | `* @see edu.uci.ics.jung.algorithms.importance.AbstractRanker#getRankScore(edu.uci.ics.jung.graph.Element)`
64 |  | `*/`
65 |  | `public double getRankScore(Element vert) {`
66 | 8 | `ArchetypeVertex v = (ArchetypeVertex) vert;`
67 | 8 | `return mRankings.get(mIndexer.getIndex(v));`
68 |  | `}`
69 |  | ``
70 |  | `/**`
71 |  | `* @see edu.uci.ics.jung.algorithms.importance.AbstractRanker#setRankScore(edu.uci.ics.jung.graph.Element, double)`
72 |  | `*/`
73 |  | `protected void setRankScore(Element v, double rankValue) {`
74 | 0 | `v.setUserDatum(getRankScoreKey(), new MutableDouble(rankValue), UserData.SHARED);`
75 | 0 | `}`
76 |  | ``
77 |  | `/**`
78 |  | `* @see edu.uci.ics.jung.algorithms.IterativeProcess#evaluateIteration()`
79 |  | `*/`
80 |  | `protected double evaluateIteration() {`
81 | 1 | `DoubleMatrix2D mFPTMatrix = GraphMatrixOperations.computeMeanFirstPassageMatrix(getGraph(), getEdgeWeightKeyName(), getStationaryDistribution());`
82 |  | ``
83 | 1 | `mRankings.assign(0);`
84 |  | ``
85 | 1 | `for (Iterator p_iter = getPriors().iterator(); p_iter.hasNext();) {`
86 | 1 | `Vertex p = (Vertex) p_iter.next();`
87 | 1 | `int p_id = mIndexer.getIndex(p);`
88 | 1 | `for (Iterator v_iter = getVertices().iterator(); v_iter.hasNext();) {`
89 | 4 | `Vertex v = (Vertex) v_iter.next();`
90 | 4 | `int v_id = mIndexer.getIndex(v);`
91 | 4 | `mRankings.set(v_id, mRankings.get(v_id) + mFPTMatrix.get(p_id, v_id));`
92 |  | `}`
93 |  | `}`
94 |  | ``
95 | 1 | `for (Iterator v_iter = getVertices().iterator(); v_iter.hasNext();) {`
96 | 4 | `Vertex v = (Vertex) v_iter.next();`
97 | 4 | `int v_id = mIndexer.getIndex(v);`
98 | 4 | `mRankings.set(v_id, 1 / (mRankings.get(v_id) / getPriors().size()));`
99 |  | `}`
100 |  | ``
101 | 1 | `double total = mRankings.zSum();`
102 |  | ``
103 | 1 | `for (Iterator v_iter = getVertices().iterator(); v_iter.hasNext();) {`
104 | 4 | `Vertex v = (Vertex) v_iter.next();`
105 | 4 | `int v_id = mIndexer.getIndex(v);`
106 | 4 | `mRankings.set(v_id, mRankings.get(v_id) / total);`
107 |  | `}`
108 |  | ``
109 | 1 | `return 0;`
110 |  | `}`
111 |  | ``
112 |  | ``
113 |  | `/**`
114 |  | `* Loads the stationary distribution into a vector if it was passed in,`
115 |  | `* or calculates it if not.`
116 |  | `*`
117 |  | `* @return DoubleMatrix1D`
118 |  | `*/`
119 |  | `private DoubleMatrix1D getStationaryDistribution() {`
120 | 1 | `DoubleMatrix1D piVector = new DenseDoubleMatrix1D(getVertices().size());`
121 | 1 | `PageRank pageRank = new PageRank((DirectedGraph) getGraph(), 0, getEdgeWeightKeyName());`
122 | 1 | `pageRank.evaluate();`
123 | 1 | `List rankings = pageRank.getRankings();`
124 |  | ``
125 | 1 | `for (Iterator r_iter = rankings.iterator(); r_iter.hasNext();) {`
126 | 4 | `NodeRanking rank = (NodeRanking) r_iter.next();`
127 | 4 | `piVector.set(mIndexer.getIndex(rank.vertex), rank.rankScore);`
128 |  | `}`
129 | 1 | `return piVector;`
130 |  | `}`
131 |  | ``
132 |  | `}`

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.