def random_distribution(n):

    #make up some data
    data = np.random.normal(scale=n, size=(n, n))
    data[0:n / 2,0:n / 2] += 75
    data[n / 2:, n / 2:] = np.random.poisson(lam=n,size=data[n / 2:, n / 2:].shape)
    #cluster the rows
    row_dist = ssd.squareform(ssd.pdist(data))
    row_Z = sch.linkage(row_dist)
    row_idxing = sch.leaves_list(row_Z)

    row_labels = ['bar{}'.format(i) for i in range(n)]

    #cluster the columns
    col_dist = ssd.squareform(ssd.pdist(data.T))
    col_Z = sch.linkage(col_dist)
    col_idxing = sch.leaves_list(col_Z)
    #make the dendrogram

    col_labels = ['foo{}'.format(i) for i in range(n)]

    data = data[:,col_idxing][row_idxing,:]

    heatmap = pdh.DendroHeatMap(heat_map_data=data,left_dendrogram=row_Z, top_dendrogram=col_Z, heatmap_colors=("#ffeda0", "#feb24c", "#f03b20"), window_size="auto", color_legend_displayed=False, label_color="#777777")
    heatmap.row_labels = row_labels
    heatmap.col_labels = col_labels
    heatmap.title = 'An example heatmap'
    heatmap.show()#heatmap.save("example.png")

    def get_clustdist_path(self, feature_ids=None, labeling_name=None,
                           class_ids=None, vmin=-3.0, vmax=3.0, root_dir='.'):

        if not(labeling_name):
            labeling_name = 'one_class'
        #labeling = self.labeling_dict[labeling_name]

        (fm, sample_names, feature_names, target, target_names) =\
            self.get_dataset(feature_ids, labeling_name, class_ids)

        #fistr = '_'.join([str(self.feature_ids.index(f)) for f in
        #    feature_names])
        #listr = '_'.join([str(labeling.class_names.index(t))
        #        for t in target_names])
        #lab_str = 'feati_' + fistr + '_' + labeling_name + '_' + listr

        #png_f = os.path.join(self.heatmap_dir, 'fm_clustered_%s.png' %
        #        (lab_str))
        d = os.path.join(root_dir, self.HEATMAP_D)
        if not(os.path.exists(d)):
            os.makedirs(d)
        img_format = 'png'
        file_path = os.path.join(d, 'fm_clustered.%s' % (img_format))

        # reorder feature matrix rows (objects)
        object_indices = hierarchy.leaves_list(self.clust_object(fm))
        fm = fm[object_indices, :]

        # reorder standardized feature matrix columns (feats)
        feat_indices = hierarchy.leaves_list(self.clust_feat(fm))
        fm = fm[:, feat_indices]

        # add labels of all available labelings (reordered using object_is)
        #lablists = [[l.labels[i] for i in object_indices]
        #                         for l in self.labeling_dict.values()
        #                         if not l.name == 'one_class']
        lablists = [[target[i] for i in object_indices]]
        class_names = [target_names]

        # reorder the feature and object ids
        fs = [feature_names[i] for i in feat_indices]
        gs = [sample_names for i in object_indices]

        heatmap.heatmap_labeled_fig(fm, fs, gs, lablists, class_names,
                                    file_path, vmin=vmin, vmax=vmax)

        return file_path

def cluster(df, metric="euclidean", method="single", row=True, column=True):
    row_linkmat, col_linkmat = None, None
    if row:
        distmat = dist.pdist(df, metric)
        row_linkmat = hier.linkage(distmat, method)
        df = df.iloc[hier.leaves_list(row_linkmat), :]
    if column:
        df = df.T
        distmat = dist.pdist(df, metric)
        col_linkmat = hier.linkage(distmat, method)
        df = df.iloc[hier.leaves_list(col_linkmat), :].T
    return df, row_linkmat, col_linkmat

def rearrange(X, optimal = True, method = "average"):
    metric_kwargs = {}

    Y = squareform(X, force="tovector")
    Z = [(int(l), int(r), max(0., d), int(n))
         for (l, r, d, n) in linkage(Y, method=method, metric=None)]

    leaves = list(leaves_list(Z))
    N      = len(leaves)
    root   = len(Z)+N-1

    assert len(X) == N

    # bar-joseph optimal ordering
    if optimal:
        import barjoseph
        leaves = barjoseph.optimal(root, **{
            "S":        lambda i, j: exp(-X[i][j]),
            "left":     lambda i: None if i < N else Z[i-N][0],
            "right":    lambda i: None if i < N else Z[i-N][1],
            "is_leaf":  lambda i: i < N,
            "is_empty": lambda v: v is None,
        })

    assert list(sorted(leaves)) == list(range(N))

    return leaves

  def to_dict(self, correlation_matrix, linkage_matrix):

    from scipy.cluster import hierarchy
    tree = hierarchy.to_tree(linkage_matrix, rd=False)
    leaves_list = hierarchy.leaves_list(linkage_matrix)

    d = {}

    # http://w3facility.org/question/scipy-dendrogram-to-json-for-d3-js-tree-visualisation/
    # https://gist.github.com/mdml/7537455

    def add_node(node):
      if node.is_leaf(): return
      cluster_id = node.get_id() - len(linkage_matrix) - 1
      row = linkage_matrix[cluster_id]
      d[cluster_id+1] = {
        'datasets': [i+1 for i in sorted(node.pre_order())],
        'height': row[2],
      }

      # Recursively add the current node's children
      if node.left: add_node(node.left)
      if node.right: add_node(node.right)

    add_node(tree)

    return d

 def check_leaves_list_iris(self, method):
     # Tests leaves_list(Z) on the Iris data set
     X = eo['iris']
     Y = pdist(X)
     Z = linkage(X, method)
     node = to_tree(Z)
     assert_equal(node.pre_order(), leaves_list(Z))

def classify_by_scores(M, threshold, loci, return_file_names=None):

    M_array = ssd.squareform(M)

    Z = linkage(M_array, method='average')

    root = to_tree(Z)
    root = clone_graph(root)

    nodes = get_nodes(root)
    id2node = {node.id: node for node in nodes}

    leaf_ids = leaves_list(Z)

    cnt = 0
    i = 0
    total_count = 1

    pool = []

    while True:
        cur_node = id2node[leaf_ids[i]]
        parent_dist = cur_node.parent.dist

        while parent_dist < threshold:
            cur_node = cur_node.parent
            parent_dist = cur_node.parent.dist

        cur_leaf_ids = get_leaves(cur_node)

        pool.append([id for id in cur_leaf_ids])

        total_count += cur_node.count

        i += len(cur_leaf_ids)

        if i >= len(leaf_ids)-1:
            break
        cnt += 1

    clusters = [l for l in pool if len(l) > 1]
    singles = [l[0] for l in pool if len(l) == 1]

    clusters = sorted(clusters, key=lambda x: len(x), reverse=True)

    if return_file_names:

        clusters_fn = []

        for cluster in clusters:

            clusters_fn.append([os.path.basename(loci[i].file_name) for i in cluster])

        singles_fn = [ os.path.basename(loci[i].file_name) for i in singles]

        return singles_fn, clusters_fn

    else:

        return singles, clusters

def make_cdt_file(basename, data, clusters=None, sep_col = True):

    data = data.copy()
    if sep_col:
        prefixes = set(col[:col.find('_sl')] for col in data.columns)
        for prefix in prefixes:
            data[prefix+"_sep"] = pd.Series()
        data = data.sort_index(axis=1)

    data.insert(0, 'GID', 'NONE')
    data.insert(1, 'FBgn', data.index)
    data.insert(2, 'NAME', data.index)
    data.insert(3, 'CHROMOSOME', 'NONE')
    data.insert(4, 'ARM', 'L')
    data.insert(5, 'POSITION', 0)
    data.insert(6, 'GWEIGHT', 1.0)

    for i, row in enumerate(data.index):
        data.ix[row,'GID'] = 'GENE{}X'.format(i)
        data.ix[row, 'FBgn'] = fbgn_lookup.get(row, '???')
        if row in fbgn_map:
            pos = fbgn_map[row].split('..')[0]
            chrom, pos = pos.split(':')
            arm = 'R' if chrom.endswith('R') else 'L'
            if chrom[-1] in 'RL':
                chrom = chrom[:-1]
            data.ix[row, 'CHROMOSOME'] = chrom
            data.ix[row, 'ARM'] = arm
            data.ix[row, 'POSITION'] = int(pos)


    if clusters is not None:
        data = data.ix[hierarchy.leaves_list(clusters)]
    data.to_csv(basename, sep='\t', index=False, float_format='%.5f')

def make_cdt_file(basename, data, clusters=None, sep_col=True):

    data = data.copy()
    if sep_col:
        prefixes = set(col[: col.find("_sl")] for col in data.columns)
        for prefix in prefixes:
            data[prefix + "_sep"] = pd.Series()
        data = data.sort_index(axis=1)

    data.insert(0, "GID", "NONE")
    data.insert(1, "FBgn", data.index)
    data.insert(2, "NAME", data.index)
    data.insert(3, "CHROMOSOME", "NONE")
    data.insert(4, "ARM", "L")
    data.insert(5, "POSITION", 0)
    data.insert(6, "GWEIGHT", 1.0)

    for i, row in enumerate(data.index):
        data.ix[row, "GID"] = "GENE{}X".format(i)
        data.ix[row, "FBgn"] = fbgn_lookup.get(row, "???")
        if row in fbgn_map:
            pos = fbgn_map[row].split("..")[0]
            chrom, pos = pos.split(":")
            arm = "R" if chrom.endswith("R") else "L"
            if chrom[-1] in "RL":
                chrom = chrom[:-1]
            data.ix[row, "CHROMOSOME"] = chrom
            data.ix[row, "ARM"] = arm
            data.ix[row, "POSITION"] = int(pos)

    if clusters is not None:
        data = data.ix[hierarchy.leaves_list(clusters)]
    data.to_csv(basename, sep="\t", index=False, float_format="%.5f")

 def get_factor_reorder(self, c, rotate='oblimin'):
     # reorder factors based on correlation matrix
     phi=get_attr(self.results['factor_tree_Rout_%s' % rotate][c],'Phi')
     if phi is None:
         return list(range(c))
     new_order = list(leaves_list(linkage(squareform(np.round(1-phi,3)))))
     return new_order[::-1] # reversing because it works better for task EFA

def plot_correlations(booklist):
    from mpl_toolkits.axes_grid1 import make_axes_locatable
    fig, ax = plt.subplots(figsize=(20,20))

    books = booklist if len(booklist)>0 else np.unique(np.array(tanach['book']))
    mesh = []
    for b in books:
        wds = words(b)
        gem = gematriaze(wds)
        mesh.append(gem)

    minsize = min(*[len(mesh[i]) for i in range(len(mesh))])
    mesh = [mesh[i][0:minsize] for i in range(len(mesh))]
    meshnum = np.array(mesh)


    plot_matr = np.dot(meshnum, meshnum.T)

    Z = sch.linkage(plot_matr)
    leaves = sch.leaves_list(Z)

    plot_matr = plot_matr[leaves][:,leaves]

    ax.set_yticks(np.arange(len(books))+0.5)
    ax.set_yticklabels(np.array(books)[leaves], fontsize=20)

    ax.set_xticks(np.arange(len(books))+0.5)
    ax.set_xticklabels(np.array(books)[leaves], rotation='vertical',fontsize=20)
    # pc = ax.pcolormesh(nmeshnum,vmin=0, vmax=np.max(meshnum))
    pc = ax.pcolormesh(plot_matr)
    div = make_axes_locatable(ax)
    cax = div.append_axes("right", size="2%", pad=0.05)
    cbar = plt.colorbar(pc, cax=cax)

    fig.tight_layout()

def _get_cluster(components, my_inds=None):
    if my_inds is None:
        my_inds = list(components.keys())
    dist = distance.pdist([components[ind] for ind in my_inds])
    hcomp = hierarchy.complete(dist)
    ll = hierarchy.leaves_list(hcomp)
    return ll

def reorder(C):
    print 'reorder...'
    Y = 1 - C
    Z = linkage(Y, method='average')
    ivl = leaves_list(Z)
    ivl = ivl[::-1]
    return C[:, ivl][ivl, :]

 def cluster_rows(self, method="ward"):
     display_data = self.display_data
     rows = len(display_data)
     if rows < 2:
         # don't attempt to cluster less than 2 rows
         return
     Z = linkage(self.display_data, method)
     self.row_order = leaves_list(Z)

 def hierarchial_cluster(self, method, metric):
     clusters = hierarchy.linkage(self.perc_ids, method=method, metric=metric)
     ordering = hierarchy.leaves_list(clusters)
     self.perc_ids = self.perc_ids[ordering, :]
     self.perc_ids = self.perc_ids[:, ordering]
     self.perc_aln = self.perc_aln[ordering, :]
     self.perc_aln = self.perc_aln[:, ordering]
     self.genomes = self.genomes[ordering]

 def __cluster_columns__(self, column_distance, column_linkage):
     columns = zip(*self.data)
     self.column_clustering = fastcluster.linkage(columns, method=column_linkage, metric=column_distance)
     self.data_order = hcluster.leaves_list(self.column_clustering)
     self.data = self.__reorder_data__(self.data, self.data_order)
     self.original_data = self.__reorder_data__(self.original_data, self.data_order)
     if self.header:
         self.header = self.__reorder_data__([self.header], self.data_order)[0]
     return

def plot_zmatrix(ax, zmatrix):
    from matplotlib import pylab

    lm = hier.linkage(zmatrix)
    ord = np.array(hier.leaves_list(lm))
    
    ax.imshow((zmatrix[ord])[:, ord], interpolation='nearest', 
              cmap=pylab.cm.Greys)
    return ord

def cluster(matrix) : 
    Z = hier.linkage(matrix, method='average')
    
    leaves = hier.leaves_list(Z)

    newmat=matrix[leaves,:]
    newmat=newmat[:,leaves]

    return leaves, newmat

def heatmap_plot_zscore_bigneuron(df_zscore_features, df_all, output_dir, title=None):

    print "heatmap plot:bigneuron"

    #taiwan
    metric ='nt_type'
    mtypes = np.unique(df_all[metric])
    print mtypes
    mtypes_pal = sns.color_palette("hls", len(mtypes))

    mtypes_lut = dict(zip(mtypes, mtypes_pal))
    mtypes_colors = df_all[metric].map(mtypes_lut)



    linkage = hierarchy.linkage(df_zscore_features, method='ward', metric='euclidean')

    data = df_zscore_features.transpose()
    row_linkage = hierarchy.linkage(data, method='ward', metric='euclidean')
    feature_order = hierarchy.leaves_list(row_linkage)

    #print data.index
    matchIndex = [data.index[x] for x in feature_order]
    #print matchIndex
    data = data.reindex(matchIndex)

    pl.figure()
    g = sns.clustermap(data, row_cluster = False, col_linkage=linkage, method='ward', metric='euclidean',
                       linewidths = 0.0,col_colors = [mtypes_colors],
                       cmap = sns.cubehelix_palette(light=1, as_cmap=True),figsize=(40,10))

    pl.setp(g.ax_heatmap.yaxis.get_majorticklabels(), rotation=0)
    pl.setp(g.ax_heatmap.xaxis.get_majorticklabels(), rotation=90)
    #g.ax_heatmap.set_xticklabels([])
    pl.subplots_adjust(left=0.1, bottom=0.1, right=0.9, top=0.95)  # !!!!!

    if title:
        pl.title(title)


    location ="best"
    num_cols=1
    # Legend for row and col colors

    for label in mtypes:
         g.ax_row_dendrogram.bar(0, 0, color=mtypes_lut[label], label=label, linewidth=0.0)
         g.ax_row_dendrogram.legend(loc=location, ncol=num_cols,borderpad=0)

    filename = output_dir + '/zscore_feature_heatmap.png'
    pl.savefig(filename, dpi=300)
    #pl.show()
    print("save zscore matrix heatmap figure to :" + filename)
    pl.close()
    print "done clustering and heatmap plotting"
    return linkage

def matrix_tree(data,color):
    normed_data = data.values

    condition_link = linkage(normed_data)
    feature_link = linkage(normed_data.T)

    condition_order = leaves_list(condition_link)
    feature_order = leaves_list(feature_link)

    conditions = data.index.values[condition_order]
    features = data.columns.values[feature_order]

    color_matrix = normed_data.T[feature_order,:][:,condition_order]
    
    plot_matrix_tree(color_matrix,
                     condition_link,
                     feature_link,
                     conditions,
                     features,
                     color)