Gfrktyl

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.

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 ?

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][0]

## note: 'starting_tuple' could be either (0, 7) or (0, 8), starting direction doesn't matter



order = [starting_tuple[0], starting_tuple[1]]

## 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 only have access to full python packages (no numpy).

This question has also been posted on SO.

No need for recursion. You may want to first convert the tuples to a dict to make it more readable. Then iterate over the dict to construct an ordered list.

In terms of efficiency (or time / space complexity), your code is $O(n^3)$ in time and $O(1)$ in auxiliary space. Note that idx = tuples.index(e) is not necessary at all, since tuples.index(e) == i. Making use of this would allow your code to be $O(n^2)$ in time. The most time-efficient solution is $O(n)$, which is also the time complexity of the proposed solution involving a dict. However, the auxiliary space complexity of that solution is $O(n)$ -- inferior to your original approach.

If you want to update the order after obtaining a new tuples list, you can keep the dict and iterate over the new tuples, comparing with values in the dict to see if there is any change. However, the efficiency of this approach would probably be in most cases worse than constructing a new dict from scratch.

from collections import defaultdict



def tuples_to_neighbors_dict(tuples):

  """

  Covert `tuples` to a dict mapping each point to a list of its neighbors.

  """

  neighbors = defaultdict(list)



  for (a,b) in tuples:

    neighbors[a].append(b)

    neighbors[b].append(a)



  return neighbors



def tuples_to_order(tuples, start=0):

  """

  Covert `tuples` to a list of points.

  """

  neighbors = tuples_to_neighbors_dict(tuples)

  order = 



  prev = None

  current = start



  while current != start or prev is None:

    # add the current value to the list

    order.append(current)



    # move to the next -- pick the neighbor which we haven't visited yet

    neigh = neighbors[current]

    new = neigh[1] if neigh[0] == prev else neigh[0]

    prev = current

    current = new



  return order

EDIT   I just now looked at the SO question and noticed that one answer is almost identical to mine 😁