How can you efficiently convert an edge list comprised of node identifiers into an edge list containing row and column indices?

user_12860541 0
Viewed 136

I currently have an edge array of dimension (n_edges, 2) containing node pairs described as [NodeID1, NodeID2], which are both integers. I need to efficiently enumerate these NodeIDs so that I can represent them as indices in an adjacency matrix. My current approach is to extract the unique set of sorted NodeIDs, map them to 0 ranging through the number of distinct nodes, and then replacing the entries using pandas.DataFrame.replace(mapping). Here is an example of what I am doing:

import numpy as np
import pandas as pd

a = np.random.randint(0, 100000000, (40000000, 2))
df = pd.DataFrame(a)
unique_values = np.unique(a)
mapping = dict(zip(unique_values, np.arange(len(unique_values))))

df.replace(mapping)

I have also tried defining a function which applies this map and vectorizing it with NumPy, but it is still quite slow. Any ideas as to how I can implement this more efficiently?

adjacency-matrix python
1 Answers

Turns out np.unique has an option to return the indices of the original numbers in the unique array, you just need to reshape it.

u, indices = np.unique(a, return_inverse=True)
b = indices.reshape(a.shape)

This runs in about 20 seconds on your example.

user_16480330
Related