# Coverage details for edu.uci.ics.jung.statistics.GraphStatistics

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 &gt; 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>&lt;u,v&gt;</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. 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.