This is my implementation of Bitonic Tour (simplification of the Traveling Salesman Problem). Tests are not done very well, but it is not the point.I would be particularly interested in the comments on architecture and performance.NEW VERSIONimport math# see https://en.wikipedia.org/wiki/Bitonic_tour for the statement of the problem# this class contains all distances between verticesclass Vertice(object):    def __init__(self, vertice_coordinates):        self.__vertice_coordinates = vertice_coordinates         # avoid altering input        self.sorted_to_original_absciss_indices = range(len(vertice_coordinates))        self.sorted_to_original_absciss_indices.sort(key = lambda index_:vertice_coordinates[index_][0])        self.original_to_sorted_absciss_indices = range(len(vertice_coordinates))        self.original_to_sorted_absciss_indices.sort(key = lambda index_:self.sorted_to_original_absciss_indices[index_])        # precompute neighbouring distances        self.distances_neighbours = [self.get_distance(self.sorted_to_original_absciss_indices[i],                                                        self.sorted_to_original_absciss_indices[i+1])                                                                         for i in xrange(len(vertice_coordinates)-1)]    def get_distance(self, ind_original_1, ind_original_2):        return math.sqrt((self.__vertice_coordinates[ind_original_1][0] - self.__vertice_coordinates[ind_original_2][0])**2 +                          (self.__vertice_coordinates[ind_original_1][1] - self.__vertice_coordinates[ind_original_2][1])**2)    # given an index in the original array, find next to the right and output it and the distance between the two       def find_next_to_the_right_and_distance(self, ind_original):        ind_sorted = self.original_to_sorted_absciss_indices[ind_original]        ind_original_next = self.sorted_to_original_absciss_indices[ind_sorted + 1]        return self.distances_neighbours[ind_sorted], ind_original_next    def get_first_node_TwoPartialPaths(self):        ind_leftmost = self.sorted_to_original_absciss_indices[0]        return TwoPartialPaths(path_to_rightmost = [ind_leftmost],                                distance_to_rightmost = 0.,                                path_to_another_extreme = [ind_leftmost],                                distance_to_another_extreme = 0.,                               vertice = self)# this class contains information about two partial paths. # For each path, it know the sequence of vertices and total length# It stores an instance of distances to avoid passing it as a parameterclass TwoPartialPaths(object):    def __init__(self, path_to_rightmost, distance_to_rightmost,                        path_to_another_extreme, distance_to_another_extreme, vertice):        self.path_to_rightmost = path_to_rightmost        self.distance_to_rightmost = distance_to_rightmost        self.path_to_another_extreme = path_to_another_extreme        self.distance_to_another_extreme = distance_to_another_extreme        self.vertice = vertice    def __str__(self):        result = path 1 is {}\ndistance 1 is {}\npath 2 is {}\ndistance 2 is {}\noverall distance is {}.\            format(self.path_to_rightmost, self.distance_to_rightmost, self.path_to_another_extreme,                   self.distance_to_another_extreme, self.get_total_distance())        return result    def add_to_rightmost(self):        additional_distance, next_vertex = self.vertice.find_next_to_the_right_and_distance(self.path_to_rightmost[-1])        result = TwoPartialPaths(path_to_rightmost = self.path_to_rightmost + [next_vertex],                                 distance_to_rightmost = self.distance_to_rightmost + additional_distance,                                 path_to_another_extreme = self.path_to_another_extreme,                                 distance_to_another_extreme = self.distance_to_another_extreme,                                 vertice = self.vertice)        return result    def add_to_another(self):        _, next_vertex = self.vertice.find_next_to_the_right_and_distance(self.path_to_rightmost[-1])        another_extreme = self.path_to_another_extreme[-1]        another_distance = self.vertice.get_distance(another_extreme, next_vertex)        result = TwoPartialPaths(path_to_rightmost = self.path_to_another_extreme + [next_vertex],                                 distance_to_rightmost = self.distance_to_another_extreme                                                         + another_distance ,                                 path_to_another_extreme = self.path_to_rightmost,                                 distance_to_another_extreme = self.distance_to_rightmost,                                 vertice = self.vertice)        return result    def add_to_both(self):        additional_distance, next_vertex = self.vertice.find_next_to_the_right_and_distance(self.path_to_rightmost[-1])        another_extreme = self.path_to_another_extreme[-1]        another_distance = self.vertice.get_distance(another_extreme, next_vertex)        result = TwoPartialPaths(path_to_rightmost = self.path_to_another_extreme + [next_vertex],                                 distance_to_rightmost = self.distance_to_another_extreme                                     + another_distance,                                 path_to_another_extreme = self.path_to_rightmost + [next_vertex],                                 distance_to_another_extreme = self.distance_to_rightmost + additional_distance,                                 vertice = self.vertice)        return result    def get_total_distance(self):        return self.distance_to_rightmost + self.distance_to_another_extreme# solve itdef find_bitonic_path(vertice_coordinates):        # initialise the distances    vertice = Vertice(vertice_coordinates = vertice_coordinates)      # initialisation for 2 leftmost vertice    leftmode_vertex_node = vertice.get_first_node_TwoPartialPaths() # only leftmost vertex node    shortest_paths_given_ends = [leftmode_vertex_node.add_to_rightmost()] # add second leftmost            # do other vertice, except the last one    for _ in xrange(len(vertice_coordinates) - 3):        # find the last element, when we add to another extreme        best_last = shortest_paths_given_ends[0].add_to_another()        for pspge in shortest_paths_given_ends[1:]:            challenger = pspge.add_to_another()            if challenger.get_total_distance() < best_last.get_total_distance():                best_last = challenger         # handle simple cases, when we add to the rightmost extreme,        # and the other extreme does not change        shortest_paths_given_ends = [            spge.add_to_rightmost() for spge in shortest_paths_given_ends] + [best_last]    # do the rightmost vertex    result = shortest_paths_given_ends[0].add_to_both()        for spge in shortest_paths_given_ends[1:]:        challenger = spge.add_to_both()        if challenger.get_total_distance() < result.get_total_distance():            result = challenger    return resultif __name__ == '__main__':        vertice_coordinates = [[3,4], [7,0], [10,4], [0,0], [1.5,2]] # [(random.random(), random.random()) for _ in xrange(4)]    for v in vertice_coordinates:        print v    result = find_bitonic_path(vertice_coordinates = vertice_coordinates)    print resultRESPONSE TO SUNNY'S COMMENTSI assume that the code is part of larger library, therefore 1. I do not alter the input because the user does not necessarily expect it 2. I output the results in terms of the input, i.e. number of a point is the same as in the input.I am using dynamic programming. For each point, I compute a set of optimal partial paths that include this point and all points to the left of it. That is, at each iteration I find all optimal subpaths with the end points \$(P_0, P_n), (P_1, P_n), ... (P_{n-1}, P_n)\$ given optimal subpaths with the end points \$(P_0, P_{n-1}), (P_1, P_{n-1}), ... (P_{n-2}, P_{n-1})\$. Finding optimal subpaths \$(P_0, P_n), (P_1, P_n), ... (P_{n-2}, P_n)\$ is trivial: we add edge \$(P_{n-1}, P_n)\$ to \$(P_0, P_{n-1}), (P_1, P_{n-1}), ... (P_{n-2}, P_{n-1})\$. Finding optimal subpaths that end with \$P_{n-1}\$ and \$P_{n}\$ is slightly trickier, as you add an edge to another extreme, so you need to compare \$(P_0, P_{n-1}) + (P_0,P_n), (P_1, P_{n-1}) + (P_1,P_n), ... (P_{n-2}, P_{n-1}) + (P_{n-2},P_n)\$ to find the shortest \$(P_{n-1},P_n)\$. distance_to_rightmost and distance_to_another_extremum correspond, more or less, to the lengths of top subpath and bottom subpath, because, ultimately, each subpath goes towards the rightmost point. More exact name for the first distance will be distance_to_rightmost_point_included_so_far, but it is I think it is too long.adding result variable is terribly helpful when you debug, I believe it is a common practiceI called a class Vertice because it contains all points (vertice) as opposed to just one point (vertex).I agree that nested calls are not good, I will change that!ORIGINAL VERSIONimport math# see https://en.wikipedia.org/wiki/Bitonic_tour for the statement of the problem# this class contains all distances between verticesclass Distances:    def __init__(self, vertice):         # avoid altering input        sorted_indices = range(len(vertice))        sorted_indices.sort(key = lambda index_:vertice[index_][0])        self.__distances = [[math.sqrt((vertice[i][0]-vertice[j][0])**2 + (vertice[i][1]-vertice[j][1])**2)                                                for i in sorted_indices] for j in sorted_indices]    def get_(self, vertice_1, vertice_2):        return self.__distances[vertice_1][vertice_2]# this class contains information about two partial paths. # For each path, it know the sequence of vertices and total length# It stores an instance of distances to avoid passing it as a parameterclass TwoPartialPaths:    def __init__(self, path_to_rightmost, distance_to_rightmost,                        path_to_another_extreme, distance_to_another_extreme, distances):        self.path_to_rightmost = path_to_rightmost        self.distance_to_rightmost = distance_to_rightmost        self.path_to_another_extreme = path_to_another_extreme        self.distance_to_another_extreme = distance_to_another_extreme        self.distances = distances    def print_out(self):        print path 1 is, self.path_to_rightmost        print distance 1 is, self.distance_to_rightmost        print path 2 is, self.path_to_another_extreme        print distance 2 is, self.distance_to_another_extreme        print overall distance, self.get_total_distance()    def add_to_rightmost(self):        new_vertex = self.path_to_rightmost[-1] + 1        result = TwoPartialPaths(path_to_rightmost = self.path_to_rightmost + [new_vertex],                                 distance_to_rightmost = self.distance_to_rightmost                                                         + self.distances.get_(new_vertex, new_vertex-1),                                 path_to_another_extreme = self.path_to_another_extreme,                                 distance_to_another_extreme = self.distance_to_another_extreme,                                 distances = self.distances)        return result    def add_to_another(self):        new_vertex = self.path_to_rightmost[-1] + 1        another_extreme = self.path_to_another_extreme[-1]        result = TwoPartialPaths(path_to_rightmost = self.path_to_another_extreme + [new_vertex],                                 distance_to_rightmost = self.distance_to_another_extreme                                                         + self.distances.get_(new_vertex, another_extreme),                                 path_to_another_extreme = self.path_to_rightmost,                                 distance_to_another_extreme = self.distance_to_rightmost,                                 distances = self.distances)        return result    def add_to_both(self):        new_vertex = self.path_to_rightmost[-1] + 1        another_extreme = self.path_to_another_extreme[-1]        result = TwoPartialPaths(path_to_rightmost = self.path_to_another_extreme + [new_vertex],                                 distance_to_rightmost = self.distance_to_another_extreme                                     + self.distances.get_(new_vertex, another_extreme),                                 path_to_another_extreme = self.path_to_rightmost + [new_vertex],                                 distance_to_another_extreme = self.distance_to_rightmost                                     + self.distances.get_(new_vertex, new_vertex-1),                                 distances = self.distances)        return result    def get_total_distance(self):        return self.distance_to_rightmost + self.distance_to_another_extreme# solve itdef find_bitonic_path(vertice):        # initialise the distances    distances = Distances(vertice = vertice)      # initialisation for 2 leftmost vertice    shortest_paths_given_ends = [TwoPartialPaths(path_to_rightmost = [0, 1],                                                  distance_to_rightmost = distances.get_(1, 0),                                                  path_to_another_extreme = [0],                                                  distance_to_another_extreme = 0.,                                                 distances = distances)]             # do other vertice, except the last one    for _ in xrange(len(vertice) - 3):        # find the last element, when we add to another extreme        best_last = shortest_paths_given_ends[0].add_to_another()        for pspge in shortest_paths_given_ends[1:]:            challenger = pspge.add_to_another()            if challenger.get_total_distance() < best_last.get_total_distance():                best_last = challenger         # handle simple cases, when we add to the rightmost extreme,        # and the other extreme does not change        shortest_paths_given_ends = [            spge.add_to_rightmost() for spge in shortest_paths_given_ends] + [best_last]    # do the rightmost vertex    result = shortest_paths_given_ends[0].add_to_both()        for spge in shortest_paths_given_ends[1:]:        challenger = spge.add_to_both()        if challenger.get_total_distance() < result.get_total_distance():            result = challenger    return resultif __name__ == '__main__':        vertice = [[0,0], [3,4], [7,0], [10,4]] # [(random.random(), random.random()) for _ in xrange(4)]    for v in vertice:        print v    result = find_bitonic_path(vertice = vertice)    result.print_out()
Bitonic Tour algorithm
python;graph;traveling salesman