``` import sys import matplotlib.pyplot as plt import numpy as np import networkx as nx import math import concavehull as cv from scipy.spatial import Delaunay from scipy.spatial import ConvexHull from itertools import product
numbed_of_point = 0 # The number of point threshold = 0 # Threshold value ( vertex to cycle ) point_list = [] # Point [ [x1, y1], [x2, y2], …] list cycle_vertex_list = [] # Cycle vertex [ v1, v2, .. ] list cycle_length = 1000 * 1000 # The Length of Cycle center= 0 # center of the cycle final_center = 0
city_f = open(‘city-100.txt’,’r’) cycle_f = open(‘citycycle-100.txt’,’w’)
def getDistance(first_vertex, second_vertex): tmp1, tmp2 = point_list[first_vertex], point_list[second_vertex] x_diff , y_diff = tmp2[0] - tmp1[0] , tmp2[1] - tmp1[1] return round(math.sqrt(x_diff2+y_diff2),3)
def get_vertex_num(tpoint): for iter_i in range(len(point_list)): if point_list[iter_i] == tpoint: return iter_i
def get_cycle_length(cycle_list_parameter): cycle_lens = 0 for cycle_list_iter in range(len(cycle_list_parameter) - 1): tmp_start, tmp_end = cycle_list_parameter[cycle_list_iter], cycle_list_parameter[cycle_list_iter + 1] cycle_lens += edgeLengthList[tmp_start - 1][tmp_end - 1] cycle_lens = round(cycle_lens, 3) return cycle_lens
def get_inserted_concave(target_value, concave_vertex_parameter, cycle_make_from_to_parameter): local_temp_cycle_candidate = [] for count_index in range(len(concave_vertex_parameter)): temp_concave_vertex_list = concave_vertex_parameter.copy() temp_concave_vertex_list.insert(count_index,target_value) temporary_cycle, temporary_vertex = create_cycle_from_concave(temp_concave_vertex_list) temporary_cycle = remove_duplicated_vertex(temporary_cycle, temporary_vertex) temporary_cycle = optimize_concaved_cycle(temporary_cycle, temp_concave_vertex_list, cycle_make_from_to_parameter) temporary_cycle.append(temporary_cycle[0]) temp_cycle_length = get_cycle_length(temporary_cycle) if temporary_cycle[0] == temporary_cycle[-1] and len(temporary_cycle[1:]) == len(set(temporary_cycle[1:])): local_temp_cycle_candidate.append([temp_concave_vertex_list,temporary_cycle, temp_cycle_length]) if len(local_temp_cycle_candidate) != 0: tmp_result_list = sorted(local_temp_cycle_candidate, key=lambda x: x[2])[0] return_concave = [] for cycle_it in tmp_result_list[1]: if cycle_it in tmp_result_list[0]: return_concave.append(cycle_it) tmp_result_list[0] = return_concave return tmp_result_list return 0
def create_cycle_from_concave(concave_parameter): new_cycle_list = [] new_vertex_check_list = [0 for i in range(numbed_of_point)] for concave_iter in range(len(concave_parameter)-1): concave_start, concave_end = concave_parameter[concave_iter], concave_parameter[concave_iter+1] shortest_path_list = nx.shortest_path(Graph, concave_start, concave_end, weight=’weight’) for shortest_path_iter in range(len(shortest_path_list)-1): new_cycle_list.append(shortest_path_list[shortest_path_iter]) new_vertex_check_list[shortest_path_list[shortest_path_iter]-1] += 1
concave_start = concave_parameter[-1] # center가 마지막 concave에 포함되는 경우 추가해줘야 함
concave_end = concave_parameter[0]
if concave_start != concave_end:
shortest_path_list = nx.shortest_path(Graph, concave_start, concave_end, weight='weight')
for shortest_path_iter in range(len(shortest_path_list) - 1):
new_cycle_list.append(shortest_path_list[shortest_path_iter])
new_vertex_check_list[shortest_path_list[shortest_path_iter] - 1] += 1
return new_cycle_list, new_vertex_check_list
def remove_duplicated_vertex(cycle_list_parameter, vertex_check_list_parameter): for vertex_check_iter in range(len(vertex_check_list_parameter)): compare_path = [] if vertex_check_list_parameter[vertex_check_iter] == 2: for c_ind in range(len(cycle_list_parameter)): if vertex_check_iter + 1 == cycle_list_parameter[c_ind]: cycle_start = cycle_list_parameter[c_ind - 1] cycle_end = cycle_list_parameter[c_ind + 1] if c_ind != len(cycle_list_parameter) - 1 else cycle_list_parameter[0] compare_path.append([cycle_start, cycle_end, c_ind])
if (compare_path[0][1] == compare_path[1][0] and compare_path[0][1] == vertex_check_iter + 1) or \
(compare_path[0][0] == compare_path[1][1] and compare_path[0][0] == vertex_check_iter + 1):
del cycle_list_parameter[compare_path[0][2]]
else:
test = Graph.copy()
remove_vertex = vertex_check_iter+1
test.remove_node(remove_vertex)
if remove_vertex != compare_path[0][0] and remove_vertex != compare_path[0][1] and \
remove_vertex != compare_path[1][0] and remove_vertex != compare_path[1][1]:
first_flag = nx.has_path(test, compare_path[0][0], compare_path[0][1])
second_flag = nx.has_path(test, compare_path[1][0], compare_path[1][1])
if first_flag == False and second_flag == False:
del cycle_list_parameter[compare_path[0][2]]
else:
removed_index = -1
if first_flag == True and second_flag == True:
first_shortest = nx.shortest_path_length(test, compare_path[0][0], compare_path[0][1],weight='weight')
second_shortest = nx.shortest_path_length(test, compare_path[1][0], compare_path[1][1], weight='weight')
removed_index = 0 if first_shortest < second_shortest else 1
elif first_flag:
removed_index = 0
else:
removed_index = 1
remove_path = nx.shortest_path(test, compare_path[removed_index][0], compare_path[removed_index][1], weight='weight')
remove_list = []
for remove_path_iter in range(1, len(remove_path) - 1):
remove_list.append(remove_path[remove_path_iter])
insert_index = compare_path[removed_index][2]
del cycle_list_parameter[insert_index]
for remove_list_iter in remove_list:
cycle_list_parameter.insert(insert_index, remove_list_iter)
insert_index += 1
return cycle_list_parameter
def optimize_concaved_cycle(cycle_list_parameter, concave_vertex_parameter, cycle_make_from_to_parameter): # 최적화 가능한 concave_vertex 제거 remove_list = [] for concave_iter in concave_vertex_parameter: checklist = [] for cycle_make_from_iter in cycle_make_from_to_parameter: if cycle_make_from_iter[1] == concave_iter: checklist.append(cycle_make_from_iter) if concave_iter in cycle_list_parameter: concave_index = cycle_list_parameter.index(concave_iter) for cycle_make_iter in cycle_make_from_to_parameter: vertex_from, vertex_to = cycle_make_iter[0], cycle_make_iter[1] if vertex_to == concave_iter: temp_cycle_list = list(set(cycle_list_parameter) - set([concave_iter])) for cycle_it in temp_cycle_list: left = len(cycle_list_parameter)-1 if concave_index == 0 else concave_index - 1 right = 0 if concave_index == len(cycle_list_parameter)-1 else concave_index + 1 compare = [vertex_from, concave_iter] if threshold > edgeLengthList[vertex_from - 1][cycle_it - 1] and Graph.has_edge(cycle_list_parameter[left], cycle_list_parameter[right]): if compare in checklist: checklist.remove([vertex_from, concave_iter]) if len(checklist) == 0: remove_list.append(concave_iter) break remove_list = list(set(remove_list)) for remove_list_iter in remove_list: cycle_list_parameter.remove(remove_list_iter) concave_vertex_parameter.remove(remove_list_iter) return cycle_list_parameter
def is_all_vertex_in_threshold(cycle_parameter): threshold_result = True for i in range(1, len(point_list) + 1): if i in cycle_parameter: continue else: minimum_dist = 1000 * 1000 for j in cycle_parameter: current_dist = nx.shortest_path_length(Graph,i,j,weight=’weight’) if current_dist < minimum_dist: minimum_dist = current_dist if minimum_dist > threshold: threshold_result = False break return threshold_result
def get_optimal_cycle(cycle_parameter):
tmp_cycle_parameter = cycle_parameter.copy()
for cycle_rm_it in range(1, len(tmp_cycle_parameter)):
is_removed = False
neighbor_flag = False
if cycle_rm_it == len(tmp_cycle_parameter)-1 or cycle_rm_it == len(tmp_cycle_parameter):
neighbor_flag = Graph.has_edge(tmp_cycle_parameter[cycle_rm_it -1], tmp_cycle_parameter[1])
if neighbor_flag:
del tmp_cycle_parameter[0] # 처음 끝 제거
del tmp_cycle_parameter[-1]
tmp_cycle_parameter.append(tmp_cycle_parameter[0]) # 마지막 꺼 추가
is_removed = True
break
else:
neighbor_flag = Graph.has_edge(tmp_cycle_parameter[cycle_rm_it + 1], tmp_cycle_parameter[cycle_rm_it - 1])
if neighbor_flag:
del tmp_cycle_parameter[cycle_rm_it]
is_removed = True
if is_removed:
if is_all_vertex_in_threshold(tmp_cycle_parameter):
cycle_parameter = tmp_cycle_parameter.copy()
else:
tmp_cycle_parameter = cycle_parameter.copy()
return cycle_parameter
Suffix Array(접미사 배열)은 어떤 문자열의 suffix(접미사)들을 사전순으로 나열한 배열을 의미한다. 특정문자열에서 반복적으로 나타나는 부분문자열을 찾는 문제에 자주 쓰이는 방법이다. 예를들어 문자열 ATTCTCG가 있을경우 접미사 배열은 다음과 같이 만들어 진다. 그림을 보면 문자열 앞에서부터 한칸씩 나가면서 문자열을 잘라낸다. 그리고 이렇게 잘라낸 문자열을 정렬하고 난 뒤 LCP(Longest Common Prefix) 를 구하면 된다. LCP[i]의 값은 Suffix Array에서 i번째 접미사와 i-1번째 접미사의 가장 긴 공통 접두사의 길이이다. 여기서 LCP의 값이 가장 큰 것이 바로 해당 문자열에서 가장 긴 반복 부분문자열의 길이이다.