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