CODEWITHSUNDEEP
python
sjpratt
sjpratt

Reputation: 68

More elegant solution to graph implementation?

I am currently trying to make a program that will use a graph data structure, in the shape of a grid to be used for a pathfinding algorithm. My only issue is that I will be planning on making a 20x20 grid, and a 4x4 one already takes up a lot of space.

graph = {'A': ['B', 'E'],
     'B': ['A', 'C', 'F'],
     'C': ['B', 'D', 'G'],
     'D': ['C', 'H'],
     'E': ['A', 'F', 'I'],
     'F': ['B', 'E', 'J', 'G'],
     'G': ['C', 'F', 'K', 'H'],
     'H': ['D', 'G', 'L'],
     'I': ['E', 'J', 'M'],
     'J': ['F', 'I', 'K', 'N'],
     'K': ['L', 'G', 'O', 'L'],
     'L': ['H', 'K', 'P'],
     'M': ['I', 'N'],
     'N': ['J', 'M', 'O'],
     'O': ['K', 'N', 'P'],
     'P': ['L', 'O']}

Is there a more elegant solution to creating a graph that I am missing?

Upvotes: 1

Views: 66

Answers (1)

JohanL
JohanL

Reputation: 6891

As long as you know that your grid will be rectangular, you will always have the same relative distance between neighbors (i.e. the above neighbor will always be X = number of columns before the current element in the list and the neighbor below will always be X columns after).

It is more easily seen if using 2D descriptions of the nodes. However, it is a simple task to convert between 1D and 2D descriptions (using divmod). A somewhat convoluted example (to allow for a bit more than you ask for) is:

from functools import partial

# Get node order from coordinates
def orderYX(y, x, Y, X):
    return y*X + x

# Get coordinates from node order
def coordinatesYX(num, Y, X):
    return divmod(num, X)

# Get the coordinates of the neigbors, based on current coordinates
def get_neighborsYX(y, x, Y, X):
    neighbors = [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]
    # Also filter out neighbors outside the grid
    return [(y, x) for y, x in neighbors if (0 <= y < Y) and (0 <= x < X)]

# Special function to translate a node number to a name
# (To be able to print the graph with letters as names)
def get_name(num):
    name = []
    base = ord('A')
    Z = ord('Z') - base
    # If the number of nodes is larger than Z (25)
    # multiple letters must be used for the name
    while num > Z:
        res, rem = divmod(num, Z+1)
        num = res-1
        name.append(chr(rem + base))
    name.append(chr(num + base))
    name.reverse()
    return "".join(name)

Y = 20 # Number of rows
X = 20 # Number of columns

# Partially apply the functions, to not have to pass Y and X repeatedly
order = partial(orderYX, Y=Y, X=X)
coordinates = partial(coordinatesYX, Y=Y, X=X)
get_neighbors = partial(get_neighborsYX, Y=Y, X=X)

# Generate the graph (with named nodes)
# This may not be necessary, since the neighbors can be found when needed.
graph = {}
for num in range(Y*X):
    coord = coordinates(num)
    neighbors_coord = get_neighbors(*coord)
    neighbors = [order(y, x) for y, x in neighbors_coord]
    graph[get_name(num)] = [get_name(neighbor) for neighbor in neighbors]

In this example I have also used partial from the functools module, mainly because I like it. :-)

Upvotes: 1

Related Questions