Skip to content
Advertisement

Getting all row indices in numpy 2d array where elements in each row exists more than 2 times in entire array

I am working with graph data defined as 2d array of edges. I.e.

[[1, 0],
 [2, 5],
 [1, 5],
 [3, 4],
 [1, 4]] 

Defines a graph, all elements define a node id, there are no self loops, it is directed, and no value in a column exists in the other column.

Now to the question, I need to select all edges where both ‘nodes’ occur more than once in the list. How do I do that in a quick way. Currently I am iterating over each edge and looking at the nodes individually. It feels like a really bad way to do this.

Current dumb/slow solution

edges = []
for edge in graph:
   src, dst = edge[0], edge[1]
   # Check src for existance in col 1 & 2
   src_fan = np.count_nonzero(graph == src, axis=1).sum()
   dst_fan = np.count_nonzero(graph == dst, axis=1).sum()

   if(src_fan >= 2 and dst_fan >= 2):
     # Add to edges
     edges.append(edge)

I am also not entirely sure this way is even correct…

Advertisement

Answer

# Obtain the unique nodes and their counts

from_nodes, from_counts = np.unique(a[:, 0], return_counts = True)
to_nodes, to_counts = np.unique(a[:, 1], return_counts = True)

# Obtain the duplicated nodes

dup_from_nodes = from_nodes[from_counts > 1]
dup_to_nodes = to_nodes[to_counts > 1]

# Obtain the edge whose nodes are duplicated

graph[np.in1d(a[:, 0], dup_from_nodes) & np.in1d(a[:, 1], dup_to_nodes)]
Out[297]: array([[1, 4]])
User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement