6
\$\begingroup\$

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_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 parameter
class 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 it
def 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 result

if __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 result

RESPONSE TO SUNNY'S COMMENTS

  • I 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 practice
  • I 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 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 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 parameter
class 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 it
def 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 result

if __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()
\$\endgroup\$
  • \$\begingroup\$ Perhaps I missed it, but I am surprised you did not implement lazy loading for your distances matrix. Relatedly, this class might be best as a singleton class to make good and sure you don't compute those distances extra times. \$\endgroup\$ – sunny Jul 20 '15 at 23:03
  • \$\begingroup\$ @sunny: I guess potentially one might want to have several different sets of distances for other applications, this is why I avoided having it as a static field; I guess this is also the reason why singleton should be avoided. Would you agree? \$\endgroup\$ – Yulia V Jul 20 '15 at 23:06
  • \$\begingroup\$ @sunny: no lazy evaluation, but, since each edge is studies only one time, I do not need to store it. Good point! \$\endgroup\$ – Yulia V Jul 20 '15 at 23:16
  • 1
    \$\begingroup\$ Cool beans. I'm going to look at this some more tmw b/c I'd like to learn more about this algorithm. Hope you get some good answers. \$\endgroup\$ – sunny Jul 21 '15 at 0:09
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks! I believe format() takes arbitrary number of arguments, so it is possible to call it only once, with 5 arguments, this makes the code shorter. \$\endgroup\$ – Yulia V Jul 20 '15 at 22:38
  • \$\begingroup\$ @YuliaV Hmm, good point. Let me see what I can do. \$\endgroup\$ – Ethan Bierlein Jul 20 '15 at 22:39
  • \$\begingroup\$ "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()) \$\endgroup\$ – Yulia V Jul 20 '15 at 22:40
  • \$\begingroup\$ @YuliaV Added into answer. \$\endgroup\$ – Ethan Bierlein Jul 20 '15 at 22:42
  • \$\begingroup\$ As someone still learning python, this new string format thing has me puzzled. Python is supposed to emphasize readability, but to my eyes the string concatenation with + is far more readable than all this {} and format business. Plus many python tutorials (e.g. codecademy) still introduce string concetenation early. I'm not doubting that format is better -- it's probably mentioned in >50% of all python posts on CR.SE -- but where is a good introduction to why? \$\endgroup\$ – Curt F. Jul 20 '15 at 22:59
2
\$\begingroup\$

I looked over your newer code. I have not implemented the bitonic algorithm myself, so apologies in advance if anything below is based on a misunderstanding of the algo or of your code. Thanks for showing me this new algo.

Structure

  • Why don't you just start with a sorted list of points? Your code is tricky to read because you are often going back and forth between the sorted and unsorted list of points, even though so far as I understand from the algorithm, the unsorted version is irrelevant.
  • Why aren't you using dynamic programming (or did I miss it)? This problem is known to lend itself to dynamic programming, but I don't see it used in your code. For example, in TwoPartialPaths.add_to_another why don't you memo-ize the result of self.vertice.get_distance(another_extreme, next_vertex)? Are you sure you won't be calling that function on that exact same set of values again?

Tricky Names

  • Your variable names are often far longer than they need to be without adding clarity. For example, instead of distance_to_rightmost and distance_to_another_extremum why not use right_path and left_path? From what I read up on this algorithm, most people seem to talk about them as the right and left directional paths, or call them path_top and path_bottom if you're visualizing a 2d layout. What I'm saying is your longer names don't add clarity.

  • You are inconsistent about creating local variables in your functions for single use. I would recommend, for example, in Vertice.__init__ naming a variable for len(vertice_coordinates) rather than calling this function 3 times, as you do. On the other hand, I wonder whether you need to have a result variable in the following TwoPartialPaths member functions: add_to_righmost, add_to_another, and add_to_both. Why not just return the result of the functional call directly? The result variable doesn't enhance readability.

  • Why Vertice as a class name instead of vertex? This was confusing and a bit wordier than necessary.

Program Consistency

  • You call self.vertice.get_distance(another_extreme, next_vertex) within add_to_another but I didn't notice any other instances of nested function calls. I have no problem with nested function calls, but since you only do it once, interspersed with lots of very long parameter names, this is easy for a reader to miss. I would move this to a local variable in the function and then just pass the local variable, in the interests of readability and consistency of style within your program.
\$\endgroup\$
  • \$\begingroup\$ thank you, I have added comments to your comments to my question! \$\endgroup\$ – Yulia V Jul 23 '15 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.