1

Given the following 2D numpy array M, form two sets and arrays A and B containing elements of M such that set A and set B hold no element in common. In other words, split M into two sets of rows from M, such that they span disjoint sets of numbers. The algorithm should work for any number of sets.

Given:

import numpy as np

M = 
[[ 2  1  0]
 [ 0  3  2]
 [ 1  4  0]
 [ 0  4  3]
 [ 5  1  2]
 [ 3  5  2]
 [ 5  4  1]
 [ 4  5  3]
 [ 8  7  6]
 [ 6  9  8]
 [ 7 10  6]
 [ 6 10  9]
 [11  7  8]
 [ 9 11  8]
 [11 10  7]
 [10 11  9]]

Return:

setA = {0, 1, 2, 3, 4, 5}
setB = {6, 7, 8, 9, 10, 11}

A = 
[[ 2  1  0]
 [ 0  3  2]
 [ 1  4  0]
 [ 0  4  3]
 [ 5  1  2]
 [ 3  5  2]
 [ 5  4  1]
 [ 4  5  3]]
B =
[[ 8  7  6]
 [ 6  9  8]
 [ 7 10  6]
 [ 6 10  9]
 [11  7  8]
 [ 9 11  8]
 [11 10  7]
 [10 11  9]]

I was able to form both matrices A and B (the sets aren't strictly necessary), but my code seems inelegant and I wonder if there is a better way. I also have the feeling it might fail if the elements of M come out of order.

Edit: Correction: My code works for this example, but not for others.

My solution:

objects  = []
obj = []
i = 0
for idx, face in enumerate(M):
    if i == 0:
        obj.append(face)
        i = i + 1
    else:
        if np.isin(face,obj).any():
            obj.append(face)
        else: 
            objects.append(obj.copy())
            obj = []
            obj.append(face)
            i = 0
        if idx == len(M)-1:
            objects.append(obj.copy())

print(np.array(objects[0]),'\n\n',np.array(objects[1]))
# returns 
[[2 1 0]
 [0 3 2]
 [1 4 0]
 [0 4 3]
 [5 1 2]
 [3 5 2]
 [5 4 1]
 [4 5 3]]

 [[ 8  7  6]
 [ 6  9  8]
 [ 7 10  6]
 [ 6 10  9]
 [11  7  8]
 [ 9 11  8]
 [11 10  7]
 [10 11  9]]

Note: I tag networkx because I am curious if there is a solution through it. I've used it elsewhere in my code and it has sped everything up enormously.

If curious: This relates to a problem I've been puzzling over. Each element in M represents a triangular face, where each element of the face is a vertex of the triangle. In M, there are two full objects. A and B are unconnected. The above algorithm is a way of sorting M for objects A and B.

McM
  • 471
  • 5
  • 21
  • The question is a little unclear. Do you wish to split M into two sets of rows/triangles from M, such that they span disjoint sets of numbers/nodes? And is it guaranteed such two sets exist? What would you wish to do if there are more than two disjoint sets? – Ehsan Apr 20 '20 at 15:01
  • 1
    Yes, I would. I do not quite have the language, so thank you. In this case, it is guaranteed two such sets exist. I would like to do this for any number of sets. – McM Apr 20 '20 at 15:06
  • If you are using networkx, would it help if you form the graph and find connected components? – Ehsan Apr 20 '20 at 15:07
  • 1
    I did that, and it worked. However, I want to plot the subgraphs in different colors using matplotlib3d. For me to do that, the vertices need to be in their original order since I run ```Poly3DCollection(verts[faces])```. When using ```connected_components``` the order of verts changes. I think this would get around that problem. I could use the original ```verts```, and fill it with each obj of ```faces```. – McM Apr 20 '20 at 15:10
  • I am not sure why it changes the order of vertices, but you can do a hash map from new order to old order to preserve the order maybe? (There could be a better way though but this is a hack that can work) – Ehsan Apr 20 '20 at 15:17
  • Hmmm, how would that work? I haven't used hashmaps yet. Basically, vertex 0 : order 0, etc. It's worth a try! What data structure would you suggest? – McM Apr 20 '20 at 15:25
  • If you provide a working example of separating into connected component, I can work on that. Otherwise, I can think of two ways. One is to assign the order as attribute to node and once partitioned into components, use attribute to rename the nodes. Another way is to keep a pandas/numpy DataFrame/array with two columns, first column with older order and second column corresponding new order. – Ehsan Apr 20 '20 at 15:29
  • Interesting, I'll have to think about that. Gonna run to the store, but please see my previous [question](https://stackoverflow.com/questions/61280483/how-to-create-a-networkx-graph-using-2d-np-array-as-input) and [answer](https://stackoverflow.com/a/61282961/12919727), which successfully separates objects using connected_components. – McM Apr 20 '20 at 15:32
  • This https://mathematica.stackexchange.com/questions/37249/how-to-split-list-into-disjoint-lists answers your question (not it python but you can find the algorithms there, the main one being using the graph we discussed) – Ehsan Apr 20 '20 at 15:36
  • Translating that may take some time... Are you thinking it'd use networkx? – McM Apr 20 '20 at 16:51
  • The basic idea is still using graph connectivity. Try using network and connected component with node attributes. I will dig deeper into reordering nodes of connected components. Thank you. – Ehsan Apr 20 '20 at 16:53
  • @Ehsan, I have created a [post](https://stackoverflow.com/questions/61569196/given-a-set-of-triangle-vertices-and-faces-separate-objects-and-form-separate-m) still focused on this question, but with more context. It does provide a working example for separating into connected components. The hashmap may be a way of retaining vertex indices. The pandas route was very slow. I am curious if there is some way to run connected components on faces. I never was able to transform the mathematica into python. Anyway, please see my new post if this interests you. Thanks! – McM May 03 '20 at 03:21
  • Just to elaborate. connected components separates into objects because it is fed edges as tuples ```(v1 : v2)```. With faces, we have just the vertices of each face ```[v1 v2 v3]``` and I do not see how I could put that in a form that networkx could then work on. – McM May 03 '20 at 03:23
  • This has been solved. https://stackoverflow.com/a/61590348/12919727 – McM May 05 '20 at 02:00

0 Answers0