Most efficient way to find spatial order from a list of tuples (Python)

Question

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.

Answer 1

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 😁