Weighted graph from a matrix (list-of-lists)

Question

I created this code while solving the Euler Project problem 83.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.

Data

Find the minimal path sum, in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by moving left, right, up, and down.

I have a matrix with weights stored as a list-of-lists. The task is to traverse the matrix from the top-left element to the bottom right element. At every point, I can go up, down, left or right. The problem is to find the path with the minimal summed weights.

To answer this, I converted the matrix to a graph (Make_Graph), represented as a dictionary in Python. The key in the dictionary is the string row_index, column_index (Name_Name). My next step in solving the Euler problem (not shown here) is to use Dijkstra's algorithm to find the shortest path.

I'm an amateur Python enthusiast, not a professional programmer. I have the feeling that Make_Graph can be made more Pythonic, but I don't know how. It looks a bit messy to me.

def node_name(row_index, col_index):
 return str(row_index)+","+str(col_index)
def make_graph(matrix):
 graph={}
 for rowindex,row in enumerate(matrix):
 for colindex,value in enumerate(row):
 graph[node_name(rowindex,colindex)]={}
 # Up
 if rowindex>0: graph[node_name(rowindex,colindex)][node_name(rowindex-1,colindex)]=matrix[rowindex-1][colindex]
 # Down
 if rowindex<len(matrix)-1: graph[node_name(rowindex,colindex)][node_name(rowindex+1,colindex)]=matrix[rowindex+1][colindex]
 # Left
 if colindex>0: graph[node_name(rowindex,colindex)][node_name(rowindex,colindex-1)]=matrix[rowindex][colindex-1]
 # Right
 if colindex<len(row)-1: graph[node_name(rowindex,colindex)][node_name(rowindex,colindex+1)]=matrix[rowindex][colindex+1]
 return graph
print make_graph([[1,2],[3,4],[5,6]])

Answer 1

Well, both node_name and make_graph can be a bit smaller, yes.

def node_name(row_index, col_index):
 return "{},{}".format(row_index, col_index)

format will do the string conversion automatically, no need to call str.

I'd also give everything a bit more space to make it more readable.

def make_graph(matrix):
 graph = {}
 width, height = len(matrix[0]), len(matrix)
 columns = range(width)
 for rowindex in range(height):
 for colindex in columns:
 graph[node_name(rowindex, colindex)] = x = {}
 # Up
 if rowindex > 0:
 x[node_name(rowindex - 1, colindex)] = matrix[rowindex - 1][colindex]
 # Down
 if rowindex < height - 1:
 x[node_name(rowindex + 1, colindex)] = matrix[rowindex + 1][colindex]
 # Left
 if colindex > 0:
 x[node_name(rowindex, colindex - 1)] = matrix[rowindex][colindex - 1]
 # Right
 if colindex < width - 1:
 x[node_name(rowindex, colindex + 1)] = matrix[rowindex][colindex + 1]
 return graph

Except caching more things this would look okay to me. Relying a rectangular matrix seems obvious to me, so width and height can be precomputed. Using range also makes it more clear that you really want the coordinates, not the row or column values.

In the interest of verbosity I'd also just i and j for indexes, but that's your choice obviously.

Also, you know that {(1, 1): 1} works, right? Because there doesn't seem to be a pressing reason to use node_name at all. In contrast to a list a tuple is immutable and can be used as a dictionary key, see also this wiki page for a more thorough discussion on that.

• SuperBiasedMan: Maybe explain why (1, 1) can be a key even though [1, 1] can't.