# -*- coding: utf-8 -*-

 """

 Created on Mon Dec  4 15:04:39 2017

 @author: zxzhu

 python3.6

 """

 from functools import reduce

 def get_weight(s1,s2):              #通过两条序列的overlap计算出权值

     l = min(len(s1),len(s2))

     while l>0:

         if s2[:l] == s1[-l:]:

             return l

         else:

             l-=1

     return 0

 def print_result(s1,s2):           #将两条序列去除首尾overlap后合并

     weight = get_weight(s1,s2)

     s = s1 + s2[weight:]

     #print(s)

     return s

 def dir_graph(l,t=3):             #得到满足条件的有向图(权值大于等于t)

     graph = {}

     for i in l:

         for j in l:

             if i!=j:

                 weight = get_weight(i,j)

                 if weight >= t:

                     key = (i,j)

                     graph[key] = weight

     return graph

 def rm_path(graph,path):           #贪婪算法加入一条边后应该去除与该边首尾顶点相同的边

     key = graph.keys()

     rm_key = []

     for i in key:

         if i[1] == path[1] or i[0] == path[0]:

             rm_key.append(i)

     for i in rm_key:

         graph.pop(i)

     return graph

 def get_path(graph,path = []):     #得到满足条件的所有边

     while graph:

         max_weight = 0

         for i in graph.keys():

             if graph[i] > max_weight:

                 max_weight = graph[i]

                 cur_path = i

         path.append(cur_path)

         graph = rm_path(graph,cur_path)

         get_path(graph,path)

     return path

 def out_num(path,V):             #计算某顶点的出度

     count = 0

     for i in path:

         if i[0] == V:

             count+=1

     return count

 def get_last_V(path,last_V = None):           #得到最后一条边

     index = 0

     if last_V:                                #非随机寻找出度为0的顶点

         for i in path:

             if i[1] == last_V:

                 return i,index

             else:

                 index+=1

         return None                           #没有找到指向last_V的顶点(一条路径结束)

     else:                                     #随机寻找出度为0的顶点

         for i in path:

             if out_num(path,i[1]) == 0:

                 return i,index

             else:

                 index+=1

         return -1                             #首尾相连

 def assemble(cur_V,path,new_path = []):       #给满足条件的边排序

     while path:

         path.pop(cur_V[1])

         new_path.insert(0,cur_V[0])

         cur_V = get_last_V(path,last_V = cur_V[0][0])

         if cur_V:

             assemble(cur_V,path,new_path)

         else:

             cur_V = get_last_V(path)

             assemble(cur_V,path,new_path)

     return new_path

 def align_isolated(path,sequence):          #加入孤立顶点

     new_path = reduce(lambda x,y:x+y,path)

     for i in sequence:

         if i not in new_path:

             new_path.append(i)

     return new_path

 x = 'CCTTTTGG'

 y = 'TTGGCAATCACT'

 w = 'AGTATTGGCAATC'

 u = 'ATGCAAACCT'

 z = 'AATCGATG'

 v = 'TCACTCCTTTT'

 a = w

 b = y

 c = 'TCACTAGTA'

 sequence = [x,y,w,u,z]

 sequence1 = [a,b,c]

 graph = dir_graph(sequence1,t=3)

 print(graph)

 path = get_path(graph)

 path = [list(i) for i in path]              #将path中的tuple元素换成list

 #print(path)

 start = get_last_V(path)                    #起始出度为0的顶点所在的边

 if start == -1:                             #序列首尾相连

     new_path = reduce(lambda x,y:x+y, path)

     new_path = new_path[:-1]

     result = reduce(print_result,new_path)

 else:

     new_path = assemble(start,path)             #排序后的边

     new_path = align_isolated(new_path,sequence1)   #加入孤立顶点

     #print(new_path)

     result = reduce(print_result,new_path)      #组装

 #print(new_path)

 print(result)