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

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  
14 import cern.colt.matrix.DoubleMatrix2D;
15 import edu.uci.ics.jung.algorithms.GraphMatrixOperations;
16 import edu.uci.ics.jung.graph.UndirectedGraph;
17 import edu.uci.ics.jung.graph.Vertex;
18 import edu.uci.ics.jung.graph.decorators.Indexer;
19  
20 /**
21  * /**
22  * Computes s-t betweenness centrality for each vertex in the graph. The betweenness values in this case
23  * are based on random walks, measuring the expected number of times a node is traversed by a random walk
24  * from s to t. The result is that each vertex has a UserData element of type
25  * MutableDouble whose key is 'centrality.RandomWalkBetweennessCentrality'
26  *
27  * A simple example of usage is: <br>
28  * RandomWalkSTBetweenness ranker = new RandomWalkBetweenness(someGraph,someSource,someTarget); <br>
29  * ranker.evaluate(); <br>
30  * ranker.printRankings(); <p>
31  *
32  * Running time is: O(n^3).
33  * @see "Mark Newman: A measure of betweenness centrality based on random walks, 2002."
34  
35  * @author Scott White
36  */
37 public class RandomWalkSTBetweenness extends AbstractRanker {
38  
39     public static final String CENTRALITY = "centrality.RandomWalkSTBetweennessCentrality";
40     private DoubleMatrix2D mVoltageMatrix;
41     private Indexer mIndexer;
42     Vertex mSource;
43     Vertex mTarget;
44  
45    /**
46     * Constructor which initializes the algorithm
47     * @param g the graph whose nodes are to be analyzed
48     * @param s the source vertex
49     * @param t the target vertex
50     */
511    public RandomWalkSTBetweenness(UndirectedGraph g, Vertex s, Vertex t) {
521        initialize(g, true, false);
531        mSource = s;
541        mTarget = t;
551    }
56  
57     protected Indexer getIndexer() {
581210        return mIndexer;
59     }
60  
61     protected DoubleMatrix2D getVoltageMatrix() {
620        return mVoltageMatrix;
63     }
64  
65     protected void setUp() {
661        mVoltageMatrix = GraphMatrixOperations.computeVoltagePotentialMatrix((UndirectedGraph) getGraph());
671        mIndexer = Indexer.getIndexer(getGraph());
681    }
69  
70     protected void computeBetweenness() {
710        setUp();
72  
730        for (Iterator iIt = getGraph().getVertices().iterator();iIt.hasNext();) {
740            Vertex ithVertex = (Vertex) iIt.next();
75  
760            setRankScore(ithVertex,computeSTBetweenness(ithVertex,mSource, mTarget));
77         }
780    }
79  
80     public double computeSTBetweenness(Vertex ithVertex, Vertex source, Vertex target) {
81605        if (ithVertex == source || ithVertex == target) return 1;
82495        if (mVoltageMatrix == null) {
830            setUp();
84         }
85495        int i = mIndexer.getIndex(ithVertex);
86495        int s = mIndexer.getIndex(source);
87495        int t = mIndexer.getIndex(target);
88  
89495        double betweenness = 0;
90495        for (Iterator vIt = ithVertex.getSuccessors().iterator();vIt.hasNext();) {
912070            Vertex jthVertex = (Vertex) vIt.next();
922070            int j = mIndexer.getIndex(jthVertex);
932070            double currentFlow = 0;
942070            currentFlow += mVoltageMatrix.get(i,s);
952070            currentFlow -= mVoltageMatrix.get(i,t);
962070            currentFlow -= mVoltageMatrix.get(j,s);
972070            currentFlow += mVoltageMatrix.get(j,t);
982070            betweenness += Math.abs(currentFlow);
99         }
100  
101495        return betweenness/2.0;
102  
103     }
104  
105     /**
106      * the user datum key used to store the rank scores
107      * @return the key
108      */
109     public String getRankScoreKey() {
1100        return CENTRALITY;
111     }
112  
113     protected double evaluateIteration() {
1140        computeBetweenness();
1150        return 0;
116     }
117 }

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.