Coverage details for edu.uci.ics.jung.algorithms.importance.PageRankWithPriors

LineHitsSource
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.HashSet;
13 import java.util.Iterator;
14 import java.util.Set;
15  
16 import edu.uci.ics.jung.algorithms.connectivity.BFSDistanceLabeler;
17 import edu.uci.ics.jung.graph.DirectedGraph;
18 import edu.uci.ics.jung.graph.Graph;
19 import edu.uci.ics.jung.graph.Vertex;
20 import edu.uci.ics.jung.utils.Pair;
21  
22 /**
23  * Algorithm that extends the PageRank algorithm by incorporating root nodes (priors). Whereas in PageRank
24  * the importance of a node is implicitly computed relative to all nodes in the graph now importance
25  * is computed relative to the specified root nodes.
26  * <p>
27  * Note: This algorithm uses the same key as PageRank for storing rank sccores
28  * <p>
29  * A simple example of usage is:
30  * <pre>
31  * PageRankWithPriors ranker = new PageRankWithPriors(someGraph,0.3,1,rootSet,null);
32  * ranker.evaluate();
33  * ranker.printRankings();
34  * </pre>
35  * <p>
36  * Running time: O(|E|*I) where |E| is the number of edges and I is the number of iterations until convergence
37  *
38  * @author Scott White
39  * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
40  */
41 public class PageRankWithPriors extends PageRank {
42  
43     /**
44      * Constructs an instance of the ranker.
45      * @param graph the graph whose nodes are being ranked
46      * @param beta the prior weight to put on the root nodes
47      * @param priors the set of root nodes
48      * @param edgeWeightKeyName the user datum key associated with any user-defined weights. If there are none,
49      * null should be passed in.
50      */
51     public PageRankWithPriors(DirectedGraph graph, double beta, Set priors, String edgeWeightKeyName) {
522        super(graph, beta, edgeWeightKeyName,computeReachableVertices(graph,priors));
532        setPriors(priors);
542        initializePriorWeights();
552    }
56  
57     protected void initializePriorWeights() {
582        Set allVertices = getVertices();
59  
602        Set priors = getPriors();
612        double numPriors = priors.size();
62  
632        Set nonPriors = new HashSet();
642        nonPriors.addAll(allVertices);
652        nonPriors.removeAll(priors);
66  
672        for (Iterator vIt = nonPriors.iterator(); vIt.hasNext();) {
6811            Vertex currentVertex = (Vertex) vIt.next();
6911            setPriorRankScore(currentVertex, 0.0);
70         }
71  
722        for (Iterator vIt = getPriors().iterator(); vIt.hasNext();) {
733            Vertex currentVertex = (Vertex) vIt.next();
743            setPriorRankScore(currentVertex, 1.0 / numPriors);
75         }
762    }
77  
78     private static Pair computeReachableVertices(Graph g, Set priors) {
79  
802        BFSDistanceLabeler labeler = new BFSDistanceLabeler("DISTANCE");
812        labeler.labelDistances(g, priors);
822        labeler.removeDecorations(g);
832        Pair p = new Pair(new HashSet(labeler.getVerticesInOrderVisited()),
84                           new HashSet(labeler.getUnivistedVertices()));
85  
862        return p;
87     }
88  
89     protected void reinitialize() {
900        super.reinitialize();
910        initializePriorWeights();
920    }
93 }

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.