def robust_single_linkage(metric, *, k_neighbors, alpha=None, force_ultrametric=False):
    """Robust single linkage algorithm of (Chaudhuri and Dasgupta 2010).

    Args
    ----
    metric : ndarray
        The distance array to transform, in condensed or square form.
    k_neighbors : int, keyword-only
        The number of neighbors to use in the transformation. Must be 
        a non-negative integer.
    alpha : float, keyword-only, optional
        The connection parameter used in the transformation. At time :math:`r`,
        all edges within :math:`\\alpha r` are connected. Default: 
        :math:`\sqrt{2}`.
    force_ultrametric : bool, keyword-only, optional
        If `True`, the resulting clustering is forced to be ultrametric (each
        point is admitted at radius zero).

    Returns
    -------
    clustering : Clustering
        The robust single linkage clustering.

    """
    kwargs = dict(metric=metric, k_neighbors=k_neighbors, alpha=alpha)
    robust_metric, levels = robust_single_linkage_metric(**kwargs)

    if force_ultrametric:
        levels = None

    # note: _hier.single requires condensed metric!
    linkage = _hier.single(robust_metric)
    return Clustering.from_linkage(linkage, levels=levels)

def find_closest_two_points(points):
	
	# use single link clustering to find closest two points
	p = pdist(points)
	slc = single(p)
	
	return np.array([points[slc[0][0]], points[slc[0][1]]])

def make_tree(X, C, method='single'):
    if method == 'single':
        tree = to_tree(single(C))
    elif method == 'ward':
        tree = to_tree(ward(X))
    elif method == 'average':
        tree = to_tree(average(C))
    return Tree(root=construct_node(tree))

def group_tuples(items=None, val_ind=None, dist_thresh = 0.1, distance_matrix=None, 
                 metric='jaccard', linkage='complete', sp_areas=None):
    '''
    items: a dict or list of tuples
    val_ind: the index of the item of interest within each tuple
    '''
    
    if distance_matrix is not None:
        if items is not None:
            if isinstance(items, dict):
                keys = items.keys()
                values = items.values()
            elif isinstance(items, list):
                keys = range(len(items))
                if isinstance(items[0], tuple):
                    values = map(itemgetter(val_ind), items)
                else:
                    values = items
    else:
        if isinstance(items, dict):
            keys = items.keys()
            values = items.values()
        elif isinstance(items, list):
            keys = range(len(items))
            if isinstance(items[0], tuple):
                values = map(itemgetter(val_ind), items)
            else:
                values = items
        else:
            raise Exception('clusters is not the right type')

        assert items is not None, 'items must be provided'
        distance_matrix = compute_pairwise_distances(values, metric, sp_areas=sp_areas)
    
    if items is None:
        assert distance_matrix is not None, 'distance_matrix must be provided.'    
        
    if linkage=='complete':
        lk = complete(squareform(distance_matrix))
    elif linkage=='average':
        lk = average(squareform(distance_matrix))
    elif linkage=='single':
        lk = single(squareform(distance_matrix))

    # T = fcluster(lk, 1.15, criterion='inconsistent')
    T = fcluster(lk, dist_thresh, criterion='distance')
    
    n_groups = len(set(T))
    groups = [None] * n_groups

    for group_id in range(n_groups):
        groups[group_id] = np.where(T == group_id+1)[0]

    index_groups = [[keys[i] for i in g] for g in groups if len(g) > 0]
    item_groups = [[items[i] for i in g] for g in groups if len(g) > 0]
    
    return index_groups, item_groups, distance_matrix

    def cluster_agglomerative(self, n, with_topic):
        #self.n_clusters = n
        if with_topic is True:
            X = self.X_with_topics
        else:
            X = self.X_without_topics

        z = hierarchy.single(pdist(X.toarray(), 'cityblock'))
        self.clusterizer_labels = hierarchy.fcluster(z,n, criterion = 'maxclust')
        cluster_set = set(self.clusterizer_labels)
        self.n_clusters = len(cluster_set) #- (1 if -1 in self.clusterizer_labels else 0)
        if with_topic is True:
            for i in cluster_set: #initialize a dict with cluster no as key to a list
                self.clusters[i] = []
            #adding the actual topics of the cluster to this dict. Mapping of label -> [list of actual topics for the documents clustered in this label]
            for i in range(0,len(self.topic_per_doc)):
                self.clusters[self.clusterizer_labels[i]].append(self.topic_per_doc[i])
            self.generate_piechart_pdf("hierarchical")
        else:
            self.calculate_and_print_silhouette(self.X_without_topics, self.clusterizer_labels, "DBSCAN")

	def CalculateClusterTree(self):
		fullMatrix = self.GenerateFullMatrix(self.results)
		dissMatrix = []
		labels = fullMatrix.keys()
		for i in xrange(0, len(labels)):
			sampleNameI = labels[i]
			for j in xrange(i+1, len(labels)):
				sampleNameJ = labels[j]
				dissMatrix.append(fullMatrix[sampleNameI][sampleNameJ])
				
		# calculate hierarchical cluster tree
		if self.radioSingleLinkage.GetValue():
			linkageMatrix = single(dissMatrix)
		elif self.radioUPGMA.GetValue():
			linkageMatrix = average(dissMatrix)
		elif self.radioCompleteLinkage.GetValue():
			linkageMatrix = complete(dissMatrix)
		elif self.radioWeighted.GetValue():
			linkageMatrix = weighted(dissMatrix)
			
		root = to_tree(linkageMatrix)
		
		# create Newick string
		return self.CreateNewickString(root, labels) + ';'

# <codecell>

np.fill_diagonal(tag_dist_matrix, 0)

# <codecell>

from scipy.spatial.distance import squareform
tag_dist = squareform(tag_dist_matrix)

# <codecell>

from scipy.cluster.hierarchy import single

# <codecell>

tag_linkage = single(tag_dist)

# <codecell>

np.save('tag_linkage',tag_linkage)

# <codecell>

from scipy.cluster.hierarchy import leaves_list, to_tree, dendrogram

# <codecell>

tag_closeness_id = leaves_list(tag_linkage)

# <codecell>

 def check_fcluster_maxclust_monocrit(self, t):
     expectedT = hierarchy_test_data.fcluster_maxclust[t]
     Z = single(hierarchy_test_data.Q_X)
     T = fcluster(Z, t, criterion='maxclust_monocrit', monocrit=maxdists(Z))
     assert_(is_isomorphic(T, expectedT))

 def check_fcluster(self, t, criterion):
     # Tests fcluster(Z, criterion=criterion, t=t) on a random 3-cluster data set.
     expectedT = getattr(hierarchy_test_data, 'fcluster_' + criterion)[t]
     Z = single(hierarchy_test_data.Q_X)
     T = fcluster(Z, criterion=criterion, t=t)
     assert_(is_isomorphic(T, expectedT))

hclust_model = cluster.AgglomerativeClustering(n_clusters = 2, linkage = 'average')
hclust_model.fit(X)
print('Cluster labels: {}\n'.format(hclust_model.labels_))

hclust_model = cluster.AgglomerativeClustering(n_clusters = 2, linkage = 'complete')
hclust_model.fit(X)
print('Cluster labels: {}\n'.format(hclust_model.labels_))


print '''
*********************************************************************************************************************
                                 scipy: dendrogram
*********************************************************************************************************************
'''

# from: https://github.com/JWarmenhoven/ISLR-python/blob/master/Notebooks/Chapter%2010.ipynb

fig, (ax1,ax2,ax3) = plt.subplots(3,1, figsize=(15,18))

for linkage, cluster, ax in zip([hierarchy.complete(X), hierarchy.average(X), hierarchy.single(X)], ['c1','c2','c3'],
                                [ax1,ax2,ax3]):
    cluster = hierarchy.dendrogram(linkage, ax=ax, color_threshold=0)

ax1.set_title('Complete Linkage')
ax2.set_title('Average Linkage')
ax3.set_title('Single Linkage')

plt.show()

    plt.figure()
    newick = final_tree.to_newick()
    tree = Phylo.read(StringIO(newick), 'newick')

    Phylo.draw_graphviz(tree, prog='neato')
    plt.savefig("%s.png" % name, dpi=200, bbox_inches='tight')
X += np.random.normal(scale=0.01, size=X.shape)

pca = PCA(2)
pca.fit(X)

# X = pca.transform(X)
N, D = X.shape

C = pdist(X)
tree = to_tree(single(C))

def construct_node(snode):
    if snode.left is None and snode.right is None:
        return TreeLeaf(snode.get_id())
    node = TreeNode()
    node.add_child(construct_node(snode.left))
    node.add_child(construct_node(snode.right))
    return node

root = construct_node(tree)
linkage_tree = Tree(root=root)
plot_tree(linkage_tree, 'linkage_induced')


if args.tree: