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

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.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) {
390        this(graph,rootNodes,null);
400    }
41  
421    public MarkovCentrality(DirectedGraph graph, Set rootNodes, String edgeWeightKey) {
431        super.initialize(graph, true, false);
441        setPriors(rootNodes);
451        if (edgeWeightKey == null)
461            assignDefaultEdgeTransitionWeights();
47         else
480            setUserDefinedEdgeWeightKey(edgeWeightKey);
491        normalizeEdgeTransitionWeights();
50  
511        mIndexer = Indexer.getIndexer(graph);
521        mRankings = new SparseDoubleMatrix1D(graph.numVertices());
531    }
54  
55     /**
56      * @see edu.uci.ics.jung.algorithms.importance.AbstractRanker#getRankScoreKey()
57      */
58     public String getRankScoreKey() {
590        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) {
668        ArchetypeVertex v = (ArchetypeVertex) vert;
678        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) {
740        v.setUserDatum(getRankScoreKey(), new MutableDouble(rankValue), UserData.SHARED);
750    }
76  
77     /**
78      * @see edu.uci.ics.jung.algorithms.IterativeProcess#evaluateIteration()
79      */
80     protected double evaluateIteration() {
811        DoubleMatrix2D mFPTMatrix = GraphMatrixOperations.computeMeanFirstPassageMatrix(getGraph(), getEdgeWeightKeyName(), getStationaryDistribution());
82  
831        mRankings.assign(0);
84  
851        for (Iterator p_iter = getPriors().iterator(); p_iter.hasNext();) {
861            Vertex p = (Vertex) p_iter.next();
871            int p_id = mIndexer.getIndex(p);
881            for (Iterator v_iter = getVertices().iterator(); v_iter.hasNext();) {
894                Vertex v = (Vertex) v_iter.next();
904                int v_id = mIndexer.getIndex(v);
914                mRankings.set(v_id, mRankings.get(v_id) + mFPTMatrix.get(p_id, v_id));
92             }
93         }
94  
951        for (Iterator v_iter = getVertices().iterator(); v_iter.hasNext();) {
964            Vertex v = (Vertex) v_iter.next();
974            int v_id = mIndexer.getIndex(v);
984            mRankings.set(v_id, 1 / (mRankings.get(v_id) / getPriors().size()));
99         }
100  
1011        double total = mRankings.zSum();
102  
1031        for (Iterator v_iter = getVertices().iterator(); v_iter.hasNext();) {
1044            Vertex v = (Vertex) v_iter.next();
1054            int v_id = mIndexer.getIndex(v);
1064            mRankings.set(v_id, mRankings.get(v_id) / total);
107         }
108  
1091        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() {
1201        DoubleMatrix1D piVector = new DenseDoubleMatrix1D(getVertices().size());
1211        PageRank pageRank = new PageRank((DirectedGraph) getGraph(), 0, getEdgeWeightKeyName());
1221        pageRank.evaluate();
1231        List rankings = pageRank.getRankings();
124  
1251        for (Iterator r_iter = rankings.iterator(); r_iter.hasNext();) {
1264            NodeRanking rank = (NodeRanking) r_iter.next();
1274            piVector.set(mIndexer.getIndex(rank.vertex), rank.rankScore);
128         }
1291        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.