Faulty conditional check in nearest neighbor calculation?

Question

I'm trying to write a function to calculate an approximate traveling salesman route through a list of cities using the nearest neighbor algorithm, starting from the first city listed. However, each time I run it I get IndexError: list index out of range.

In debugging the error, I found that the value of index stays the same from one loop iteration to the next, rather than changing. When it's time to append, the code checks the if not in condition; since it's False, it adds 1 to i and moves to the next iteration of the loop. Once it reaches a higher number than exists in the array, it gives me the error.

So my problem is, why does execution not enter the first if not in block? It seems like the code ignores it.

For my actual problem I'm reading in a file of 317 cities, each of which has an index and two coordinates. Here's a shorter sample list of cities for testing:

Nodelist = [
    (1, 63, 71),
    (2, 94, 71),
    (3, 142, 370),
    (4, 173, 1276),
    (5, 205, 1213),
    (6, 213, 69),
    (7, 244, 69),
    (8, 276, 630),
    (9, 283, 732),
    (10, 362, 69),
]

Here is the function's code:

def Nearest(Nodelist,Distance,index):
    Time_Calculation = time.time()
    Newarray=[]
    Newarray.append(Nodelist[0])
    for i in range(0,len(Nodelist)):
        for j in range(1,len(Nodelist)):
            if (Nodelist[j] not in Newarray):
                DisEquation = math.sqrt(pow(Nodelist[j][1]-Newarray[i][1],2)+pow(Nodelist[j][2]-Newarray[i][2],2))
                if Distance==0:
                    Distance=DisEquation
                if Distance > DisEquation:
                    index=j
                    Distance=DisEquation
        if(Nodelist[index] not in Newarray):
            Newarray.append(Nodelist[index])
        Distance=0
    print (time.time() - Time_Calculation)
    return Newarray

Code that calls it:

NearestMethodArr=Nearest(Cities,b,index)
print(NearestMethodArr)
print(len(NearestMethodArr))

The print statements should produce:

[(1, 63, 71), (2, 94, 71), (6, 213, 69), (7, 244, 69), (10, 362, 69), (3, 142, 370), (8, 276, 630), (9, 283, 732), (5, 205, 1213), (4, 173, 1276)]
10

Answer 1

Newarray.append(Nodelist[0])#adding Nodelist[0] to NewArray    
for i in range(0,len(Nodelist)):
        for j in range(1,len(Nodelist)):
            if (Nodelist[j] not in Newarray):
                DisEquation = math.sqrt(pow(Nodelist[j][1]-Newarray[i [1],2)+pow(Nodelist[j][2]-Newarray[i][2],2)) #you access Newarray at i
                if Distance==0:
                    Distance=DisEquation
                if Distance > DisEquation:
                    index=j
                    Distance=DisEquation
        if(Nodelist[index] not in Newarray):
            Newarray.append(Nodelist[index])#you conditionally add new elements to newarray

If you see the comments I added to your code the issues should be clear. You loop over all the elements of Nodelist and call the index i you've already added one element to NewArray so the first time index 0 exists. Then you hit the Nodelist[index] not in Newarray, if it is true NewArray gets bigger by 1 and then NewArray[1] works if this is ever not true for any reason then NewArray stays the same size and the next NewArray[i] will be an index out of range error.

Edit: thanks to CrazyChucky for setting me straight in the comments. I've adjusted below

My comment about the failure was correct though I hadn't identified the root cause which was not setting index as the author identified. I didn't parse the code correctly in my head. The code in the updated version works though it would be faster and easier to read if you did something like:

def new_nearest(Nodelist):
    start_time = time.time()
    shortest_path = [Nodelist[0]]
    Nodelist = Nodelist[1:]
    while len(Nodelist) > 0:
        shortest_dist_sqr = -1
        next_node = None
        for potential_dest in Nodelist:
            dist_sqr = (shortest_path[-1][1] - potential_dest[1])**2 + (shortest_path[-1][2] - potential_dest[2])**2 #you don't keep the distances so there is no need to sqrt as if a > b then a**2 > b**2
            if shortest_dist_sqr < 0 or dist_sqr < shortest_dist_sqr:
                next_node = potential_dest
                shortest_dist_sqr = dist_sqr
        shortest_path.append(next_node)
        Nodelist.remove(next_node)
    print(time.time() - start_time)
    return shortest_path

This returns identical results but executes faster. changing to an approach where you remove nodes from the inner loop makes it clearer what's going on, it might make the code a bit slower (it would in C but python has a lot of overhead in various places that may make this a net gain,) and because there is no need to calculate the actual distance since you don't store it you can compare the distance squared and not do any square roots. If you do want the distance you can just square root the nearest node after you've determined which it is.

Edit: I couldn't help but check. The move to removing nodes from Nodelist actually represents the majority of the time savings while the lack of a sqrt does reliably speed things up (I used timeit and varied the code.) In a lower level language doing tiny things is ultra fast so it's likely faster to leave the array alone and just skip over elements that are already used (this might not actually be true because it will mess with branch prediction performance analysis is really hard and will depend on what processor architecture you're using...) In python though even small things are very expensive (add two variables: figure out what types they are, decode variable byte length ints, do add, create new object for result...) so even though removing a value from a list may be more expensive than skipping values and leaving the list alone it will lead to more small operations that are very slow in Python. If a low level language was in use you could also recognise that the order of the nodes is arbitrary (except for which one is first,) so you can just have an array with all the nodes and instead of making a new small array you track the length of the values used in the array and copy the last value in the array over the value that is selected for the next node in the path.

Edit yet again :P : Again I couldn't help but be curious. The approach to overwriting part of the nodelist instead of removing entries had me wondering as to if it would be faster in python as it does create more work that is slow in python but decreases the amount of work involved in removing node elements. Turns out that this approach is a noticeable (though not very significant a little less than 2% but consistent in micro benchmarks) speedup even in python so the below code is even faster:

def newer_nearest(Nodelist):
    shortest_path = [Nodelist[0]]
    Nodelist = Nodelist[1:]
    while len(Nodelist) > 0:
        shortest_dist_sqr = -1
        next_node = None
        for index, potential_dest in enumerate(Nodelist):
            dist_sqr = (shortest_path[-1][1] - potential_dest[1])**2 + (shortest_path[-1][2] - potential_dest[2])**2 #you don't keep the distances so there is no need to sqrt as if a > b then a**2 > b**2
            if shortest_dist_sqr < 0 or dist_sqr < shortest_dist_sqr:
                next_node = index
                shortest_dist_sqr = dist_sqr
        shortest_path.append(Nodelist[next_node])
        Nodelist[next_node] = Nodelist[-1]
        Nodelist = Nodelist[:-1]
    return shortest_path

Answer 2

David Oldford's answer beat me to the punch for most functional improvements, but I wanted to touch on several specific things that can make your code cleaner and more Pythonic. Readability counts.

The main improvements below:

• There is rarely, if ever, a need to use for i in range(len(sequence)) in Python. Doing so goes against the spirit of how Python for loops are designed. If you need an index, use for i, element in enumerate(sequence). (When you don't need the index, simply use for element in sequence.)
• Give your variables names that are clear (they say what they are) and consistently formatted (ideally snake_case, but if you prefer camelCase or some other format, choose one and stick with it). This will not only help others reading your code; it will help you when you come back a month later and don't remember why you wrote what you did.
• Break up long lines; put spaces around assignment (=) and comparison (e.g. ==), and after commas; use blank lines (sparingly) to separate chunks of code for better readability.
• In Python you can create infinity with float('inf') (or negative infinity with -float('inf'). This is the idiomatic way to make comparisons to find the smallest or largest of something.
• Your function operates on the list of nodes/cities. It doesn't make sense to supply a distance or index as an argument to the function.
• Multiple assignment is often a good way to make code much clearer by assigning descriptive names to indices. It's much easier to read (x2 - x1)**2 + (y2 - y1)**2 and understand what it's doing, compared to pow(Nodelist[j][1]-Newarray[i][1],2)+pow(Nodelist[j][2]-Newarray[i][2],2).
• I wouldn't include quite so many comments in my own code, were it not intended for a post like this. But some comments explaining control flow can be very helpful.

import time

def nearest_neighbor_path(cities):
    """Find traveling salesman path via nearest neighbor algorithm."""
    start_time = time.time()

    # Start at the first city, and maintain a list of unvisited cities.
    path = [cities[0]]
    remaining_cities = cities[1:]

    # Loop until every city has been visited. (An empty list evaluates
    # to False.)
    while remaining_cities:
        # In each loop, set starting coordinates to those of the current
        # city, and initialize shortest distance to infinity.
        _, x1, y1 = path[-1]
        shortest_so_far = float('inf')
        nearest_city = None

        # Investigate each possible city to visit next.
        for index, other_city in enumerate(remaining_cities):
            # Since we don't need the *actual* distance, only a
            # comparison, there's no need to take the square root.
            # (Credit to David Oldford, good catch!)
            _, x2, y2 = other_city
            distance_squared = (x2 - x1)**2 + (y2 - y1)**2

            # If it's the closest one we've seen so far, record it.
            if distance_squared < shortest_so_far:
                shortest_so_far = distance_squared
                index_of_nearest, nearest_city = index, other_city

        # After checking all possible destinations, add the nearest one
        # to the path...
        path.append(nearest_city)
        # ...and remove it from the list of remaining cities. This could
        # simply be remaining_cities.remove(nearest_city), in which case
        # we wouldn't need the index or enumerate() at all. But doing it
        # this way saves an extra iteration to find the city again in
        # the list.
        remaining_cities.pop(index_of_nearest)
    
    print(f'Elapsed time: {time.time() - start_time :f} seconds')
    return path

If you don't mind importing NumPy for its argmin function, the while loop could be further streamlined like so:

import numpy as np
import time

def nearest_neighbor_path(cities):
    """Find traveling salesman path via nearest neighbor algorithm."""
    start_time = time.time()
    path = [cities[0]]
    remaining_cities = cities[1:]

    while remaining_cities:
        _, x1, y1 = path[-1]
        distances = [(x2 - x1)**2 + (y2 - y1)**2
                     for _, x2, y2 in remaining_cities]
        index_of_nearest = np.argmin(distances)
        
        nearest_city = remaining_cities.pop(index_of_nearest)
        path.append(nearest_city)
    
    print(f'Elapsed time: {time.time() - start_time :f} seconds')
    return path

I'd also recommend taking a look at PEP 8, the official Python style guide. It's a very good set of guidelines for keeping Python code clear and readable. The easier your code is to read, the easier it is for you to identify problems and solutions.

Answer 3

I find out what was the problem with my code, when I reassigned the Distance to x I forgot that I need to reassign the index with it because the first city that got tested was had the shortest distance and In my first code I reassigned the variable index only when x is < than the Distance

new code:

def Nearest(Nodelist,Distance,index):
    Time_Calculation = time.time()
    Newarray=[]
    Newarray.append(Nodelist[0])
    for i in range(0,len(Nodelist)):
        for j in range(1,len(Nodelist)):
            if (Nodelist[j] not in Newarray):
                DisEquation = math.sqrt(pow(Nodelist[j][1]-Newarray[i][1],2)+pow(Nodelist[j][2]-Newarray[i][2],2))
                if Distance==0:
                    Distance=DisEquation
                    index=j
                if Distance > DisEquation:
                    index=j
                    Distance=DisEquation
        if(Nodelist[index] not in Newarray):
            Newarray.append(Nodelist[index])
        Distance=0
    print (time.time() - Time_Calculation)
    return Newarray
    ```