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

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...

CodePudding user response：

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

CodePudding user response：

a solution using networkx:

import networkx as nx

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

G = nx.DiGraph()
G.add_edges_from(edges)

print([node for node in G.nodes if G.degree[node]>1])

edit:

print([edge for edge in G.edges if (G.degree[edge[0]]>1) & (G.degree[edge[1]]>1)])

CodePudding user response：

import numpy as np
graph = np.array([[1, 0],
 [2, 5],
 [1, 5],
 [3, 4],
 [1, 4]])

# get a 1d array of all nodes
array = graph.reshape(-1)

# get occurances of each element 
occurances = np.sum(np.equal(array, array[:,np.newaxis]), axis=0)

# reshape back to graph shape
occurances = occurances.reshape(graph.shape)

# check if both edges occur more than once
mask = np.all(occurances > 1, axis=1)

# select the masked elements
edges = graph[mask]

Based on my test this method is almost 2 times faster than the accepted answer.

Test:

import timeit
import numpy as np

graph = np.array([[1, 0],
    [2, 5],
    [1, 5],
    [3, 4],
    [1, 4]])

# accepted answer
def method1(a):
    # 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

    return graph[np.in1d(a[:, 0], dup_from_nodes) & np.in1d(a[:, 1], dup_to_nodes)]

# this answer
def method2(graph):
    # get a 1d array of all nodes
    array = graph.reshape(-1)

    # get occurances of each element then reshape back to graph shape
    occurances = np.sum(np.equal(array, array[:,np.newaxis]), axis=0).reshape(graph.shape)

    # check if both edges occur more than once
    mask = np.all(occurances > 1, axis=1)

    # select the masked elements
    edges = graph[mask]

    return edges

print('method1 (accepted answer): ', timeit.timeit(lambda: method1(graph), number=10000))

print('method2 (this answer): ', timeit.timeit(lambda: method2(graph), number=10000))

Outhput:

method1 (accepted answer):  0.20238440000000013
method2 (this answer):  0.06534320000000005