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.statistics; | |
11 | import java.util.ArrayList; | |
12 | import java.util.HashMap; | |
13 | import java.util.Iterator; | |
14 | import java.util.Map; | |
15 | import java.util.Set; | |
16 | ||
17 | import cern.colt.list.DoubleArrayList; | |
18 | import edu.uci.ics.jung.algorithms.shortestpath.Distance; | |
19 | import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath; | |
20 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
21 | import edu.uci.ics.jung.graph.ArchetypeVertex; | |
22 | import edu.uci.ics.jung.graph.Graph; | |
23 | ||
24 | /** | |
25 | * A set of statistical measures for structural properties of a graph. | |
26 | * @author Scott White | |
27 | * @author Joshua O'Madadhain | |
28 | */ | |
29 | 0 | public class GraphStatistics |
30 | { | |
31 | ||
32 | /** | |
33 | * Returns a <code>Map</code> of vertices to their clustering coefficients. | |
34 | * The clustering coefficient cc(v) of a vertex v is defined as follows: | |
35 | * <ul> | |
36 | * <li/><code>degree(v) == 0</code>: 0 | |
37 | * <li/><code>degree(v) == 1</code>: 1 | |
38 | * <li/><code>degree(v) == n, n > 1</code>: given S, the set of neighbors | |
39 | * of <code>v</code>: cc(v) = (the sum over all w in S of the number of | |
40 | * other elements of w that are neighbors of w) / ((|S| * (|S| - 1) / 2). | |
41 | * Less formally, the fraction of <code>v</code>'s neighbors that are also | |
42 | * neighbors of each other. | |
43 | * <p><b>Note</b>: This algorithm treats its argument as an undirected graph; | |
44 | * edge direction is ignored. | |
45 | * @param graph | |
46 | */ | |
47 | public static Map clusteringCoefficients(ArchetypeGraph graph) | |
48 | { | |
49 | 1 | Map coefficients = new HashMap(); |
50 | ||
51 | 1 | for (Iterator v_iter = graph.getVertices().iterator(); v_iter.hasNext(); ) |
52 | { | |
53 | 6 | ArchetypeVertex v = (ArchetypeVertex)v_iter.next(); |
54 | 6 | int n = v.numNeighbors(); |
55 | 6 | if (n == 0) |
56 | 0 | coefficients.put(v, new Double(0)); |
57 | 6 | else if (n == 1) |
58 | 0 | coefficients.put(v, new Double(1)); |
59 | else | |
60 | { | |
61 | // how many of v's neighbors are connected to each other? | |
62 | 6 | ArrayList neighbors = new ArrayList(v.getNeighbors()); |
63 | 6 | double edge_count = 0; |
64 | 22 | for (int i = 0; i < neighbors.size(); i++) |
65 | { | |
66 | 16 | ArchetypeVertex w = (ArchetypeVertex)neighbors.get(i); |
67 | 31 | for (int j = i+1; j < neighbors.size(); j++ ) |
68 | { | |
69 | 15 | ArchetypeVertex x = (ArchetypeVertex)neighbors.get(j); |
70 | 15 | edge_count += w.isNeighborOf(x) ? 1 : 0; |
71 | } | |
72 | } | |
73 | 6 | double possible_edges = (n * (n - 1))/2.0; |
74 | 6 | coefficients.put(v, new Double(edge_count / possible_edges)); |
75 | } | |
76 | } | |
77 | ||
78 | 1 | return coefficients; |
79 | } | |
80 | ||
81 | ||
82 | /** | |
83 | * For each vertex <code>v</code> in <code>graph</code>, | |
84 | * calculates the average shortest path length from <code>v</code> | |
85 | * to all other vertices in <code>graph</code> using the metric | |
86 | * specified by <code>d</code>, and returns the results in a | |
87 | * <code>Map</code> from vertices to <code>Double</code> values. | |
88 | * If there exists an ordered pair <code><u,v></code> | |
89 | * for which <code>d.getDistance(u,v)</code> returns <code>null</code>, | |
90 | * then the average distance value for <code>u</code> will be stored | |
91 | * as <code>Double.POSITIVE_INFINITY</code>). | |
92 | * | |
93 | * <p>To calculate the average distances, ignoring edge weights if any: | |
94 | * <pre> | |
95 | * Map distances = GraphStatistics.averageDistances(g, new UnweightedShortestPath(g)); | |
96 | * </pre> | |
97 | * To calculate the average distances respecting edge weights: | |
98 | * <pre> | |
99 | * DijkstraShortestPath dsp = new DijkstraShortestPath(g, nev); | |
100 | * Map distances = GraphStatistics.averageDistances(g, dsp); | |
101 | * </pre> | |
102 | * where <code>nev</code> is an instance of <code>NumberEdgeValue</code> that | |
103 | * is used to fetch the weight for each edge. | |
104 | * | |
105 | * @see edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath | |
106 | * @see edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance | |
107 | */ | |
108 | public static Map averageDistances(ArchetypeGraph graph, Distance d) | |
109 | { | |
110 | 2 | Map avg_dist = new HashMap(); |
111 | 2 | Set vertices = graph.getVertices(); |
112 | 2 | int n = graph.numVertices(); |
113 | 2 | for (Iterator outer = vertices.iterator(); outer.hasNext(); ) |
114 | { | |
115 | 12 | ArchetypeVertex v = (ArchetypeVertex)outer.next(); |
116 | 12 | double avgPathLength = 0; |
117 | 12 | for (Iterator inner = vertices.iterator(); inner.hasNext(); ) |
118 | { | |
119 | 48 | ArchetypeVertex w = (ArchetypeVertex)inner.next(); |
120 | 48 | if (v != w) // don't include self-distances |
121 | { | |
122 | 40 | Number dist = d.getDistance(v, w); |
123 | 40 | if (dist == null) |
124 | { | |
125 | 5 | avgPathLength = Double.POSITIVE_INFINITY; |
126 | 5 | break; |
127 | } | |
128 | 35 | avgPathLength += dist.doubleValue(); |
129 | } | |
130 | } | |
131 | 12 | avgPathLength /= (n - 1); |
132 | 12 | avg_dist.put(v, new Double(avgPathLength)); |
133 | } | |
134 | 2 | return avg_dist; |
135 | } | |
136 | ||
137 | /** | |
138 | * For each vertex <code>v</code> in <code>g</code>, | |
139 | * calculates the average shortest path length from <code>v</code> | |
140 | * to all other vertices in <code>g</code>, ignoring edge weights. | |
141 | * @see #diameter(ArchetypeGraph, Distance) | |
142 | */ | |
143 | public static Map averageDistances(ArchetypeGraph g) | |
144 | { | |
145 | 0 | return averageDistances(g, new UnweightedShortestPath((Graph)g)); |
146 | } | |
147 | ||
148 | /** | |
149 | * Returns the diameter of <code>g</code> using the metric | |
150 | * specified by <code>d</code>. The diameter is defined to be | |
151 | * the maximum, over all pairs of vertices <code>u,v</code>, | |
152 | * of the length of the shortest path from <code>u</code> to | |
153 | * <code>v</code>. If the graph is disconnected (that is, not | |
154 | * all pairs of vertices are reachable from one another), the | |
155 | * value returned will depend on <code>use_max</code>: | |
156 | * if <code>use_max == true</code>, the value returned | |
157 | * will be the the maximum shortest path length over all pairs of <b>connected</b> | |
158 | * vertices; otherwise it will be <code>Double.POSITIVE_INFINITY</code>. | |
159 | */ | |
160 | public static double diameter(ArchetypeGraph g, Distance d, boolean use_max) | |
161 | { | |
162 | 1 | double diameter = 0; |
163 | 1 | Set vertices = g.getVertices(); |
164 | 1 | for (Iterator outer = vertices.iterator(); outer.hasNext(); ) |
165 | { | |
166 | 6 | ArchetypeVertex v = (ArchetypeVertex)outer.next(); |
167 | 6 | for (Iterator inner = vertices.iterator(); inner.hasNext(); ) |
168 | { | |
169 | 36 | ArchetypeVertex w = (ArchetypeVertex)inner.next(); |
170 | 36 | if (v != w) // don't include self-distances |
171 | { | |
172 | 30 | Number dist = d.getDistance(v, w); |
173 | 30 | if (dist == null) |
174 | { | |
175 | 0 | if (!use_max) |
176 | 0 | return Double.POSITIVE_INFINITY; |
177 | } | |
178 | else | |
179 | 30 | diameter = Math.max(diameter, dist.doubleValue()); |
180 | } | |
181 | } | |
182 | } | |
183 | 1 | return diameter; |
184 | } | |
185 | ||
186 | /** | |
187 | * Returns the diameter of <code>g</code> using the metric | |
188 | * specified by <code>d</code>. The diameter is defined to be | |
189 | * the maximum, over all pairs of vertices <code>u,v</code>, | |
190 | * of the length of the shortest path from <code>u</code> to | |
191 | * <code>v</code>, or <code>Double.POSITIVE_INFINITY</code> | |
192 | * if any of these distances do not exist. | |
193 | * @see #diameter(ArchetypeGraph, Distance, boolean) | |
194 | */ | |
195 | public static double diameter(ArchetypeGraph g, Distance d) | |
196 | { | |
197 | 1 | return diameter(g, d, false); |
198 | } | |
199 | ||
200 | /** | |
201 | * Returns the diameter of <code>g</code>, ignoring edge weights. | |
202 | * @see #diameter(ArchetypeGraph, Distance, boolean) | |
203 | */ | |
204 | public static double diameter(ArchetypeGraph g) | |
205 | { | |
206 | 1 | return diameter(g, new UnweightedShortestPath((Graph)g)); |
207 | } | |
208 | ||
209 | /** | |
210 | * Creates a histogram from a sequence of doubles | |
211 | * @param values the sequence of doubles | |
212 | * @param min the minimum value to bin off of | |
213 | * @param numBins the number of bins | |
214 | * @param binWidth the width of the bin | |
215 | * @return a histogram | |
216 | */ | |
217 | public static Histogram createHistogram( | |
218 | DoubleArrayList values, | |
219 | double min, | |
220 | int numBins, | |
221 | double binWidth) { | |
222 | 2 | Histogram histogram = new Histogram(numBins, min, binWidth); |
223 | 1002 | for (int idx = 0; idx < values.size(); idx++) { |
224 | 1000 | histogram.fill(values.get(idx)); |
225 | } | |
226 | 2 | return histogram; |
227 | } | |
228 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |