I'm not really sure how to describe my question here, so I guess I'll try and explain the situation first. I've got a data set being pulled in from a square lattice grid of 4 sided polygons. The lattice dimensions aren't guaranteed to be anything in particular. I have access to the data that describes the neighbours of any given point on the grid (ie, "point 236 has edges to points 417, 872, 123, and 331") and that's about it.
What I have is this:
graph = [set([5, 9]), set([4, 11]), set([5, 6, 12]), set([6, 10, 2]), \
set([1, 3, 8]), set([3, 7, 4]), set([6, 12, 10, 16]), \
set([5, 9, 18, 12]), set([1, 8, 13]), set([4, 11, 7, 15]), \
set([2, 10, 17]), set([3, 7, 8, 14]), set([9, 18]), \
set([18, 12, 16]), set([16, 10, 17]), set([14, 7, 15]), \
set([15, 11]), set([13, 8, 14])]
Where graph[n] lets me access the neighbours of any given point by index n... The entire data set of which can be visualized by the 2D graph shown below (which I don't have access to other then via the data listed above):
*--------*--------*-------*-------*-------*
| 1 | 5 | 3 | 6 | 4 | 2
| | | | | |
| | | | | |
*--------*--------*-------*-------*-------*
| 9 | 8 | 12 | 7 | 10 | 11
| | | | | |
| | | | | |
*--------*--------*-------*-------*-------*
13 18 14 16 15 17
And I'm trying to turn it into a set of data that looks like this:
u = [[1, 5, 3, 6, 4, 2], [9, 8, 12, 7, 10, 11], [13, 18, 14, 16, 15, 17]]
v = [[1, 9, 13], [5, 8, 18], [3, 12, 14], [6, 7, 16], [4, 10, 15], [2, 11, 17]]
The output data describes the parallel lines of the grid (starting at the corner with the lowest index number). Each point is guaranteed to have a unique index, and the grid is guaranteed to have a contiguous set of indices (in this case, 1 through to 18) but the order is not guaranteed in any way. The dimensions of the grid are not known beforehand. Each point will only ever have a valance of 2 (corner point), 3 (edge point), or 4 (point somewhere in the centre).
Now, I've written a brute force approach to this, but it's fairly inefficient. It consists of figuring out the first two horizontal and vertical edges (in this case, [1, 5, 3, 6, 4, 2] and [1, 9, 13]), then "shifting" each edge over by getting the connected neighbours of each point and subtracting an already visited set from that (so 1 -> 5, 9 -> 8, 13 -> 18) and repeating this process until you hit the other side of the grid.
What I was wondering was if there was a more "pythonic" way of handling this. My own code is split up into several different phases, but I figured there's got to be some way of doing this in one fell swoop rather then iterating over everything so many times (it's currently taking me about 60ms per run to figure all this out, and I'm trying to get that down to 20ms if possible).
I think you can build your grid gradually, one node at a time without too much trouble. Here's how I'd do it:
zip(*rows))If your neighbor data is in the form of a dictionary mapping from each node to a list of its neighbors, this code should work:
def make_grid(neighbor_dict):
# step 1, find the first corner
for node, neighbors in neighbor_dict:
if len(neighbors) == 2:
break # node and neighbors will hold our start corner and its neighbors
# step 2, build the first edge
row = [node, neighbor[0]] # start with the corner, and an arbitrary neighbor
while len(neighbors_dict[row[-1]]) == 3:
for neighbor in neighbor_dict[row[-1]]:
if neighbor != row[-2] and len(neighbor_dict[neighbor]) <= 3:
row.append(neighbor)
break
# setup for steps 3 and 4
seen = set(row) # a set of all nodes we've added to the grid so far
rows = []
done = False
while not done: # this loop is step 4, building all rows
rows.append(row)
new_row = []
for node in row: # this is step 3, building a new row from the previous row
for neighbor in neighbor_dict[node]:
if neighbor not in seen:
new_row.append(neighbor)
seen.add(neighbor)
break
else: # no break hit in for loop, only happens if `row` is the far edge
done = True
break
row = new_row
# step 5, transpose to get columns from rows
columns = list(zip(*rows))
return rows, columns