In [23]:
import os
import csv
import platform
import pandas as pd
import networkx as nx
from graph_partitioning import GraphPartitioning, utils

run_metrics = True

cols = ["WASTE", "CUT RATIO", "EDGES CUT", "TOTAL COMM VOLUME", "Qds", "CONDUCTANCE", "MAXPERM", "RBSE", "NMI", "FSCORE", "FSCORE RELABEL IMPROVEMENT", "LONELINESS"]
#cols = ["WASTE", "CUT RATIO", "EDGES CUT", "TOTAL COMM VOLUME", "Q", "Qds", "CONDUCTANCE", "LONELINESS", "NETWORK PERMANENCE", "NORM. MUTUAL INFO", "EDGE CUT WEIGHT", "FSCORE", "FSCORE RELABEL IMPROVEMENT"]
#cols = ["WASTE", "CUT RATIO", "EDGES CUT", "TOTAL COMM VOLUME", "MODULARITY", "LONELINESS", "NETWORK PERMANENCE", "NORM. MUTUAL INFO", "EDGE CUT WEIGHT", "FSCORE", "FSCORE RELABEL IMPROVEMENT"]

pwd = %pwd

config = {

    "DATA_FILENAME": os.path.join(pwd, "data", "predition_model_tests", "network", "network_2.txt"),
    "OUTPUT_DIRECTORY": os.path.join(pwd, "output"),

    # Set which algorithm is run for the PREDICTION MODEL.
    # Either: 'FENNEL' or 'SCOTCH'
    "PREDICTION_MODEL_ALGORITHM": "FENNEL",

    # Alternativly, read input file for prediction model.
    # Set to empty to generate prediction model using algorithm value above.
    "PREDICTION_MODEL": "",

    
    "PARTITIONER_ALGORITHM": "FENNEL",

    # File containing simulated arrivals. This is used in simulating nodes
    # arriving at the shelter. Nodes represented by line number; value of
    # 1 represents a node as arrived; value of 0 represents the node as not
    # arrived or needing a shelter.
    "SIMULATED_ARRIVAL_FILE": os.path.join(pwd,
                                           "data",
                                           "predition_model_tests",
                                           "dataset_1_shift_rotate",
                                           "simulated_arrival_list",
                                           "percentage_of_prediction_correct_100",
                                           "arrival_100_2.txt"
                                          ),

    # File containing the prediction of a node arriving. This is different to the
    # simulated arrivals, the values in this file are known before the disaster.
    "PREDICTION_LIST_FILE": os.path.join(pwd,
                                         "data",
                                         "predition_model_tests",
                                         "dataset_1_shift_rotate",
                                         "prediction_list",
                                         "prediction_2.txt"
                                        ),

    # File containing the geographic location of each node, in "x,y" format.
    "POPULATION_LOCATION_FILE": os.path.join(pwd,
                                             "data",
                                             "predition_model_tests",
                                             "coordinates",
                                             "coordinates_2.txt"
                                            ),

    # Number of shelters
    "num_partitions": 4,

    # The number of iterations when making prediction model
    "num_iterations": 1,

    # Percentage of prediction model to use before discarding
    # When set to 0, prediction model is discarded, useful for one-shot
    "prediction_model_cut_off": .0,

    # Alpha value used in one-shot (when restream_batches set to 1)
    "one_shot_alpha": 0.5,
    
    "use_one_shot_alpha": False,
    
    # Number of arrivals to batch before recalculating alpha and restreaming.
    "restream_batches": 50,

    # When the batch size is reached: if set to True, each node is assigned
    # individually as first in first out. If set to False, the entire batch
    # is processed and empty before working on the next batch.
    "sliding_window": False,

    # Create virtual nodes based on prediction model
    "use_virtual_nodes": False,

    # Virtual nodes: edge weight
    "virtual_edge_weight": 1.0,
    
    # Loneliness score parameter. Used when scoring a partition by how many
    # lonely nodes exist.
    "loneliness_score_param": 1.2,

    "compute_metrics_enabled" : True,

    ####
    # GRAPH MODIFICATION FUNCTIONS

    # Also enables the edge calculation function.
    "graph_modification_functions": True,

    # If set, the node weight is set to 100 if the node arrives at the shelter,
    # otherwise the node is removed from the graph.
    "alter_arrived_node_weight_to_100": False,

    # Uses generalized additive models from R to generate prediction of nodes not
    # arrived. This sets the node weight on unarrived nodes the the prediction
    # given by a GAM.
    # Needs POPULATION_LOCATION_FILE to be set.
    "alter_node_weight_to_gam_prediction": False,
    
    # Enables edge expansion when graph_modification_functions is set to true
    "edge_expansion_enabled": True,

    # The value of 'k' used in the GAM will be the number of nodes arrived until
    # it reaches this max value.
    "gam_k_value": 100,

    # Alter the edge weight for nodes that haven't arrived. This is a way to
    # de-emphasise the prediction model for the unknown nodes.
    "prediction_model_emphasis": 1.0,
    
    # This applies the prediction_list_file node weights onto the nodes in the graph
    # when the prediction model is being computed and then removes the weights
    # for the cutoff and batch arrival modes
    "apply_prediction_model_weights": True,

    "SCOTCH_LIB_PATH": os.path.join(pwd, "libs/scotch/macOS/libscotch.dylib")
    if 'Darwin' in platform.system()
    else "/usr/local/lib/libscotch.so",
    
    # Path to the PaToH shared library
    "PATOH_LIB_PATH": os.path.join(pwd, "libs/patoh/lib/macOS/libpatoh.dylib")
    if 'Darwin' in platform.system()
    else os.path.join(pwd, "libs/patoh/lib/linux/libpatoh.so"),
    
    "PATOH_ITERATIONS": 5,
        
    # Expansion modes: 'avg_node_weight', 'total_node_weight', 'smallest_node_weight'
    # 'largest_node_weight'
    # add '_squared' or '_sqrt' at the end of any of the above for ^2 or sqrt(weight)
    # i.e. 'avg_node_weight_squared
    "PATOH_HYPEREDGE_EXPANSION_MODE": 'no_expansion',
    
    # Edge Expansion: average, total, minimum, maximum, product, product_squared, sqrt_product
    "EDGE_EXPANSION_MODE" : 'total',
    
    # Whether nodes should be reordered using a centrality metric for optimal node assignments in batch mode
    # This is specific to FENNEL and at the moment Leverage Centrality is used to compute new noder orders
    "FENNEL_NODE_REORDERING_ENABLED": False,
    
    # The node ordering scheme: PII_LH (political index), LEVERAGE_HL
    "FENNEL_NODE_REODERING_SCHEME": 'LEVERAGE_HL',
    
    # Whether the Friend of a Friend scoring system is active during FENNEL partitioning.
    # FOAF employs information about a node's friends to determine the best partition when
    # this node arrives at a shelter and no shelter has friends already arrived
    "FENNEL_FRIEND_OF_A_FRIEND_ENABLED": False,
    
    # Alters how much information to print. Keep it at 1 for this notebook.
    # 0 - will print nothing, useful for batch operations.
    # 1 - prints basic information on assignments and operations.
    # 2 - prints more information as it batches arrivals.
    "verbose": 1
}

#gp = GraphPartitioning(config)

# Optional: shuffle the order of nodes arriving
# Arrival order should not be shuffled if using GAM to alter node weights
#random.shuffle(gp.arrival_order)

%pylab inline


Populating the interactive namespace from numpy and matplotlib

Prediction Model


In [24]:
from copy import deepcopy

# make a copy of configuration file
conf = deepcopy(config)

#with GraphPartitioning(conf) as gp:
gp = GraphPartitioning(conf)
gp.verbose = 0
gp.load_network()
gp.init_partitioner()

m = gp.prediction_model()
m = gp.assign_cut_off()
m = gp.batch_arrival()

rows = list(range(1, len(m)+1))
df = pd.DataFrame(m, index=rows, columns=cols).astype(float)
print(df)


      WASTE  CUT RATIO  EDGES CUT  TOTAL COMM VOLUME       Qds  CONDUCTANCE  \
1  0.040000   0.125000        2.0                4.0  0.583148     0.000000   
2  0.000000   0.178082       13.0               24.0  0.644251     0.000000   
3  0.013333   0.173611       25.0               42.0  0.613617     0.007439   
4  0.040000   0.155709       45.0               71.0  0.529345     0.033124   
5  0.024000   0.185501       87.0              123.0  0.463204     0.054200   
6  0.026667   0.186747      124.0              169.0  0.439884     0.056554   
7  0.041801   0.187324      133.0              180.0  0.438307     0.070629   

    MAXPERM      RBSE       NMI    FSCORE  FSCORE RELABEL IMPROVEMENT  \
1 -0.444091  0.020000  0.139881  0.309231                    0.131667   
2 -0.056667  0.060000  0.076165  0.303426                    0.110330   
3  0.080429  0.060000  0.084663  0.305907                    0.104807   
4  0.224845  0.065000  0.106204  0.299158                    0.139444   
5  0.317391  0.068000  0.101017  0.285245                    0.154406   
6  0.329095  0.073333  0.110163  0.292382                    0.148160   
7  0.350525  0.080386  0.113257  0.301010                    0.146139   

   LONELINESS  
1    0.292424  
2    0.470187  
3    0.554224  
4    0.653034  
5    0.707293  
6    0.745886  
7    0.753012  

In [31]:
GArrived = gp.G.subgraph(gp.nodes_arrived)
#print(GArrived.nodes())
#print(gp._batches)

def findPartitionOfNode(nodeID, assignments):
    partition = -1
    for i in range(0, config['num_partitions']):
        partitionAssignments = assignments[i]
        if nodeID in partitionAssignments:
            partition = i
            break
    return partition

def recordCut(data, n1, n2):
    smaller = n1
    larger = n2
    if n2 < n1:
        smaller = n2
        larger = n1
    
    if smaller in data:
        if larger not in data[smaller]:
            data[smaller].append(larger)
    else:
        data[smaller] = [larger]
    return data
    
def countCuts(data):
    cuts = 0
    for key in list(data.keys()):
        cuts += len(data[key])
    return cuts
        
        
def computeAssignmentStats(GArrived, gp, assignments):
    arrivedNodes = 0
    #totalCutEdges = 0
    totalUnassignedEdges = 0
    unassignedNodes = []
    
    cutEdges = {}
    allMissing = {}
    allCorrect = {}
    
    for i in range(0, config['num_partitions']):
        partitionAssignments = assignments[i]
        for node in partitionAssignments:
            arrivedNodes += 1
            # total number of friends
            neighbors = GArrived.neighbors(node)
            
            # friends in current partition
            samePartitionFriends = []
            otherPartitionFriends = []
            unassignedFriends = []
            for neighbor in neighbors:
                neighborPartition = findPartitionOfNode(neighbor, assignments)
                
                if neighborPartition == i:
                    samePartitionFriends.append(neighbor)
                    allCorrect = recordCut(allCorrect, node, neighbor)
                else:
                    if neighborPartition == -1:
                        unassignedFriends.append(neighbor)
                        if neighbor not in unassignedNodes:
                            unassignedNodes.append(neighbor)
                    else:
                        otherPartitionFriends.append(neighbor)
                    # record all nodes in other partitions
                    allMissing = recordCut(allMissing, node, neighbor)
                
                #if neighborPartition == -1:
                #    unassignedFriends.append(neighbor)
                #    if neighbor not in unassignedNodes:
                #        unassignedNodes.append(neighbor)
                #elif neighborPartition == i:
                #    samePartitionFriends.append(neighbor)
                #else:
                #    otherPartitionFriends.append(neighbor)
                    
                
            
            for edgeCut in otherPartitionFriends:
                cutEdges = recordCut(cutEdges, node, edgeCut)
            
            #cut = countCuts(cutEdges)
            unassigned = len(unassignedFriends)
            
            #totalCutEdges += cut
            totalUnassignedEdges += unassigned
    return [arrivedNodes, countCuts(cutEdges), len(unassignedNodes), countCuts(allMissing), countCuts(allCorrect)]#totalUnassignedEdges]
                
print('Arrived Nodes', GArrived.number_of_nodes())
print('Arrived Edges', GArrived.number_of_edges())

assignments = []
for i in range(0, config['num_partitions']):
    assignments.append([])


totalCuts = []
totalUnassigned = []
cumulativeCuts = []

averageCuts = []
averageUnassigned = []
averageCumulativeCuts = []

nodesArrived = []

totalEdges = GArrived.number_of_edges()
totalNodes = GArrived.number_of_nodes()

for batch in gp._batches:
    for node in batch:
        assignment = gp.assignments[node]
        # assign this node, just like in the simulation
        assignments[assignment].append(node)
        
        # compute stats for full arrivals list
        stats = computeAssignmentStats(GArrived, gp, assignments)
        
        totalCuts.append(stats[1])
        totalUnassigned.append(stats[2])
        cumulativeCuts.append(totalEdges - stats[4])
    
        averageCuts.append(stats[1] / stats[0])
        averageUnassigned.append(stats[2] / stats[0])
        averageCumulativeCuts.append((totalEdges - stats[4]) / totalNodes)
        
        nodesArrived.append(stats[0])


Arrived Nodes 311
Arrived Edges 710

In [26]:
import matplotlib
import matplotlib.pyplot as plt

plt.figure(figsize=(10, 10))
plt.plot(nodesArrived, totalCuts)
plt.plot(nodesArrived, totalUnassigned)
#plt.plot(nodesArrived, cumulativeCuts)
plt.legend(['Total Edges Cut', 'Total Unassigned Nodes'])
plt.title('Total Edges cut and Unassigned Nodes per arrival iteration')
plt.xlabel('Number of Arrived Nodes')
plt.ylabel('Edges Cut/Unassigned Nodes')
plt.show()
plt.savefig('total_cuts_unassigned_nodes.png')


<matplotlib.figure.Figure at 0x10bf942e8>

In [27]:
plt.figure(figsize=(10, 10))
plt.plot(nodesArrived, averageCuts)
plt.title('Average Edges cut')
plt.xlabel('Number of Arrived Nodes')
plt.ylabel('Average Edges Cut')
plt.show()
plt.savefig('average_cut_nodes.png')


<matplotlib.figure.Figure at 0x10c8b2978>

In [28]:
plt.figure(figsize=(10, 10))
plt.plot(nodesArrived, averageUnassigned)
plt.title('Average Unassigned Nodes per arrival iteration')
plt.xlabel('Number of Arrived Nodes')
plt.ylabel('Average Unassigned Nodes')
plt.show()
plt.savefig('average_unassigned_nodes.png')


<matplotlib.figure.Figure at 0x10ba30ba8>

In [32]:
plt.figure(figsize=(10, 10))
plt.plot(nodesArrived, averageCumulativeCuts)
plt.title('Average Edges cut')
plt.xlabel('Number of Arrived Nodes')
plt.ylabel('Average Edges Cut')
plt.show()



In [33]:
print('arrived_nodes,total_cuts,total_unassigned_friends,total_unassigned_and_cut,average_cuts,average_unassigned_friends,average_unassigned_and_cut')
for i in range(0, len(nodesArrived)):
    s = ''
    s = str(i + 1) + ',' + str(totalCuts[i]) + ',' + str(totalUnassigned[i]) + ',' + str(cumulativeCuts[i]) + ',' + str(averageCuts[i]) + ',' + str(averageUnassigned[i]) + ',' + str(averageCumulativeCuts[i])
    print(s)


arrived_nodes,total_cuts,total_unassigned_friends,total_unassigned_and_cut,average_cuts,average_unassigned_friends,average_unassigned_and_cut
1,0,7,710,0.0,7.0,2.282958199356913
2,0,9,710,0.0,4.5,2.282958199356913
3,0,16,710,0.0,5.333333333333333,2.282958199356913
4,0,20,710,0.0,5.0,2.282958199356913
5,0,21,710,0.0,4.2,2.282958199356913
6,0,25,710,0.0,4.166666666666667,2.282958199356913
7,0,35,710,0.0,5.0,2.282958199356913
8,0,38,710,0.0,4.75,2.282958199356913
9,0,46,710,0.0,5.111111111111111,2.282958199356913
10,0,50,710,0.0,5.0,2.282958199356913
11,0,52,710,0.0,4.7272727272727275,2.282958199356913
12,0,52,709,0.0,4.333333333333333,2.279742765273312
13,0,52,709,0.0,4.0,2.279742765273312
14,0,58,709,0.0,4.142857142857143,2.279742765273312
15,0,60,709,0.0,4.0,2.279742765273312
16,0,63,708,0.0,3.9375,2.2765273311897105
17,0,68,708,0.0,4.0,2.2765273311897105
18,0,73,708,0.0,4.055555555555555,2.2765273311897105
19,0,77,708,0.0,4.052631578947368,2.2765273311897105
20,0,83,708,0.0,4.15,2.2765273311897105
21,0,85,708,0.0,4.0476190476190474,2.2765273311897105
22,0,92,708,0.0,4.181818181818182,2.2765273311897105
23,0,96,708,0.0,4.173913043478261,2.2765273311897105
24,0,95,707,0.0,3.9583333333333335,2.2733118971061095
25,1,96,706,0.04,3.84,2.270096463022508
26,1,97,706,0.038461538461538464,3.730769230769231,2.270096463022508
27,1,103,706,0.037037037037037035,3.814814814814815,2.270096463022508
28,1,106,706,0.03571428571428571,3.7857142857142856,2.270096463022508
29,1,106,705,0.034482758620689655,3.6551724137931036,2.266881028938907
30,1,111,705,0.03333333333333333,3.7,2.266881028938907
31,1,115,705,0.03225806451612903,3.7096774193548385,2.266881028938907
32,1,116,704,0.03125,3.625,2.2636655948553055
33,1,117,703,0.030303030303030304,3.5454545454545454,2.260450160771704
34,1,120,703,0.029411764705882353,3.5294117647058822,2.260450160771704
35,1,121,702,0.02857142857142857,3.4571428571428573,2.257234726688103
36,1,125,701,0.027777777777777776,3.4722222222222223,2.2540192926045015
37,1,131,701,0.02702702702702703,3.5405405405405403,2.2540192926045015
38,1,131,701,0.02631578947368421,3.4473684210526314,2.2540192926045015
39,1,136,701,0.02564102564102564,3.4871794871794872,2.2540192926045015
40,1,136,701,0.025,3.4,2.2540192926045015
41,1,139,701,0.024390243902439025,3.3902439024390243,2.2540192926045015
42,1,140,700,0.023809523809523808,3.3333333333333335,2.2508038585209005
43,1,139,699,0.023255813953488372,3.2325581395348837,2.247588424437299
44,1,141,699,0.022727272727272728,3.2045454545454546,2.247588424437299
45,1,141,699,0.022222222222222223,3.1333333333333333,2.247588424437299
46,2,140,698,0.043478260869565216,3.0434782608695654,2.2443729903536975
47,2,141,698,0.0425531914893617,3.0,2.2443729903536975
48,2,140,697,0.041666666666666664,2.9166666666666665,2.2411575562700965
49,2,140,696,0.04081632653061224,2.857142857142857,2.237942122186495
50,2,141,696,0.04,2.82,2.237942122186495
51,2,143,696,0.0392156862745098,2.803921568627451,2.237942122186495
52,2,144,696,0.038461538461538464,2.769230769230769,2.237942122186495
53,2,146,696,0.03773584905660377,2.7547169811320753,2.237942122186495
54,2,146,695,0.037037037037037035,2.7037037037037037,2.234726688102894
55,3,147,694,0.05454545454545454,2.672727272727273,2.2315112540192925
56,4,146,693,0.07142857142857142,2.607142857142857,2.2282958199356915
57,4,148,693,0.07017543859649122,2.5964912280701755,2.2282958199356915
58,4,152,693,0.06896551724137931,2.6206896551724137,2.2282958199356915
59,4,152,693,0.06779661016949153,2.5762711864406778,2.2282958199356915
60,4,155,693,0.06666666666666667,2.5833333333333335,2.2282958199356915
61,4,158,693,0.06557377049180328,2.5901639344262297,2.2282958199356915
62,4,157,692,0.06451612903225806,2.532258064516129,2.22508038585209
63,5,156,691,0.07936507936507936,2.4761904761904763,2.2218649517684885
64,5,156,690,0.078125,2.4375,2.2186495176848875
65,5,157,690,0.07692307692307693,2.4153846153846152,2.2186495176848875
66,6,158,688,0.09090909090909091,2.393939393939394,2.212218649517685
67,6,161,688,0.08955223880597014,2.4029850746268657,2.212218649517685
68,6,163,687,0.08823529411764706,2.3970588235294117,2.2090032154340835
69,6,163,686,0.08695652173913043,2.36231884057971,2.2057877813504825
70,6,164,685,0.08571428571428572,2.342857142857143,2.202572347266881
71,6,166,684,0.08450704225352113,2.3380281690140845,2.1993569131832795
72,7,167,683,0.09722222222222222,2.3194444444444446,2.1961414790996785
73,7,168,680,0.0958904109589041,2.3013698630136985,2.1864951768488745
74,7,168,678,0.0945945945945946,2.27027027027027,2.180064308681672
75,7,170,678,0.09333333333333334,2.2666666666666666,2.180064308681672
76,7,170,677,0.09210526315789473,2.236842105263158,2.1768488745980705
77,7,170,677,0.09090909090909091,2.207792207792208,2.1768488745980705
78,8,169,674,0.10256410256410256,2.1666666666666665,2.167202572347267
79,8,168,673,0.10126582278481013,2.1265822784810124,2.1639871382636655
80,8,168,673,0.1,2.1,2.1639871382636655
81,8,167,672,0.09876543209876543,2.0617283950617282,2.1607717041800645
82,8,169,672,0.0975609756097561,2.0609756097560976,2.1607717041800645
83,8,168,670,0.0963855421686747,2.0240963855421685,2.1543408360128615
84,8,168,670,0.09523809523809523,2.0,2.1543408360128615
85,8,167,669,0.09411764705882353,1.964705882352941,2.1511254019292605
86,8,166,666,0.09302325581395349,1.930232558139535,2.1414790996784565
87,9,165,665,0.10344827586206896,1.896551724137931,2.1382636655948555
88,9,166,665,0.10227272727272728,1.8863636363636365,2.1382636655948555
89,9,168,663,0.10112359550561797,1.8876404494382022,2.1318327974276525
90,9,167,659,0.1,1.8555555555555556,2.1189710610932475
91,9,166,658,0.0989010989010989,1.8241758241758241,2.1157556270096465
92,9,165,656,0.09782608695652174,1.7934782608695652,2.1093247588424435
93,9,166,656,0.0967741935483871,1.7849462365591398,2.1093247588424435
94,9,166,655,0.09574468085106383,1.7659574468085106,2.1061093247588425
95,9,165,654,0.09473684210526316,1.736842105263158,2.102893890675241
96,9,166,653,0.09375,1.7291666666666667,2.09967845659164
97,10,165,652,0.10309278350515463,1.7010309278350515,2.0964630225080385
98,10,165,652,0.10204081632653061,1.683673469387755,2.0964630225080385
99,12,166,651,0.12121212121212122,1.6767676767676767,2.0932475884244375
100,13,165,650,0.13,1.65,2.090032154340836
101,13,165,650,0.12871287128712872,1.6336633663366336,2.090032154340836
102,13,164,649,0.12745098039215685,1.607843137254902,2.0868167202572345
103,13,165,649,0.1262135922330097,1.6019417475728155,2.0868167202572345
104,13,164,648,0.125,1.5769230769230769,2.0836012861736335
105,13,163,647,0.12380952380952381,1.5523809523809524,2.080385852090032
106,14,163,646,0.1320754716981132,1.5377358490566038,2.077170418006431
107,14,164,646,0.1308411214953271,1.5327102803738317,2.077170418006431
108,14,164,646,0.12962962962962962,1.5185185185185186,2.077170418006431
109,14,163,645,0.12844036697247707,1.4954128440366972,2.0739549839228295
110,14,165,645,0.12727272727272726,1.5,2.0739549839228295
111,14,164,644,0.12612612612612611,1.4774774774774775,2.0707395498392285
112,14,164,644,0.125,1.4642857142857142,2.0707395498392285
113,14,165,644,0.12389380530973451,1.4601769911504425,2.0707395498392285
114,14,167,644,0.12280701754385964,1.4649122807017543,2.0707395498392285
115,14,167,643,0.12173913043478261,1.4521739130434783,2.067524115755627
116,14,167,643,0.1206896551724138,1.4396551724137931,2.067524115755627
117,14,167,643,0.11965811965811966,1.4273504273504274,2.067524115755627
118,15,166,642,0.1271186440677966,1.4067796610169492,2.0643086816720255
119,15,165,641,0.12605042016806722,1.3865546218487395,2.0610932475884245
120,15,164,640,0.125,1.3666666666666667,2.057877813504823
121,15,163,639,0.12396694214876033,1.3471074380165289,2.054662379421222
122,17,162,636,0.13934426229508196,1.3278688524590163,2.045016077170418
123,17,162,634,0.13821138211382114,1.3170731707317074,2.0385852090032155
124,18,161,633,0.14516129032258066,1.2983870967741935,2.035369774919614
125,18,160,632,0.144,1.28,2.032154340836013
126,19,159,630,0.15079365079365079,1.2619047619047619,2.0257234726688105
127,19,160,629,0.14960629921259844,1.2598425196850394,2.022508038585209
128,19,160,629,0.1484375,1.25,2.022508038585209
129,19,159,628,0.14728682170542637,1.2325581395348837,2.0192926045016075
130,20,158,625,0.15384615384615385,1.2153846153846153,2.009646302250804
131,20,157,624,0.15267175572519084,1.1984732824427482,2.0064308681672025
132,20,156,622,0.15151515151515152,1.1818181818181819,2.0
133,20,155,620,0.15037593984962405,1.1654135338345866,1.9935691318327975
134,21,154,617,0.15671641791044777,1.1492537313432836,1.9839228295819935
135,21,154,616,0.15555555555555556,1.1407407407407408,1.9807073954983923
136,21,153,612,0.15441176470588236,1.125,1.9678456591639872
137,21,152,611,0.15328467153284672,1.1094890510948905,1.9646302250803858
138,21,152,611,0.15217391304347827,1.1014492753623188,1.9646302250803858
139,22,151,610,0.15827338129496402,1.0863309352517985,1.9614147909967845
140,22,150,608,0.15714285714285714,1.0714285714285714,1.954983922829582
141,23,150,604,0.16312056737588654,1.0638297872340425,1.9421221864951768
142,24,149,603,0.16901408450704225,1.0492957746478873,1.9389067524115755
143,25,148,602,0.17482517482517482,1.034965034965035,1.9356913183279743
144,25,147,601,0.1736111111111111,1.0208333333333333,1.932475884244373
145,25,148,599,0.1724137931034483,1.0206896551724138,1.9260450160771705
146,25,147,597,0.17123287671232876,1.0068493150684932,1.9196141479099678
147,25,146,595,0.17006802721088435,0.9931972789115646,1.9131832797427653
148,25,145,593,0.16891891891891891,0.9797297297297297,1.9067524115755627
149,25,144,592,0.16778523489932887,0.9664429530201343,1.9035369774919615
150,25,143,591,0.16666666666666666,0.9533333333333334,1.9003215434083602
151,25,144,591,0.16556291390728478,0.9536423841059603,1.9003215434083602
152,26,143,590,0.17105263157894737,0.9407894736842105,1.8971061093247588
153,26,142,588,0.16993464052287582,0.9281045751633987,1.8906752411575563
154,27,141,584,0.17532467532467533,0.9155844155844156,1.8778135048231512
155,27,141,584,0.17419354838709677,0.9096774193548387,1.8778135048231512
156,28,140,583,0.1794871794871795,0.8974358974358975,1.8745980707395498
157,28,139,579,0.17834394904458598,0.8853503184713376,1.8617363344051447
158,28,139,576,0.17721518987341772,0.879746835443038,1.8520900321543408
159,31,138,574,0.1949685534591195,0.8679245283018868,1.8456591639871383
160,31,137,571,0.19375,0.85625,1.8360128617363345
161,31,136,570,0.19254658385093168,0.84472049689441,1.832797427652733
162,31,135,569,0.19135802469135801,0.8333333333333334,1.8295819935691318
163,31,134,565,0.1901840490797546,0.8220858895705522,1.8167202572347267
164,31,133,563,0.18902439024390244,0.8109756097560976,1.810289389067524
165,33,132,560,0.2,0.8,1.8006430868167203
166,35,131,554,0.21084337349397592,0.7891566265060241,1.7813504823151125
167,35,131,553,0.20958083832335328,0.7844311377245509,1.7781350482315113
168,36,130,552,0.21428571428571427,0.7738095238095238,1.77491961414791
169,36,129,548,0.21301775147928995,0.7633136094674556,1.7620578778135048
170,36,128,546,0.21176470588235294,0.7529411764705882,1.7556270096463023
171,37,127,545,0.21637426900584794,0.7426900584795322,1.752411575562701
172,37,126,543,0.21511627906976744,0.7325581395348837,1.7459807073954985
173,37,125,540,0.2138728323699422,0.7225433526011561,1.7363344051446945
174,37,124,537,0.21264367816091953,0.7126436781609196,1.7266881028938907
175,37,123,533,0.21142857142857144,0.7028571428571428,1.7138263665594855
176,37,123,531,0.21022727272727273,0.6988636363636364,1.707395498392283
177,38,122,530,0.21468926553672316,0.6892655367231638,1.7041800643086817
178,38,121,529,0.21348314606741572,0.6797752808988764,1.7009646302250805
179,38,120,524,0.2122905027932961,0.6703910614525139,1.684887459807074
180,38,119,521,0.2111111111111111,0.6611111111111111,1.67524115755627
181,38,119,521,0.20994475138121546,0.6574585635359116,1.67524115755627
182,39,118,519,0.21428571428571427,0.6483516483516484,1.6688102893890675
183,39,117,518,0.21311475409836064,0.639344262295082,1.6655948553054662
184,40,116,516,0.21739130434782608,0.6304347826086957,1.6591639871382637
185,40,115,512,0.21621621621621623,0.6216216216216216,1.6463022508038585
186,40,114,507,0.21505376344086022,0.6129032258064516,1.630225080385852
187,40,113,504,0.21390374331550802,0.6042780748663101,1.6205787781350482
188,40,112,503,0.2127659574468085,0.5957446808510638,1.617363344051447
189,40,111,501,0.21164021164021163,0.5873015873015873,1.6109324758842443
190,40,110,500,0.21052631578947367,0.5789473684210527,1.607717041800643
191,41,109,498,0.21465968586387435,0.5706806282722513,1.6012861736334405
192,41,108,495,0.21354166666666666,0.5625,1.5916398713826367
193,41,107,492,0.21243523316062177,0.5544041450777202,1.5819935691318328
194,41,106,490,0.211340206185567,0.5463917525773195,1.5755627009646302
195,42,105,485,0.2153846153846154,0.5384615384615384,1.5594855305466238
196,43,104,483,0.2193877551020408,0.5306122448979592,1.5530546623794212
197,43,103,478,0.2182741116751269,0.5228426395939086,1.5369774919614148
198,45,102,470,0.22727272727272727,0.5151515151515151,1.5112540192926045
199,45,101,467,0.22613065326633167,0.507537688442211,1.5016077170418007
200,45,100,466,0.225,0.5,1.4983922829581993
201,46,99,465,0.22885572139303484,0.4925373134328358,1.495176848874598
202,46,98,460,0.22772277227722773,0.48514851485148514,1.4790996784565917
203,50,97,457,0.24630541871921183,0.47783251231527096,1.4694533762057878
204,51,96,455,0.25,0.47058823529411764,1.4630225080385852
205,53,95,451,0.25853658536585367,0.4634146341463415,1.45016077170418
206,53,94,449,0.25728155339805825,0.4563106796116505,1.4437299035369775
207,55,93,448,0.26570048309178745,0.4492753623188406,1.4405144694533762
208,55,92,445,0.2644230769230769,0.4423076923076923,1.4308681672025723
209,55,91,442,0.2631578947368421,0.4354066985645933,1.4212218649517685
210,55,91,442,0.2619047619047619,0.43333333333333335,1.4212218649517685
211,57,90,440,0.27014218009478674,0.4265402843601896,1.414790996784566
212,59,89,438,0.2783018867924528,0.419811320754717,1.4083601286173633
213,60,88,432,0.28169014084507044,0.4131455399061033,1.3890675241157557
214,62,87,422,0.2897196261682243,0.40654205607476634,1.3569131832797428
215,63,86,420,0.2930232558139535,0.4,1.3504823151125402
216,63,87,420,0.2916666666666667,0.4027777777777778,1.3504823151125402
217,65,86,418,0.2995391705069124,0.39631336405529954,1.3440514469453375
218,65,85,416,0.2981651376146789,0.38990825688073394,1.337620578778135
219,67,85,414,0.3059360730593607,0.3881278538812785,1.3311897106109325
220,68,84,410,0.3090909090909091,0.38181818181818183,1.3183279742765273
221,69,83,406,0.31221719457013575,0.3755656108597285,1.3054662379421222
222,69,82,404,0.3108108108108108,0.36936936936936937,1.2990353697749195
223,69,81,399,0.3094170403587444,0.3632286995515695,1.2829581993569132
224,69,80,397,0.3080357142857143,0.35714285714285715,1.2765273311897105
225,72,79,393,0.32,0.3511111111111111,1.2636655948553055
226,72,78,389,0.3185840707964602,0.34513274336283184,1.2508038585209003
227,72,77,387,0.31718061674008813,0.3392070484581498,1.2443729903536977
228,73,76,383,0.3201754385964912,0.3333333333333333,1.2315112540192925
229,74,75,382,0.3231441048034934,0.32751091703056767,1.2282958199356913
230,76,76,381,0.33043478260869563,0.33043478260869563,1.22508038585209
231,76,75,375,0.329004329004329,0.3246753246753247,1.2057877813504823
232,76,74,374,0.3275862068965517,0.31896551724137934,1.202572347266881
233,76,73,373,0.3261802575107296,0.3133047210300429,1.1993569131832797
234,76,72,370,0.3247863247863248,0.3076923076923077,1.189710610932476
235,76,71,366,0.32340425531914896,0.3021276595744681,1.1768488745980707
236,76,71,363,0.3220338983050847,0.3008474576271186,1.167202572347267
237,76,70,362,0.3206751054852321,0.29535864978902954,1.1639871382636655
238,76,69,360,0.31932773109243695,0.28991596638655465,1.157556270096463
239,76,68,353,0.3179916317991632,0.28451882845188287,1.135048231511254
240,80,67,349,0.3333333333333333,0.2791666666666667,1.1221864951768488
241,82,66,346,0.34024896265560167,0.27385892116182575,1.112540192926045
242,82,65,343,0.33884297520661155,0.26859504132231404,1.1028938906752412
243,82,64,340,0.3374485596707819,0.26337448559670784,1.0932475884244373
244,84,63,338,0.3442622950819672,0.2581967213114754,1.0868167202572347
245,84,62,336,0.34285714285714286,0.2530612244897959,1.0803858520900322
246,84,61,335,0.34146341463414637,0.24796747967479674,1.0771704180064308
247,84,61,335,0.340080971659919,0.24696356275303644,1.0771704180064308
248,84,60,331,0.3387096774193548,0.24193548387096775,1.0643086816720257
249,85,59,329,0.3413654618473896,0.23694779116465864,1.0578778135048232
250,87,58,328,0.348,0.232,1.0546623794212218
251,89,57,326,0.3545816733067729,0.22709163346613545,1.0482315112540193
252,90,56,319,0.35714285714285715,0.2222222222222222,1.0257234726688103
253,90,55,313,0.3557312252964427,0.21739130434782608,1.0064308681672025
254,92,54,310,0.36220472440944884,0.2125984251968504,0.9967845659163987
255,92,53,304,0.3607843137254902,0.20784313725490197,0.977491961414791
256,93,52,302,0.36328125,0.203125,0.9710610932475884
257,93,51,301,0.36186770428015563,0.19844357976653695,0.9678456591639871
258,95,50,297,0.3682170542635659,0.1937984496124031,0.954983922829582
259,95,49,291,0.3667953667953668,0.1891891891891892,0.9356913183279743
260,95,48,288,0.36538461538461536,0.18461538461538463,0.9260450160771704
261,95,47,286,0.36398467432950193,0.18007662835249041,0.9196141479099679
262,95,46,279,0.36259541984732824,0.17557251908396945,0.8971061093247589
263,95,45,273,0.3612167300380228,0.17110266159695817,0.8778135048231511
264,98,44,270,0.3712121212121212,0.16666666666666666,0.8681672025723473
265,98,43,268,0.36981132075471695,0.16226415094339622,0.8617363344051447
266,100,42,265,0.37593984962406013,0.15789473684210525,0.8520900321543409
267,101,41,263,0.3782771535580524,0.15355805243445692,0.8456591639871383
268,101,40,260,0.376865671641791,0.14925373134328357,0.8360128617363344
269,101,39,253,0.3754646840148699,0.1449814126394052,0.8135048231511254
270,101,38,245,0.37407407407407406,0.14074074074074075,0.7877813504823151
271,101,37,242,0.3726937269372694,0.13653136531365315,0.7781350482315113
272,102,36,239,0.375,0.1323529411764706,0.7684887459807074
273,105,35,236,0.38461538461538464,0.1282051282051282,0.7588424437299035
274,105,34,227,0.38321167883211676,0.12408759124087591,0.729903536977492
275,106,33,225,0.38545454545454544,0.12,0.7234726688102894
276,106,32,218,0.38405797101449274,0.11594202898550725,0.7009646302250804
277,108,31,216,0.3898916967509025,0.11191335740072202,0.6945337620578779
278,109,30,214,0.3920863309352518,0.1079136690647482,0.6881028938906752
279,109,29,213,0.3906810035842294,0.1039426523297491,0.684887459807074
280,109,28,211,0.3892857142857143,0.1,0.6784565916398714
281,109,27,204,0.3879003558718861,0.09608540925266904,0.6559485530546624
282,109,26,201,0.38652482269503546,0.09219858156028368,0.6463022508038585
283,109,26,201,0.38515901060070673,0.09187279151943463,0.6463022508038585
284,109,25,200,0.38380281690140844,0.0880281690140845,0.6430868167202572
285,111,24,196,0.3894736842105263,0.08421052631578947,0.6302250803858521
286,111,23,194,0.3881118881118881,0.08041958041958042,0.6237942122186495
287,114,22,193,0.397212543554007,0.07665505226480836,0.6205787781350482
288,114,21,191,0.3958333333333333,0.07291666666666667,0.6141479099678456
289,115,20,189,0.39792387543252594,0.06920415224913495,0.6077170418006431
290,116,19,188,0.4,0.06551724137931035,0.6045016077170418
291,120,18,184,0.41237113402061853,0.061855670103092786,0.5916398713826366
292,120,17,182,0.410958904109589,0.05821917808219178,0.5852090032154341
293,120,16,181,0.40955631399317405,0.05460750853242321,0.5819935691318328
294,121,15,179,0.41156462585034015,0.05102040816326531,0.5755627009646302
295,122,14,177,0.4135593220338983,0.04745762711864407,0.5691318327974276
296,122,14,177,0.41216216216216217,0.0472972972972973,0.5691318327974276
297,123,13,176,0.41414141414141414,0.04377104377104377,0.5659163987138264
298,123,12,175,0.412751677852349,0.040268456375838924,0.5627009646302251
299,123,12,175,0.411371237458194,0.04013377926421405,0.5627009646302251
300,124,11,170,0.41333333333333333,0.03666666666666667,0.5466237942122186
301,125,10,169,0.4152823920265781,0.03322259136212625,0.5434083601286174
302,125,9,163,0.4139072847682119,0.029801324503311258,0.5241157556270096
303,125,8,160,0.41254125412541254,0.026402640264026403,0.5144694533762058
304,126,7,156,0.4144736842105263,0.023026315789473683,0.5016077170418006
305,128,6,154,0.419672131147541,0.019672131147540985,0.49517684887459806
306,128,5,150,0.41830065359477125,0.016339869281045753,0.48231511254019294
307,130,4,147,0.4234527687296417,0.013029315960912053,0.47266881028938906
308,132,3,143,0.42857142857142855,0.00974025974025974,0.45980707395498394
309,132,2,141,0.42718446601941745,0.006472491909385114,0.4533762057877814
310,132,1,137,0.4258064516129032,0.0032258064516129032,0.4405144694533762
311,133,0,133,0.42765273311897106,0.0,0.42765273311897106

In [ ]: