5
\$\begingroup\$

I have a list of tuples or a NumPy array (it can be either of them as the variable comes as a list and will end up being a NumPy array) and I want to order them in a specific way (that I am not able to phrase it).

Let's make an example:

boundary=[(1, 2), (1, 3), (3, 4), (2, 4)];

Desired output:

[(1, 2), (2, 4), (4, 3), (3, 1)]

(or a NumPy array of 2x4 will do also)

The logic behind it is to get the first row, read its last value and find that value in the array. Get that tuple, swap it to make the found value the first one (if needed) and repeat.

The idea is that ...N),(N... , N is the same. There will always be 2 and only 2 repetitions of the numbers.

I can figure out how to do it "C-like", iterating, searching, swapping etc, but I wonder if there is a pythonic way (those amazing one-liners) of achieving it. Ultimately I am just trying to increase my Python-fu.

boundary=np.array(boundary)
ordered=np.zeros([boundary.shape[0],boundary.shape[1]]);
idx=0
idy=0
for i in range(len(boundary)):
    ordered[i,0]=boundary[idx,idy]
    ordered[i,1]=boundary[idx,(idy+1)%2]
    ix,iy=np.where(boundary==boundary[idx,(idy+1)%2])
    for j in range(len(ix)):
        isused=np.where(np.all(ordered==boundary[ix[j],],axis=1))
        if isused[0].size==0:
            idx=ix[j]
            idy=iy[j]
            print idx, idy
            break
\$\endgroup\$
11
\$\begingroup\$

This is really a graph problem! Draw a graph with a vertex for every number in your list, and an edge between vertices \$a\$ and \$b\$ if there is a pair \$(a, b)\$ or \$(b, a)\$ in your list:

graph with four vertices and edges 1-2, 1-3, 2-3 and 3-4

What you want to do is to find a path in this graph that visits all the edges. Such a path is known as an Eulerian path. Your condition that each number appears exactly twice in the list means that the path must return to the original vertex: that makes it an Eulerian cycle.

To find this cycle, we must first represent the graph using a suitable data structure. Here we can use the adjacency list representation (really, adjacency set):

from collections import defaultdict

def graph(edges):
    """Given a list of edges, return a map from vertex to a set of
    adjacent vertices.

    >>> graph([(1, 2), (1, 3), (3, 4), (2, 4)])
    defaultdict(<class 'set'>, {1: {2, 3}, 2: {1, 4}, 3: {1, 4}, 4: {2, 3}})

    """
    g = defaultdict(set)
    for v, w in edges:
        g[v].add(w)
        g[w].add(v)
    return g

Then, to find the path, we can use Hierholzer's algorithm. This is really simple: we just pick a starting vertex and then repeatedly pick any unvisited edge from that vertex. Your condition that each number appears exactly twice in the list of edges means that the algorithm can't get stuck: there are exactly two edges meeting each vertex, so having gone in on one we can go out on the other:

def eulerian_path(edges, v):
    """Generate an Eulerian path over the given collection of edges,
    starting at the vertex v.

    >>> list(eulerian_path([(1, 2), (1, 3), (3, 4), (2, 4)], 1))
    [(1, 2), (2, 4), (4, 3), (3, 1)]

    """
    g = graph(edges)
    while True:
        try:
            w = g[v].pop()
        except KeyError:
            return
        g[w].remove(v)
        yield v, w
        v = w

What might happen, however, is that your data contains multiple disjoint cycles. For example if the input is:

[(1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 4)]

then this corresponds to the graph:

graph with six vertices and edges 1-2, 2-3, 3-1, 4-5, 5-6 and 6-4

The eulerian_path algorithm only finds one of the cycles. What should you do in ths case? Stop at the end of the first cycle? Keep going and find all the other cycles? Maybe this can't happen in your problem, so raise an error? You didn't explain what your problem really is, so I can't tell you what the right thing is to do in this case.

Update

If you're determined to stick to NumPy, then consider using the Compressed Sparse Graph Routines. The idea is to use scipy.sparse.csr_matrix to convert your array into a CSR matrix:

>>> edges = np.array([(1, 2), (1, 3), (3, 4), (2, 4)])
>>> m = scipy.sparse.csr_matrix((np.ones(len(edges)), (edges[:,0], edges[:,1])), shape=(5, 5))

and then call scipy.sparse.csgraph.depth_first_order to get the vertices on the Eulerian path:

>>> scipy.sparse.csgraph.depth_first_order(m, 1, False)[0]
array([1, 2, 4, 3], dtype=int32)

If you need to turn this array of vertices back into an array of edges (as in the OP), you could use numpy.vstack and numpy.roll, like this:

>>> np.vstack((vertices, np.roll(vertices, -1))).T
array([[1, 2],
       [2, 4],
       [4, 3],
       [3, 1]], dtype=int32)
\$\endgroup\$
  • \$\begingroup\$ Haha fantastic. Actually my whole code is supposed to find the boundary of a FEM triangular mesh in order, so yeah, good one. the disjoint case wont happen. The explanation is fantastic, and the code brilliant. However, I just would like to avoid using any more data structures for the moment, as ultimately the result will be stored in a numpy.array. Is that possible? The .pop() and remove() are very nice, but I feel like I waste too much code into changing datatypes all the time \$\endgroup\$ – Ander Biguri Jul 2 '15 at 19:42
  • \$\begingroup\$ Consider using scipy.sparse.csgraph.depth_first_order. \$\endgroup\$ – Gareth Rees Jul 2 '15 at 19:57
  • \$\begingroup\$ Still constrained into using a new datatype right? \$\endgroup\$ – Ander Biguri Jul 2 '15 at 20:01
  • 1
    \$\begingroup\$ See update. You can't expect a graph algorithm to operate on the list-of-edges representation of a graph (see here: this representation doesn't efficiently support common graph operations, like enumerating the vertices, or finding adjacent vertices), so some kind of transformation will be needed. The compressed sparse graph version of the code is only two lines long, so I expect you can cope. \$\endgroup\$ – Gareth Rees Jul 2 '15 at 20:13
  • 1
    \$\begingroup\$ I would just add np.r_[np.c_[idx[:-1], idx[1:]], [(idx[-1], idx[0]),]] with idx = the last output in the edited answer, to get the desired output by the OP (which works assuming it is a loopy graph). \$\endgroup\$ – Imanol Luengo Jul 2 '15 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.