| 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. |