• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1'''
2altgraph.GraphStat - Functions providing various graph statistics
3=================================================================
4'''
5import sys
6
7def degree_dist(graph, limits=(0,0), bin_num=10, mode='out'):
8    '''
9    Computes the degree distribution for a graph.
10
11    Returns a list of tuples where the first element of the tuple is the center of the bin
12    representing a range of degrees and the second element of the tuple are the number of nodes
13    with the degree falling in the range.
14
15    Example::
16
17        ....
18    '''
19
20    deg = []
21    if mode == 'inc':
22        get_deg = graph.inc_degree
23    else:
24        get_deg = graph.out_degree
25
26    for node in graph:
27        deg.append( get_deg(node) )
28
29    if not deg:
30        return []
31
32    results = _binning(values=deg, limits=limits, bin_num=bin_num)
33
34    return results
35
36_EPS = 1.0/(2.0**32)
37def _binning(values, limits=(0,0), bin_num=10):
38    '''
39    Bins data that falls between certain limits, if the limits are (0, 0) the
40    minimum and maximum values are used.
41
42    Returns a list of tuples where the first element of the tuple is the center of the bin
43    and the second element of the tuple are the counts.
44    '''
45    if limits == (0, 0):
46        min_val, max_val = min(values) - _EPS, max(values) + _EPS
47    else:
48        min_val, max_val = limits
49
50    # get bin size
51    bin_size = (max_val - min_val)/float(bin_num)
52    bins = [0] * (bin_num)
53
54    # will ignore these outliers for now
55    out_points = 0
56    for value in values:
57        try:
58            if (value - min_val) < 0:
59                out_points += 1
60            else:
61                index = int((value - min_val)/float(bin_size))
62                bins[index] += 1
63        except IndexError:
64            out_points += 1
65
66    # make it ready for an x,y plot
67    result = []
68    center = (bin_size/2) + min_val
69    for i, y in enumerate(bins):
70        x = center + bin_size * i
71        result.append( (x,y) )
72
73    return result
74