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.ArrayList; | |
13 | import java.util.HashSet; | |
14 | import java.util.Iterator; | |
15 | import java.util.List; | |
16 | import java.util.Set; | |
17 | ||
18 | import edu.uci.ics.jung.graph.DirectedEdge; | |
19 | import edu.uci.ics.jung.graph.DirectedGraph; | |
20 | import edu.uci.ics.jung.graph.Edge; | |
21 | import edu.uci.ics.jung.graph.Element; | |
22 | import edu.uci.ics.jung.graph.Vertex; | |
23 | import edu.uci.ics.jung.graph.impl.SparseVertex; | |
24 | import edu.uci.ics.jung.utils.GraphUtils; | |
25 | import edu.uci.ics.jung.utils.MutableDouble; | |
26 | import edu.uci.ics.jung.utils.UserData; | |
27 | ||
28 | ||
29 | /** | |
30 | * This algorithm measures the importance of nodes based upon both the number and length of disjoint paths that lead | |
31 | * to a given node from each of the nodes in the root set. Specifically the formula for measuring the importance of a | |
32 | * node is given by: I(t|R) = sum_i=1_|P(r,t)|_{alpha^|p_i|} where alpha is the path decay coefficient, p_i is path i | |
33 | * and P(r,t) is a set of maximum-sized node-disjoint paths from r to t. | |
34 | * <p> | |
35 | * This algorithm uses heuristic breadth-first search to try and find the maximum-sized set of node-disjoint paths | |
36 | * between two nodes. As such, it is not guaranteed to give exact answers. | |
37 | * <p> | |
38 | * A simple example of usage is: | |
39 | * <pre> | |
40 | * WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet); | |
41 | * ranker.evaluate(); | |
42 | * ranker.printRankings(); | |
43 | * </pre> | |
44 | * | |
45 | * @author Scott White | |
46 | * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003" | |
47 | */ | |
48 | public class WeightedNIPaths extends AbstractRanker { | |
49 | public final static String WEIGHTED_NIPATHS_KEY = "jung.algorithms.importance.WEIGHTED_NIPATHS_KEY"; | |
50 | private double mAlpha; | |
51 | private int mMaxDepth; | |
52 | private Set mPriors; | |
53 | ||
54 | /** | |
55 | * Constructs and initializes the algorithm. | |
56 | * @param graph the graph whose nodes are being measured for their importance | |
57 | * @param alpha the path decay coefficient (>= 1); 2 is recommended | |
58 | * @param maxDepth the maximal depth to search out from the root set | |
59 | * @param priors the root set (starting vertices) | |
60 | */ | |
61 | 1 | public WeightedNIPaths(DirectedGraph graph, double alpha, int maxDepth, Set priors) { |
62 | 1 | super.initialize(graph, true,false); |
63 | 1 | mAlpha = alpha; |
64 | 1 | mMaxDepth = maxDepth; |
65 | 1 | mPriors = priors; |
66 | 1 | for (Iterator vIt = graph.getVertices().iterator(); vIt.hasNext();) { |
67 | 5 | Vertex currentVertex = (Vertex) vIt.next(); |
68 | 5 | currentVertex.setUserDatum(WEIGHTED_NIPATHS_KEY, new MutableDouble(0), UserData.SHARED); |
69 | } | |
70 | 1 | } |
71 | ||
72 | /** | |
73 | * Given a node, returns the corresponding rank score. This implementation of <code>getRankScore</code> assumes | |
74 | * the decoration representing the rank score is of type <code>MutableDouble</code>. | |
75 | * @return the rank score for this node | |
76 | */ | |
77 | public String getRankScoreKey() { | |
78 | 51 | return WEIGHTED_NIPATHS_KEY; |
79 | } | |
80 | ||
81 | protected void incrementRankScore(Element v, double rankValue) { | |
82 | 13 | setRankScore(v, getRankScore(v) + rankValue); |
83 | 13 | } |
84 | ||
85 | protected void computeWeightedPathsFromSource(Vertex root, int depth) { | |
86 | ||
87 | 1 | int pathIdx = 1; |
88 | 1 | for (Iterator rootEdgeIt = root.getOutEdges().iterator(); rootEdgeIt.hasNext();) { |
89 | 3 | DirectedEdge currentEdge = (DirectedEdge) rootEdgeIt.next(); |
90 | 3 | Integer pathIdxValue = new Integer(pathIdx); |
91 | 3 | currentEdge.setUserDatum(PATH_INDEX_KEY, pathIdxValue, UserData.REMOVE); |
92 | 3 | currentEdge.setUserDatum(ROOT_KEY, root, UserData.REMOVE); |
93 | 3 | newVertexEncountered(pathIdxValue, currentEdge.getDest(), root); |
94 | 3 | pathIdx++; |
95 | } | |
96 | ||
97 | 1 | List edges = new ArrayList(); |
98 | ||
99 | 1 | Vertex virtualNode = getGraph().addVertex(new SparseVertex()); |
100 | 1 | Edge virtualSinkEdge = GraphUtils.addEdge(getGraph(), virtualNode, root); |
101 | 1 | edges.add(virtualSinkEdge); |
102 | ||
103 | 1 | int currentDepth = 0; |
104 | 4 | while (currentDepth <= depth) { |
105 | ||
106 | 4 | double currentWeight = Math.pow(mAlpha, -1.0 * currentDepth); |
107 | ||
108 | 4 | for (Iterator it = edges.iterator(); it.hasNext();) { |
109 | 13 | DirectedEdge currentEdge = (DirectedEdge) it.next(); |
110 | 13 | incrementRankScore(currentEdge.getDest(), currentWeight); |
111 | } | |
112 | ||
113 | 4 | if ((currentDepth == depth) || (edges.size() == 0)) break; |
114 | ||
115 | 3 | List newEdges = new ArrayList(); |
116 | ||
117 | 3 | for (Iterator sourceEdgeIt = edges.iterator(); sourceEdgeIt.hasNext();) { |
118 | 11 | DirectedEdge currentSourceEdge = (DirectedEdge) sourceEdgeIt.next(); |
119 | 11 | Integer sourcePathIndex = (Integer) currentSourceEdge.getUserDatum(PATH_INDEX_KEY); |
120 | ||
121 | 11 | for (Iterator edgeIt = currentSourceEdge.getDest().getOutEdges().iterator(); edgeIt.hasNext();) { |
122 | 27 | DirectedEdge currentDestEdge = (DirectedEdge) edgeIt.next(); |
123 | 27 | Vertex destEdgeRoot = (Vertex) currentDestEdge.getUserDatum(ROOT_KEY); |
124 | 27 | Vertex destEdgeDest = currentDestEdge.getDest(); |
125 | ||
126 | 27 | if (currentSourceEdge == virtualSinkEdge) { |
127 | 3 | newEdges.add(currentDestEdge); |
128 | 3 | continue; |
129 | } | |
130 | 24 | if (destEdgeRoot == root) { |
131 | 11 | continue; |
132 | } | |
133 | 13 | if (destEdgeDest == currentSourceEdge.getSource()) { |
134 | 3 | continue; |
135 | } | |
136 | ||
137 | 10 | Set pathsSeen = (Set) destEdgeDest.getUserDatum(PATHS_SEEN_KEY); |
138 | ||
139 | /* | |
140 | Set pathsSeen = new HashSet(); | |
141 | pathsSeen.add(sourcePathIndex); | |
142 | dest.setUserDatum(PATHS_SEEN_KEY, pathsSeen, UserData.REMOVE); | |
143 | dest.setUserDatum(ROOT_KEY, root, UserData.REMOVE); | |
144 | */ | |
145 | ||
146 | 10 | if (pathsSeen == null) { |
147 | 2 | newVertexEncountered(sourcePathIndex, destEdgeDest, root); |
148 | 8 | } else if (destEdgeDest.getUserDatum(ROOT_KEY) != root) { |
149 | 0 | destEdgeDest.setUserDatum(ROOT_KEY, root, UserData.REMOVE); |
150 | 0 | pathsSeen.clear(); |
151 | 0 | pathsSeen.add(sourcePathIndex); |
152 | 8 | } else if (!pathsSeen.contains(sourcePathIndex)) { |
153 | 7 | pathsSeen.add(sourcePathIndex); |
154 | } else { | |
155 | continue; | |
156 | } | |
157 | ||
158 | 9 | currentDestEdge.setUserDatum(PATH_INDEX_KEY, sourcePathIndex, UserData.REMOVE); |
159 | 9 | currentDestEdge.setUserDatum(ROOT_KEY, root, UserData.REMOVE); |
160 | 9 | newEdges.add(currentDestEdge); |
161 | } | |
162 | } | |
163 | ||
164 | 3 | edges = newEdges; |
165 | 3 | currentDepth++; |
166 | } | |
167 | ||
168 | 1 | getGraph().removeVertex(virtualNode); |
169 | 1 | } |
170 | ||
171 | private void newVertexEncountered(Integer sourcePathIndex, Vertex dest, Vertex root) { | |
172 | 5 | Set pathsSeen = new HashSet(); |
173 | 5 | pathsSeen.add(sourcePathIndex); |
174 | 5 | dest.setUserDatum(PATHS_SEEN_KEY, pathsSeen, UserData.REMOVE); |
175 | 5 | dest.setUserDatum(ROOT_KEY, root, UserData.REMOVE); |
176 | 5 | } |
177 | ||
178 | protected double evaluateIteration() { | |
179 | 1 | for (Iterator it = mPriors.iterator(); it.hasNext();) { |
180 | 1 | computeWeightedPathsFromSource((Vertex) it.next(), mMaxDepth); |
181 | } | |
182 | ||
183 | 1 | normalizeRankings(); |
184 | 1 | return 0; |
185 | } | |
186 | ||
187 | protected void onFinalize(Element udc) { | |
188 | 5 | udc.removeUserDatum(PATH_INDEX_KEY); |
189 | 5 | udc.removeUserDatum(ROOT_KEY); |
190 | 5 | udc.removeUserDatum(PATHS_SEEN_KEY); |
191 | 5 | } |
192 | ||
193 | private static final String PATH_INDEX_KEY = "WeightedNIPathsII.PathIndexKey"; | |
194 | private static final String ROOT_KEY = "WeightedNIPathsII.RootKey"; | |
195 | private static final String PATHS_SEEN_KEY = "WeightedNIPathsII.PathsSeenKey"; | |
196 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |