Most efficient way to find spatial order from a list of tuples?

user_8452243 0
Viewed 195

I have a circle-growth algorithm (line-growth with closed links) where new points are added between existing points at each iteration.

The linkage information of each point is stored as a tuple in a list. That list is updated iteratively.

enter image description here

QUESTIONS:

  • What would be the most efficient way to return the spatial order of these points as a list ?

  • Do I need to compute the whole order at each iteration or is there a way to cumulatively insert the new points in a orderly manner into that list ?

enter image description here

All I could come up with is the following:

tuples = [(1, 4), (2, 5), (3, 6), (1, 6), (0, 7), (3, 7), (0, 8), (2, 8), (5, 9), (4, 9)]

starting_tuple = [e for e in tuples if e[0] == 0 or e[1] == 0][0]
## note: 'starting_tuple' could be either (0, 7) or (0, 8), starting direction doesn't matter

order = list(starting_tuple) if starting_tuple[0] == 0 else [starting_tuple[1], starting_tuple[0]]
## order will always start from point 0


idx = tuples.index(starting_tuple)
## index of the starting tuple


def findNext():
    global idx
    for i, e in enumerate(tuples):
        if order[-1] in e and i != idx:
            ind = e.index(order[-1])
            c = 0 if ind == 1 else 1
            order.append(e[c])
            idx = tuples.index(e)


for i in range(len(tuples)/2):
    findNext()

print order

It is working but it is neither elegant (non pythonic) nor efficient. It seems to me that a recursive algorithm may be more suitable but unfortunately I don't know how to implement such solution.

Also, please note that I'm using Python 2 and can have access to full python packages only (no numpy)

recursion python-2.x sorting python
2 Answers

Since the nodes only link to two other nodes, you can bin them by number, then follow the numbers around. This is O(n) sorting, which is pretty solid, but it's not a true sort in the <,>,= sense.

def bin_nodes(node_list):
    #figure out the in and out nodes for each node, and put those into a dictionary.
    node_bins = {} #init the bins
    for node_pair in node_list: #go once through the list
        for i in range(len(node_pair)): #put each node into the other's bin
            if node_pair[i] not in node_bins: #initialize the bin dictionary for unseen nodes
                node_bins[node_pair[i]] = []
            node_bins[node_pair[i]].append(node_pair[(i+1)%2])
    return node_bins

def sort_bins(node_bins):
    #go from bin to bin, following the numbers
    nodes = [0]*len(node_bins) #allocate a list
    nodes[0] = next(iter(node_bins)) #pick an arbitrary one to start
    nodes[1] = node_bins[nodes[0]][0] #pick a direction to go
    for i in range(2, len(node_bins)):
        #one of the two nodes in the bin is the horse we rode in on.  
        #The other is the next stop.   
        j = 1 if node_bins[nodes[i-1]][0] == nodes[i-2] else 0 #figure out which one ISN"T the one we came in on
        nodes[i] = node_bins[nodes[i-1]][j] #pick the next node, then go to its bin, rinse repeat
    return nodes

if __name__ == "__main__":
    #test
    test = [(1,2),(3,4),(2,4),(1,3)] #should give 1,3,4,2 or some rotation or reversal thereof
    print(bin_nodes(test))
    print(sort_bins(bin_nodes(test)))
user_28865750

Rather than recursion, this seems more like a dictionary and generator problem to me:

from collections import defaultdict

def findNext(tuples):
    previous = 0
    yield previous  # our first result

    dictionary = defaultdict(list)

    # [(1, 4), (2, 5), (3, 6), ...] -> {0: [7, 8], 1: [4, 6], 2: [5, 8], ...}
    for a, b in tuples:
        dictionary[a].append(b)
        dictionary[b].append(a)

    current = dictionary[0][0]  # dictionary[0][1] should also work
    yield current  # our second result

    while True:
        a, b = dictionary[current]  # possible connections

        following = a if a != previous else b  # only one will move us forward

        if following == 0:  # have we come full circle?
            break

        yield following  # our next result

        previous, current = current, following  # reset for next iteration

tuples = [(1, 4), (2, 5), (3, 6), (1, 6), (7, 0), (3, 7), (8, 0), (2, 8), (5, 9), (4, 9)]

generator = findNext(tuples)

for n in generator:
    print n

OUTPUT

% python test.py
0
7
3
6
1
4
9
5
2
8
%

Algorithm currently assumes we have more than two nodes.

user_57712690
Related