#!/usr/bin/python
# -*- coding: utf-8 -*-

import itertools

import numpy
import fastcluster
import hcluster
import networkx
from networkx.algorithms.components.connected import connected_components
from scipy.sparse import coo_matrix,dok_matrix
from hungarian import _Hungarian


def condensedDistance(dupes):
    '''
    Convert the pairwise list of distances in dupes to "condensed
    distance matrix" required by the hierarchical clustering
    algorithms. Also return a dictionary that maps the distance matrix
    to the record_ids.
   
    The condensed distance matrix is described in the scipy
    documentation of scipy.cluster.hierarchy.linkage
    http://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html
    '''

    candidate_set = numpy.unique(dupes['pairs'])
    candidate_set = numpy.sort(candidate_set)

    i_to_id = dict(enumerate(candidate_set))

    ids = candidate_set.searchsorted(dupes['pairs'])
    id_1 = ids[:, 0]
    id_2 = ids[:, 1]

    N = len(numpy.union1d(id_1, id_2))
    matrix_length = N * (N - 1) / 2

    step = (N - id_1) * (N - id_1 - 1) / 2
    index = matrix_length - step + id_2 - id_1 - 1

    condensed_distances = numpy.ones(matrix_length, 'f4')
    condensed_distances[index] = 1 - dupes['score']

    return (i_to_id, condensed_distances)


def cluster(dupes, id_type, threshold=.5):
    '''
    Takes in a list of duplicate pairs and clusters them in to a
    list records that all refer to the same entity based on a given
    threshold

    Keyword arguments:
    threshold -- number betweent 0 and 1 (default is .5). lowering the 
                 number will increase precision, raising it will increase
                 recall
    '''

    threshold = 1 - threshold

    score_dtype = [('pairs', id_type, 2), ('score', 'f4', 1)]

    dupe_graph = networkx.Graph()
    dupe_graph.add_weighted_edges_from((x[0], x[1], y) for (x, y) in dupes)

    dupe_sub_graphs = connected_components(dupe_graph)

    clustering = {}
    cluster_id = 0
    for sub_graph in dupe_sub_graphs:
        if len(sub_graph) > 2:
            pair_gen = ((sorted(x[0:2]), x[2]['weight'])
                        for x in dupe_graph.edges_iter(sub_graph, data=True))

            pairs = numpy.fromiter(pair_gen, dtype=score_dtype)

            (i_to_id, condensed_distances) = condensedDistance(pairs)
            linkage = fastcluster.linkage(condensed_distances,
                                          method='centroid', 
                                          preserve_input=False)

            partition = hcluster.fcluster(linkage, 
                                          threshold,
                                          criterion='distance')

            for (i, sub_cluster_id) in enumerate(partition):
                clustering.setdefault(cluster_id + sub_cluster_id, []).append(i_to_id[i])
            
            cluster_id += max(partition)
        else:

            clustering[cluster_id] = sub_graph
            cluster_id += 1

    clusters = [set(l) for l in clustering.values() if len(l) > 1]

    return clusters


def clusterConstrained(dupes,threshold=.6):

    dupe_graph = networkx.Graph()
    dupe_graph.add_weighted_edges_from((x[0], x[1], y) for (x, y) in dupes)

    dupe_sub_graphs = connected_components(dupe_graph)
    clusters = []
    
    for sub_graph in dupe_sub_graphs:
        if len(sub_graph) > 2:
            pairs = (x[0:2] for x in dupe_graph.edges_iter(sub_graph, data=True))
            scores = (x[2]['weight'] for x in dupe_graph.edges_iter(sub_graph, data=True))
            scores = list(scores)
            id_list = numpy.asarray(list(pairs))
            row = list(set(id_list[:,0]))
            row_list = [row.index(a) for a in id_list[:,0]]
            col = list(set(id_list[:,1]))
            col_list = [col.index(a) for a in id_list[:,1]]
            
            scored_pairs = numpy.asarray(coo_matrix((scores,(row_list,col_list))).todense())
            scored_pairs[scored_pairs < threshold] = 0
            scored_pairs = 1 - scored_pairs
            
            m = _Hungarian()
            clustering = m.compute(scored_pairs)
            cluster = [set(l) for l in clustering if len(l) > 1]
            clusters = clusters + cluster
        else:
            clusters.append(set(sub_graph))

    return clusters

@@ -192,16 +192,54 @@
 ponents%0A
+from networkx import adjacency_matrix%0A
 from sci
@@ -3904,16 +3904,17 @@
 t%5B:,1%5D%5D%0A
+%0A
         
@@ -3909,32 +3909,68 @@
 %5D%5D%0A%0A            
+cost_matrix_graph = networkx.Graph()
 %0A            sco
@@ -3970,56 +3970,146 @@
     
-s
 co
-red_pairs = numpy.asarray(coo_matrix((scores,
+st_matrix_graph.add_weighted_edges_from((x, y, z) for (x, y, z) in %5C%0A                                                                zip
 (row
@@ -4114,24 +4114,25 @@
 ow_list,
+ 
 col_list
 ))).tode
@@ -4127,20 +4127,94 @@
 list
-))).todense(
+, scores))%0A            scored_pairs = numpy.asarray(adjacency_matrix(cost_matrix_graph
 ))%0A 

Use Networkx's Adjaceny Matrix, instead of scipy coo_matrix