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]])