使循环查找更快：Pandas 合并的 Numpy 等价物？

Question

我从有向图中的 parent/child（边）关系列表开始，如下所示：

import numpy as np
import pandas as pd

df = pd.DataFrame(columns=['parent', 'child'])
df.loc[0] = (0, 1)
df.loc[1] = (1, 2)
df.loc[2] = (2, 0)

您可以立即看到我们有循环 0 --> 1 --> 2 --> 0。我希望能够像我一样在数据框中检测到这些循环。到目前为止，我的策略（有效但在我更大的数据集上太慢）是利用 pandas 合并函数：

def find_loops(link_df: pd.DataFrame) -> dict:
    link_df.columns = ['0', '1']
    # Max number of iterations - don't expect to need this many.
    num_appts = len(set(link_df['0']) | set(link_df['1']))
    new_df = pd.DataFrame(link_df)
    for i in range(num_appts):
        new_df = new_df.merge(link_df, left_on=str(i+1), right_on='0', how='inner')
        new_df.drop(columns='0_y', inplace=True)
        new_df.columns = [str(j) for j in range(i+3)]

在每次循环迭代中，这为我提供了 new_df.values 中的数组，其中包含长度递增的路径 (i+3)。如果路径结束并且没有循环，那么 merge 函数会自动删除该行，这非常好。为了检测循环，我在 new_df.values 的一行中查找重复值，如下所示：

        paths = new_df.values.astype(np.int32)
        is_loop = pd.Series(paths[:, 0] == paths[:, 1])
        width = i + 3
        for j in range(width - 1):
            for k in range(j+1, width):
                is_loop = is_loop | (paths[:, j] == paths[:, k])

find_loops(df)

我需要此代码运行快很多。有任何想法吗？我的一个想法是尝试在 numpy 中执行 pandas merge 函数，但我不知道哪个函数甚至可以做到这一点。

我已经尝试了 duplicated 函数、Counter 对象和 np.unique 函数，其中 none 的速度远不及我在这里的速度.

我看过this post, and this one；这些功能中的一些是可行的吗？

Answer 1

你可以试试：

import pandas as pd
import networkx as nx

df = pd.DataFrame(columns=['parent', 'child'])
df.loc[0] = (0, 1)
df.loc[1] = (1, 2)
df.loc[2] = (2, 0)


dg = nx.from_pandas_edgelist(df, source='parent', target='child', create_using=nx.DiGraph)
res = list(nx.simple_cycles(dg))
print(res)

输出

[[0, 1, 2]]

来自 simple_cycles 上的文档：

Find simple cycles (elementary circuits) of a directed graph.

A simple cycle, or elementary circuit, is a closed path where no node appears twice. Two elementary circuits are distinct if they are not cyclic permutations of each other.

在上面的文档 link 中，有一些 link 可能感兴趣的其他算法。

使循环查找更快：Pandas 合并的 Numpy 等价物？

Making Loop-Finding Faster: Numpy Equivalent of Pandas Merge?

numpy

graph-theory

duplicates

python-3.x

pandas