使用 NetworkX 在图中进行循环检测 Python

Question

我的 CSV 文件有大约 260 万条不同人之间的交易记录。我正在尝试从该文件中制作一个图表：具有唯一 ID 的人作为表示两个人之间交易的节点和边缘，并希望从图表中获取所有可能的周期。我正在尝试使用 networkx.simple_cycles(graph_name) 从该图中获取所有循环，但出现此错误：

    NetworkXNotImplemented                    Traceback (most recent call 
    last)
    <ipython-input-21-c36e4cd0e220> in <module>()
    ----> 1 nx.simple_cycles(Directed_G)

    <decorator-gen-215> in simple_cycles(G)

    ~\AppData\Local\Continuum\anaconda3\lib\site- 
     packages\networkx\utils\decorators.py in _not_implemented_for(f, *args, 
     **kwargs)
     64         if match:
     65             raise nx.NetworkXNotImplemented('not implemented for %s 
     type'%
     ---> 66                                             ' 
     '.join(graph_types))
     67         else:
     68             return f(*args,**kwargs)

     NetworkXNotImplemented: not implemented for undirected type

我的 Python 代码如下所示：

    import pandas as pd
    import time
    import networkx as nx
    import numpy as np
    import matplotlib.pyplot as plt
    import seaborn as sns
    %matplotlib inline

    data=pd.read_csv(path/to/csv/file)
    Directed_G=nx.DiGraph()
    Directed_G=nx.from_pandas_dataframe(data, 'from', 'to')
    nx.simple_cycles(Directed_G)

我的数据看起来像这样：

            from                to  
    0       000028c1f8598db 1a55bc3aab8562f     
    1       00003147f02a255 9c1f54d9859ce12     
    2       00003cdc5ed35a0 472f48d28903b43     
    3       00003cdc5ed35a0 5ab9e7e07978f9d 
    4       00003cdc5ed35a0 693452b7ae2fd0c

谁能帮我解决这个错误。是否有其他方法可以从该图中找到所有可能的循环？

Answer 1

当你这样做时：

Directed_G=nx.from_pandas_dataframe(data, 'from', 'to')

它从 pandas 数据框创建一个图形，并将该结果分配给名称 Directed_G。它不会先去检查 Directed_G 以前是哪种图表。因此它使用默认类型（即 Graph）创建了一个图，并且之前存储在 Directed_G 中的图被覆盖，丢失给了天空中的垃圾收集器。然后查找循环的命令就死了，因为它无法处理无向图。

将可选参数 create_using=DiGraph 添加到对 from_pandas_dataframe 的调用中。

您应该知道在最新版本的 networkx 中 from_pandas_dataframe 已被删除：https://networkx.github.io/documentation/networkx-2.0/release/release_2.0.html

Previously, the function from_pandas_dataframe assumed that the dataframe has edge-list like structures, but to_pandas_dataframe generates an adjacency matrix. We now provide four functions from_pandas_edgelist, to_pandas_edgelist, from_pandas_adjacency, and to_pandas_adjacency.

使用 NetworkX 在图中进行循环检测 Python

Cycle Detection in a Graph using NetworkX Python

python

graph

networkx

cycle-detection