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

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.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  */
290public 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     {
491        Map coefficients = new HashMap();
50         
511        for (Iterator v_iter = graph.getVertices().iterator(); v_iter.hasNext(); )
52         {
536            ArchetypeVertex v = (ArchetypeVertex)v_iter.next();
546            int n = v.numNeighbors();
556            if (n == 0)
560                coefficients.put(v, new Double(0));
576            else if (n == 1)
580                coefficients.put(v, new Double(1));
59             else
60             {
61                 // how many of v's neighbors are connected to each other?
626                ArrayList neighbors = new ArrayList(v.getNeighbors());
636                double edge_count = 0;
6422                for (int i = 0; i < neighbors.size(); i++)
65                 {
6616                    ArchetypeVertex w = (ArchetypeVertex)neighbors.get(i);
6731                    for (int j = i+1; j < neighbors.size(); j++ )
68                     {
6915                        ArchetypeVertex x = (ArchetypeVertex)neighbors.get(j);
7015                        edge_count += w.isNeighborOf(x) ? 1 : 0;
71                     }
72                 }
736                double possible_edges = (n * (n - 1))/2.0;
746                coefficients.put(v, new Double(edge_count / possible_edges));
75             }
76         }
77         
781        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     {
1102        Map avg_dist = new HashMap();
1112        Set vertices = graph.getVertices();
1122        int n = graph.numVertices();
1132        for (Iterator outer = vertices.iterator(); outer.hasNext(); )
114         {
11512            ArchetypeVertex v = (ArchetypeVertex)outer.next();
11612            double avgPathLength = 0;
11712            for (Iterator inner = vertices.iterator(); inner.hasNext(); )
118             {
11948                ArchetypeVertex w = (ArchetypeVertex)inner.next();
12048                if (v != w) // don't include self-distances
121                 {
12240                    Number dist = d.getDistance(v, w);
12340                    if (dist == null)
124                     {
1255                        avgPathLength = Double.POSITIVE_INFINITY;
1265                        break;
127                     }
12835                    avgPathLength += dist.doubleValue();
129                 }
130             }
13112            avgPathLength /= (n - 1);
13212            avg_dist.put(v, new Double(avgPathLength));
133         }
1342        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     {
1450        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     {
1621        double diameter = 0;
1631        Set vertices = g.getVertices();
1641        for (Iterator outer = vertices.iterator(); outer.hasNext(); )
165         {
1666            ArchetypeVertex v = (ArchetypeVertex)outer.next();
1676            for (Iterator inner = vertices.iterator(); inner.hasNext(); )
168             {
16936                ArchetypeVertex w = (ArchetypeVertex)inner.next();
17036                if (v != w) // don't include self-distances
171                 {
17230                    Number dist = d.getDistance(v, w);
17330                    if (dist == null)
174                     {
1750                        if (!use_max)
1760                            return Double.POSITIVE_INFINITY;
177                     }
178                     else
17930                        diameter = Math.max(diameter, dist.doubleValue());
180                 }
181             }
182         }
1831        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     {
1971        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     {
2061        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) {
2222        Histogram histogram = new Histogram(numBins, min, binWidth);
2231002        for (int idx = 0; idx < values.size(); idx++) {
2241000            histogram.fill(values.get(idx));
225         }
2262        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.