Bitonic Tour algorithm

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 VERSION

```
import math
# see https://en.wikipedia.org/wiki/Bitonic_tour for the statement of the problem

# this class contains all distances between vertices
class 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_n

The print_out function in your class TwoPartialPaths should be changed to a magic method, in this case, __str__. Here's how you could do that:

def __str__(self):
    return (
        "path 1 is " + self.path_to_rightmost +
        "\ndistance 1 is " + self.distance_to_rightmost +
        "\npath 2 is " + self.path_to_another_extreme +
        "\ndistance 2 is " + self.distance_to_another_extreme +
        "\noverall distance " + self.get_total_distance()
    )

We can make this method much better though. Rather than using string concatenation, we can use the str.format method. We can also get rid of those extra +'es at the end of each line as well, using implicit concatenation. Using str.format, and implicit concatenation, TwoPartialPaths.__str__ becomes this:

def __str__(self):
    return (
        "path 1 is {}".format(self.path_to_rightmost)
        "\ndistance 1 is {}".format(self.distance_to_rightmost)
        "\npath 2 is {}".format(self.path_to_another_extreme)
        "\ndistance 2 is {}".format(self.distance_to_another_extreme)
        "\noverall distance {}".format(self.get_total_distance())
    )

But that's not all, we can shorten this two one line, by combining all of these str.formats into one, and formatting one long string.

def __str__(self):
    return "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()
    )

After doing all this, all you have to do to output data about a TwoPartialPaths class instance is this:

tpp = TwoPartialPaths( ... )
print tpp

In any version of Python 2.x, when you create classes, you need to have them explicitly inherit from object, like this:

class MyClass(object):
    ...

If you're using Python 3.x or higher, you can just type them like this:

class MyClass:
    ...

Finally, I'm noticing that you're missing whitespace in a few areas. For example, this:

(vertice[i][0]-vertice[j][0])**2 + (vertice[i][1]-vertice[j][1])**2

Should be expanded to this:

(vertice[i][0] - vertice[j][0]) ** 2 + (vertice[i][1] - vertice[j][1]) ** 2

Adding whitespace around operators generally increases the readability of your code, and if it voilates the 80 characters per line limit, you can always use the line break character, \, to continue the line's contents on a separate line.

StackExchange Code Review Q#97511, answer score: 4