jcoverage | summary | package | file

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

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.ArrayList;
13 import java.util.Collections;
14 import java.util.Iterator;
15 import java.util.List;
16 import java.util.Set;
17  
18 import cern.colt.list.DoubleArrayList;
19 import corejava.Format;
20 import edu.uci.ics.jung.algorithms.IterativeProcess;
21 import edu.uci.ics.jung.exceptions.FatalException;
22 import edu.uci.ics.jung.graph.Edge;
23 import edu.uci.ics.jung.graph.Element;
24 import edu.uci.ics.jung.graph.Graph;
25 import edu.uci.ics.jung.graph.Vertex;
26 import edu.uci.ics.jung.graph.decorators.StringLabeller;
27 import edu.uci.ics.jung.utils.MutableDouble;
28 import edu.uci.ics.jung.utils.UserData;
29  
30 /**
31  * Abstract class for algorithms that rank nodes or edges by some "importance" metric. Provides a common set of
32  * services such as:
33  * <ul>
34  * <li> storing rank scores</li>
35  * <li> getters and setters for rank scores</li>
36  * <li> computing default edge weights</li>
37  * <li> normalizing default or user-provided edge transition weights </li>
38  * <li> normalizing rank scores</li>
39  * <li> automatic cleanup of decorations</li>
40  * <li> creation of Ranking list</li>
41  * <li>print rankings in sorted order by rank</li>
42  * </ul>
43  * <p>
44  * By default, all rank scores are removed from the vertices (or edges) being ranked.
45  * @author Scott White
46  */
4724public abstract class AbstractRanker extends IterativeProcess {
48     private Graph mGraph;
49     private List mRankings;
50     public static final String DEFAULT_EDGE_WEIGHT_KEY = "jung.algorithms.importance.AbstractRanker.EdgeWeight";
51     private String mUserDefinedEdgeWeightKey;
52     private boolean mRemoveRankScoresOnFinalize;
53     private boolean mRankNodes;
54     private boolean mRankEdges;
55     private boolean mNormalizeRankings;
56  
57     protected void initialize(Graph graph, boolean isNodeRanker,
58         boolean isEdgeRanker)
59     {
6024        if (!isNodeRanker && !isEdgeRanker)
610            throw new IllegalArgumentException("Must rank edges, vertices, or both");
6224        mGraph = graph;
6324        mRemoveRankScoresOnFinalize = true;
6424        mNormalizeRankings = true;
6524        mUserDefinedEdgeWeightKey = null;
6624        mRankNodes = isNodeRanker;
6724        mRankEdges = isEdgeRanker;
6824    }
69     
70     protected Set getVertices() {
71553        return mGraph.getVertices();
72     }
73  
74     protected Graph getGraph() {
7521        return mGraph;
76     }
77  
78     protected void reinitialize() {
790    }
80  
81     /**
82      * Returns <code>true</code> if this ranker ranks nodes, and
83      * <code>false</code> otherwise.
84      */
85     public boolean isRankingNodes() {
860        return mRankNodes;
87     }
88  
89     /**
90      * Returns <code>true</code> if this ranker ranks edges, and
91      * <code>false</code> otherwise.
92      */
93     public boolean isRankingEdges()
94     {
950        return mRankEdges;
96     }
97     
98     /**
99      * Instructs the ranker whether or not it should remove the rank scores from the nodes (or edges) once the ranks
100      * have been computed.
101      * @param removeRankScoresOnFinalize <code>true</code> if the rank scores are to be removed, <code>false</code> otherwise
102      */
103     public void setRemoveRankScoresOnFinalize(boolean removeRankScoresOnFinalize) {
10415        this.mRemoveRankScoresOnFinalize = removeRankScoresOnFinalize;
10515    }
106  
10720162    protected void onFinalize(Element e) {}
108  
109     protected void finalizeIterations() {
11024        ArrayList sortedRankings = new ArrayList();
111  
11224        int id = 1;
11324        if (mRankNodes)
114         {
11521            for (Iterator it = getVertices().iterator(); it.hasNext();) {
11620110                Vertex currentVertex = (Vertex) it.next();
11720110                NodeRanking ranking = new NodeRanking(id,getRankScore(currentVertex),currentVertex);
11820110                sortedRankings.add(ranking);
11920110                if (mRemoveRankScoresOnFinalize) {
12020031                    currentVertex.removeUserDatum(getRankScoreKey());
121                 }
12220110                id++;
12320110                onFinalize(currentVertex);
124             }
125         }
12624        if (mRankEdges)
127         {
1287            for (Iterator it = mGraph.getEdges().iterator(); it.hasNext();) {
12960                Edge currentEdge = (Edge) it.next();
13060                EdgeRanking ranking = new EdgeRanking(id,getRankScore(currentEdge),currentEdge);
13160                sortedRankings.add(ranking);
13260                if (mRemoveRankScoresOnFinalize) {
13333                    currentEdge.removeUserDatum(getRankScoreKey());
134                 }
13560                id++;
13660                onFinalize(currentEdge);
137             }
138         }
139  
14024        mRankings = sortedRankings;
14124        Collections.sort(mRankings);
14224    }
143  
144     /**
145      * Retrieves the list of ranking instances in descending sorted order by rank score
146      * If the algorithm is ranking edges, the instances will be of type <code>EdgeRanking</code>, otherwise
147      * if the algorithm is ranking nodes the instances will be of type <code>NodeRanking</code>
148      * @return the list of rankings
149      */
150     public List getRankings() {
15128        return mRankings;
152     }
153  
154     /**
155      * Return a list of the top k rank scores.
156      * @param topKRankings the value of k to use
157      * @return list of rank scores
158      */
159     public DoubleArrayList getRankScores(int topKRankings) {
1600        DoubleArrayList scores = new DoubleArrayList();
1610        int count=1;
1620        for (Iterator rIt=getRankings().iterator(); rIt.hasNext();) {
1630            if (count > topKRankings) {
1640                return scores;
165             }
1660            NodeRanking currentRanking = (NodeRanking) rIt.next();
1670            scores.add(currentRanking.rankScore);
1680            count++;
169         }
170  
1710        return scores;
172     }
173  
174     /**
175      * The user datum key used to store the rank score.
176      * @return the key
177      */
178     abstract public String getRankScoreKey();
179  
180     /**
181      * Given an edge or node, returns the corresponding rank score. This is a default
182      * implementation of getRankScore which assumes the decorations are of type MutableDouble.
183      * This method only returns legal values if <code>setRemoveRankScoresOnFinalize(false)</code> was called
184      * prior to <code>evaluate()</code>.
185      * @return the rank score value
186      */
187     public double getRankScore(Element e) {
18861436        MutableDouble rankScore = (MutableDouble) e.getUserDatum(getRankScoreKey());
18961436        if (rankScore != null) {
19061436            return rankScore.doubleValue();
191         } else {
1920            throw new FatalException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
193         }
194  
195     }
196  
197     protected void setRankScore(Element e, double rankValue) {
19840683        MutableDouble value = (MutableDouble) e.getUserDatum(getRankScoreKey());
199  
20040683        if (value == null) {
20120051            e.setUserDatum(getRankScoreKey(),new MutableDouble(rankValue),UserData.SHARED);
202         } else {
20320632            value.setDoubleValue(rankValue);
204         }
205  
20640683    }
207  
208     protected double getEdgeWeight(Edge e) {
2091075       String edgeWeightKey = getEdgeWeightKeyName();
2101075       return ((Number) e.getUserDatum(edgeWeightKey)).doubleValue();
211     }
212  
213     /**
214      * the user datum key used to store the edge weight, if any
215      * @return the key
216      */
217     public String getEdgeWeightKeyName() {
2181151        if (mUserDefinedEdgeWeightKey == null) {
219586           return DEFAULT_EDGE_WEIGHT_KEY;
220         } else {
221565            return mUserDefinedEdgeWeightKey;
222         }
223     }
224  
225     protected void setEdgeWeight(Edge e, double weight) {
22655        String edgeWeightKey = getEdgeWeightKeyName();
227  
228 // MutableDouble value = (MutableDouble) e.getUserDatum(edgeWeightKey);
229 // if (value == null) {
230 // e.setUserDatum(edgeWeightKey,new MutableDouble(weight),UserData.SHARED);
231 // } else {
232 // value.setDoubleValue(weight);
233 // }
23455        e.setUserDatum(edgeWeightKey,new Double(weight),UserData.SHARED);
23555    }
236  
237     protected void assignDefaultEdgeTransitionWeights() {
238  
2395        for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {
24026            Vertex currentVertex = (Vertex) vIt.next();
241  
242 // Set outgoingEdges = null;
243 // if (getGraph().isDirected()) {
244 // outgoingEdges = currentVertex.getOutEdges();
245 // } else {
246 // outgoingEdges = currentVertex.getIncidentEdges();
247 // }
248             // getOutEdges() returns the right thing regardless, so just use this.
24926            Set outgoingEdges = currentVertex.getOutEdges();
250  
25126            double numOutEdges = outgoingEdges.size();
25226            for (Iterator edgeIt = outgoingEdges.iterator(); edgeIt.hasNext();) {
25334                Edge currentEdge = (Edge) edgeIt.next();
25434                setEdgeWeight(currentEdge,1.0/numOutEdges);
255             }
256         }
257  
2585    }
259  
260  
261     protected void normalizeEdgeTransitionWeights() {
262  
2634        for (Iterator vIt = getVertices().iterator(); vIt.hasNext();) {
26415            Vertex currentVertex = (Vertex) vIt.next();
265  
266 // Set outgoingEdges = null;
267 // if (getGraph().isDirected()) {
268 // outgoingEdges = currentVertex.getOutEdges();
269 // } else {
270 // outgoingEdges = currentVertex.getIncidentEdges();
271 // }
27215            Set outgoingEdges = currentVertex.getOutEdges();
273  
27415            double totalEdgeWeight = 0;
27515            for (Iterator edgeIt = outgoingEdges.iterator(); edgeIt.hasNext();) {
27621                Edge currentEdge = (Edge) edgeIt.next();
27721                totalEdgeWeight += getEdgeWeight(currentEdge);
278             }
279  
280             //double numOutEdges = outgoingEdges.size();
28115            for (Iterator edgeIt = outgoingEdges.iterator(); edgeIt.hasNext();) {
28221                Edge currentEdge = (Edge) edgeIt.next();
28321                setEdgeWeight(currentEdge,getEdgeWeight(currentEdge)/totalEdgeWeight);
284             }
285         }
2864    }
287  
288     protected void normalizeRankings() {
2897        if (!mNormalizeRankings) {
2900            return;
291         }
2927        double totalWeight = 0;
2937        Vertex currentVertex = null;
294  
2957        for (Iterator it = getVertices().iterator(); it.hasNext();) {
29620023            currentVertex = (Vertex) it.next();
29720023            totalWeight += getRankScore(currentVertex);
298         }
299  
3007        for (Iterator it = getVertices().iterator(); it.hasNext();) {
30120023            currentVertex = (Vertex) it.next();
30220023            setRankScore(currentVertex,getRankScore(currentVertex)/totalWeight);
303         }
3047    }
305  
306     /**
307      * Print the rankings to standard out in descending order of rank score
308      * @param verbose if <code>true</code>, include information about the actual rank order as well as
309      * the original position of the vertex before it was ranked
310      * @param printScore if <code>true</code>, include the actual value of the rank score
311      */
312     public void printRankings(boolean verbose,boolean printScore) {
3130            double total = 0;
3140            Format formatter = new Format("%7.6f");
3150            int rank = 1;
3160            boolean hasLabels = StringLabeller.hasStringLabeller(getGraph());
3170            StringLabeller labeller = StringLabeller.getLabeller(getGraph());
3180            for (Iterator it = getRankings().iterator(); it.hasNext();) {
3190                Ranking currentRanking = (Ranking) it.next();
3200                double rankScore = currentRanking.rankScore;
3210                if (verbose) {
3220                    System.out.print("Rank " + rank + ": ");
3230                    if (printScore) {
3240                        System.out.print(formatter.format(rankScore));
325                     }
3260                    System.out.print("\tVertex Id: " + currentRanking.originalPos);
3270                    if (hasLabels && currentRanking instanceof NodeRanking) {
3280                        Vertex v = ((NodeRanking) currentRanking).vertex;
3290                        System.out.print(" (" + labeller.getLabel(v) + ")");
330                     }
3310                    System.out.println();
332                 } else {
3330                    System.out.print(rank + "\t");
3340                     if (printScore) {
3350                        System.out.print(formatter.format(rankScore));
336                     }
3370                    System.out.println("\t" + currentRanking.originalPos);
338  
339                 }
3400                total += rankScore;
3410                rank++;
342             }
343  
3440            if (verbose) {
3450                System.out.println("Total: " + formatter.format(total));
346             }
3470    }
348  
349     /**
350      * Allows the user to specify whether or not s/he wants the rankings to be normalized.
351      * In some cases, this will have no effect since the algorithm doesn't allow normalization
352      * as an option
353      * @param normalizeRankings
354      */
355     public void setNormalizeRankings(boolean normalizeRankings) {
3560        mNormalizeRankings = normalizeRankings;
3570    }
358  
359     /**
360      * Allows the user to provide his own set of data instances as edge weights by giving the ranker
361      * the <code>UserDatum</code> key where those instances can be found.
362      * @param keyName the name of the <code>UserDatum</code> key where the data instance representing an edge weight
363      * can be found
364      */
365     public void setUserDefinedEdgeWeightKey(String keyName) {
3663        mUserDefinedEdgeWeightKey = keyName;
3673    }
368 }

jcoverage | summary | package | file

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.