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

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.HashMap;`
13 |  | `import java.util.Iterator;`
14 |  | `import java.util.Set;`
15 |  | ``
16 |  | `import edu.uci.ics.jung.graph.DirectedGraph;`
17 |  | `import edu.uci.ics.jung.graph.Edge;`
18 |  | `import edu.uci.ics.jung.graph.Element;`
19 |  | `import edu.uci.ics.jung.graph.Vertex;`
20 |  | `import edu.uci.ics.jung.utils.MutableDouble;`
21 |  | `import edu.uci.ics.jung.utils.UserData;`
22 |  | ``
23 |  | `/**`
24 |  | `* Algorithm variant of <code>PageRankWithPriors</code> that computes the importance of a node based upon taking fixed-length random`
25 |  | `* walks out from the root set and then computing the stationary probability of being at each node. Specifically, it computes`
26 |  | `* the relative probability that the markov chain will spend at any particular node, given that it start in the root`
27 |  | `* set and ends after k steps.`
28 |  | `* <p>`
29 |  | `* A simple example of usage is:`
30 |  | `* <pre>`
31 |  | `* KStepMarkov ranker = new KStepMarkov(someGraph,rootSet,6,null);`
32 |  | `* ranker.evaluate();`
33 |  | `* ranker.printRankings();`
34 |  | `* </pre>`
35 |  | `* <p>`
36 |  | `*`
37 |  | `* @author Scott White`
38 |  | `* @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"`
39 |  | `*/`
40 |  | `public class KStepMarkov extends RelativeAuthorityRanker {`
41 |  | `public final static String RANK_SCORE = "jung.algorithms.importance.KStepMarkovExperimental.RankScore";`
42 |  | `private final static String CURRENT_RANK = "jung.algorithms.importance.KStepMarkovExperimental.CurrentRank";`
43 |  | `private int mNumSteps;`
44 |  | `HashMap mPreviousRankingsMap;`
45 |  | ``
46 |  | `/**`
47 |  | `* Construct the algorihm instance and initializes the algorithm.`
48 |  | `* @param graph the graph to be analyzed`
49 |  | `* @param priors the set of root nodes`
50 |  | `* @param k positive integer parameter which controls the relative tradeoff between a distribution "biased" towards`
51 |  | `* R and the steady-state distribution which is independent of where the Markov-process started. Generally values`
52 |  | `* between 4-8 are reasonable`
53 |  | `* @param edgeWeightKeyName`
54 |  | `*/`
55 | 1 | `public KStepMarkov(DirectedGraph graph, Set priors, int k, String edgeWeightKeyName) {`
56 | 1 | `super.initialize(graph,true,false);`
57 | 1 | `mNumSteps = k;`
58 | 1 | `setPriors(priors);`
59 | 1 | `initializeRankings();`
60 | 1 | `if (edgeWeightKeyName == null) {`
61 | 0 | `assignDefaultEdgeTransitionWeights();`
62 |  | `} else {`
63 | 1 | `setUserDefinedEdgeWeightKey(edgeWeightKeyName);`
64 |  | `}`
65 | 1 | `normalizeEdgeTransitionWeights();`
66 | 1 | `}`
67 |  | ``
68 |  | `/**`
69 |  | `* The user datum key used to store the rank scores.`
70 |  | `* @return the key`
71 |  | `*/`
72 |  | `public String getRankScoreKey() {`
73 | 21 | `return RANK_SCORE;`
74 |  | `}`
75 |  | ``
76 |  | `protected void incrementRankScore(Element v, double rankValue) {`
77 | 6 | `MutableDouble value = (MutableDouble) v.getUserDatum(RANK_SCORE);`
78 |  | ``
79 | 6 | `value.add(rankValue);`
80 | 6 | `}`
81 |  | ``
82 |  | `protected double getCurrentRankScore(Element v) {`
83 | 6 | `return ((MutableDouble) v.getUserDatum(CURRENT_RANK)).doubleValue();`
84 |  | `}`
85 |  | ``
86 |  | `protected void setCurrentRankScore(Element v, double rankValue) {`
87 | 9 | `MutableDouble value = (MutableDouble) v.getUserDatum(CURRENT_RANK);`
88 |  | ``
89 | 9 | `if (value == null) {`
90 | 3 | `v.setUserDatum(CURRENT_RANK,new MutableDouble(rankValue),UserData.SHARED);`
91 |  | `} else {`
92 | 6 | `value.setDoubleValue(rankValue);`
93 |  | `}`
94 | 9 | `}`
95 |  | ``
96 |  | `protected void initializeRankings() {`
97 | 1 | `mPreviousRankingsMap = new HashMap();`
98 | 1 | `for (Iterator vIt = getVertices().iterator();vIt.hasNext();) {`
99 | 3 | `Vertex currentVertex = (Vertex) vIt.next();`
100 | 3 | `Set priors = getPriors();`
101 | 3 | `double numPriors = priors.size();`
102 |  | ``
103 | 3 | `if (getPriors().contains(currentVertex)) {`
104 | 2 | `setRankScore(currentVertex, 1.0/ numPriors);`
105 | 2 | `setCurrentRankScore(currentVertex, 1.0/ numPriors);`
106 | 2 | `mPreviousRankingsMap.put(currentVertex,new MutableDouble(1.0/numPriors));`
107 |  | `} else {`
108 | 1 | `setRankScore(currentVertex, 0);`
109 | 1 | `setCurrentRankScore(currentVertex, 0);`
110 | 1 | `mPreviousRankingsMap.put(currentVertex,new MutableDouble(0));`
111 |  | ``
112 |  | `}`
113 |  | `}`
114 | 1 | `}`
115 |  | `protected double evaluateIteration() {`
116 |  | ``
117 | 3 | `for (int i=0;i<mNumSteps;i++) {`
118 | 2 | `updateRankings();`
119 | 2 | `for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {`
120 | 6 | `Vertex currentVertex = (Vertex) vIt.next();`
121 | 6 | `double currentRankScore = getCurrentRankScore(currentVertex);`
122 | 6 | `MutableDouble previousRankScore = (MutableDouble) mPreviousRankingsMap.get(currentVertex);`
123 | 6 | `incrementRankScore(currentVertex,currentRankScore);`
124 | 6 | `previousRankScore.setDoubleValue(currentRankScore);`
125 |  | `}`
126 |  | `}`
127 |  | ``
128 | 1 | `normalizeRankings();`
129 |  | ``
130 | 1 | `return 0;`
131 |  | `}`
132 |  | ``
133 |  | `protected void onFinalize(Element udc) {`
134 | 3 | `udc.removeUserDatum(CURRENT_RANK);`
135 |  | ``
136 | 3 | `}`
137 |  | ``
138 |  | `protected void updateRankings() {`
139 |  | ``
140 | 2 | `for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {`
141 | 6 | `Vertex currentVertex = (Vertex) vIt.next();`
142 |  | ``
143 |  | `// Set incomingEdges = null;`
144 |  | `// if (getGraph().isDirected()) {`
145 |  | `// incomingEdges = currentVertex.getInEdges();`
146 |  | `// } else {`
147 |  | `// incomingEdges = currentVertex.getIncidentEdges();`
148 |  | `// }`
149 | 6 | `Set incomingEdges = currentVertex.getInEdges();`
150 |  | ``
151 | 6 | `double currentPageRankSum = 0;`
152 | 6 | `for (Iterator edgeIt = incomingEdges.iterator(); edgeIt.hasNext();) {`
153 | 12 | `Edge incomingEdge = (Edge) edgeIt.next();`
154 | 12 | `double currentWeight = getEdgeWeight(incomingEdge);`
155 | 12 | `currentPageRankSum += ((MutableDouble) mPreviousRankingsMap.get(incomingEdge.getOpposite(currentVertex))).doubleValue()*currentWeight;`
156 |  | `}`
157 |  | ``
158 | 6 | `setCurrentRankScore(currentVertex,currentPageRankSum);`
159 |  | `}`
160 |  | ``
161 | 2 | `}`
162 |  | `}`

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.