Help finding longest non-repeating path through connected nodes - Python
- by Jordan Magnuson
I've been working on this for a couple of days now without success. Basically, I have a bunch of nodes arranged in a 2D matrix. Every node has four neighbors, except for the nodes on the sides and corners of the matrix, which have 3 and 2 neighbors, respectively. Imagine a bunch of square cards laid out side by side in a rectangular area--the project is actually simulating a sort of card/board game.
Each node may or may not be connected to the nodes around it. Each node has a function (get_connections()), that returns the nodes immediately around it that it is connected to (so anywhere from 0 to 4 nodes are returned). Each node also has an "index" property, that contains it's position on the board matrix (eg '1, 4' - row 1, col 4). What I am trying to do is find the longest non-repeating path of connected nodes given a particular "start" node.
I've uploaded a couple of images that should give a good idea of what I'm trying to do:
In both images, the highlighted red cards are supposedly the longest path of connected cards containing the most upper-left card. However, you can see in both images that a couple of cards that should be in the path have been left out (Romania and Maldova in the first image, Greece and Turkey in the second)
Here's the recursive function that I am using currently to find the longest path, given a starting node/card:
def get_longest_trip(self, board, processed_connections = list(),
processed_countries = list()):
#Append this country to the processed countries list,
#so we don't re-double over it
processed_countries.append(self)
possible_trips = dict()
if self.get_connections(board):
for i, card in enumerate(self.get_connections(board)):
if card not in processed_countries:
processed_connections.append((self, card))
possible_trips[i] = card.get_longest_trip(board,
processed_connections,
processed_countries)
if possible_trips:
longest_trip = []
for i, trip in possible_trips.iteritems():
trip_length = len(trip)
if trip_length > len(longest_trip):
longest_trip = trip
longest_trip.append(self)
return longest_trip
else:
print
card_list = []
card_list.append(self)
return card_list
else:
#If no connections from start_card, just return the start card
#as the longest trip
card_list = []
card_list.append(board.start_card)
return card_list
The problem here has to do with the processed_countries list: if you look at my first screenshot, you can see that what has happened is that when Ukraine came around, it looked at its two possible choices for longest path (Maldova-Romania, or Turkey, Bulgaria), saw that they were both equal, and chose one indiscriminantly. Now when Hungary comes around, it can't attempt to make a path through Romania (where the longest path would actually be), because Romania has been added to the processed_countries list by Ukraine.
Any help on this is EXTREMELY appreciated. If you can find me a solution to this, recursive or not, I'd be happy to donate some $$ to you.
I've uploaded my full source code (Python 2.6, Pygame 1.9 required) to:
http://www.necessarygames.com/junk/planes_trains.zip
The relevant code is in src/main.py, which is all set to run.
