    
from sklearn.neighbors import NearestNeighbors
from sklearn import preprocessing
import numpy as np


def do_knn(post_vectors, output, n_neighbors=20, algorithm='ball_tree'):
    size = len(post_vectors)
    X = np.array(np.mat(';'.join(post_vectors)))
    
    nbrs = NearestNeighbors(n_neighbors=n_neighbors, algorithm=algorithm).fit(X)
    # Because the query set matches the training set, the nearest neighbor of each point is the point itself, at a distance of zero.
    distances, indices = nbrs.kneighbors(X)
    distances = preprocessing.normalize(distances, norm='l2')

    # sort post by weight
    post_dict = {}
    k_rate = 0.005
    top_k = int(k_rate * size)

    graph = []
    for post_id in range(0, size):
        line = post_vectors[post_id].strip().split(' ') 
        post_indices = indices[post_id]
        post_k_distances = distances[post_id]

        post_dict[str(post_id)] = sum(post_k_distances)

        # change to start from 1 for lab propagation library input format
        if max([float(_) for _ in line]) == 0:
            graph_item = [post_id+1, 1]
        else:
            graph_item = [post_id+1, 0]
        post_neighbors = []
        for idx in range(n_neighbors):
            if post_id == post_indices[idx]:
                continue
            post_neighbors.append([post_indices[idx]+1, 1-post_k_distances[idx]])
        graph_item.append(post_neighbors)
        graph.append(str(graph_item))

    output_fh = open(output, 'wb')
    for node in graph:
        output_fh.write(node+'\n')
    output_fh.close()


    post_dict = sorted(post_dict.iteritems(), key=lambda x: x[1], reverse=True)
    post_dict = [int(_[0]) for _ in post_dict]

    return post_dict[:top_k], top_k


def build_graph(input, output, n_neighbors=20, algorithm='ball_tree'):
    n_neighbors += 1

    with open(input, 'rb') as f:
        lines = f.readlines()
        return do_knn(lines, output)


@@ -98,16 +98,30 @@
 y as np%0A
+import random%0A
 %0A%0Adef do
@@ -138,32 +138,50 @@
 vectors, output,
+ post_labels=None,
  n_neighbors=20,
@@ -705,16 +705,755 @@
  size)%0A%0A
+    # load post labels%0A    if not post_labels:%0A        post_labels = %5B0%5D*size%0A%0A    training_index = list(np.random.choice(size-1, int(size*.1), replace=False))%0A    training_index = %5B_+1 for _ in training_index%5D%0A    print 'training size:', len(training_index)%0A    training_index.sort()%0A%0A    testing_index = %5B%5D%0A    testing_labels = %5B%5D%0A    training_labels = %5B%5D%0A    for i in range(len(post_labels)):%0A        post_id = i+1%0A        if post_id in training_index:%0A            training_labels.append(post_labels%5Bi%5D)%0A        else:%0A            testing_labels.append(post_labels%5Bi%5D)%0A            testing_index.append(post_id)%0A            post_labels%5Bi%5D = 0%0A            %0A    # print training_labels%0A    # print training_index%0A    # print testing_index%0A%0A
     grap
@@ -1637,17 +1637,16 @@
 ost_id%5D%0A
-%0A
         
@@ -1698,82 +1698,8 @@
 s)%0A%0A
-        # change to start from 1 for lab propagation library input format%0A
     
@@ -1757,54 +1757,33 @@
     
-graph_item = %5Bpost_id+1, 1%5D%0A        else:%0A    
+post_labels%5Bpost_id%5D = 1%0A
     
@@ -1811,18 +1811,38 @@
 t_id+1, 
-0%5D
+post_labels%5Bpost_id%5D%5D%0A
 %0A       
@@ -2250,17 +2250,16 @@
 lose()%0A%0A
-%0A
     post
@@ -2413,16 +2413,80 @@
 %5D, top_k
+, training_index, training_labels, testing_index, testing_labels
 %0A%0A%0Adef b

update knn for another lp implementation