如何在 Networkx 中从叶子到根的所有路径中从每个叶子到每个节点的连接

Question

所以我已经研究这个问题一段时间了。我之前问过这个问题，但是在仅使用 python 的上下文中。我在这个线程中从 trincot 得到了很好的回答（这里也详细描述了这个问题）：

我在使用它时运行遇到的问题是，它太慢了。它适用于大约 300 行的文件，但我的有 11k。当我尝试运行它时，它占用了我 16 GB RAM 的 95%，并且即使在编译 3 天后也没有 return 结果。所以我考虑为此使用 NetworkX，因为我读到它是图形的最佳库。数据将创建多个树，这些树可能彼此不连接，也没有多图。现在我的代码只从存储数据的文件中获取输入，如下所示：

Parent Child
Parent Child
Parent Child
...

所以让我们从我之前的线程中获取示例数据：

Parent             child
ANALYTICAL_BALANCE BFG_DEPOSIT 
CUSTOMER_DETAIL BALANCE 
BFG_2056 FFD_15 
BALANCE BFG_16 
BFG_16 STAT_HIST 
ANALYTICAL_BALANCE BFG_2056 
CUSTOM_DATA AND_11 
AND_11 DICT_DEAL 
DICT_DEAL BFG_2056

我将数据加载到 pandas dataframe 并删除 Parent 和 Child 相同的连接：

data = pd.read_csv('data.txt', sep=" ", header=0)
data = data[data['child'] != data['Parent]]

然后我从我的数据框创建一个有向图：

G = nx.from_pandas_edgelist(data, source = 'Parent', target = 'child', create_using = nx.DiGraph())

然后我尝试筛选根和叶：

roots = (v for v, d in G.in_degree() if d==0)
leaves = (v for v, d in G.out_degree() if d ==0)

aaaaa 我卡住了。我有两个想法。获取从叶子到根的所有可能路径，然后仅打印从叶子到根的叶子 -> 节点连接，或者获取每个节点，检查它是否存在于从叶子到根的路径中，获取它的叶子并打印叶子 -> 节点。示例数据的输出将如下所示：

ANALYTICAL_BALANCE BFG_DEPOSIT

ANALYTICAL_BALANCE BFG_2056
ANALYTICAL_BALANCE FFD_15
CUSTOM_DATA AND_11
CUSTOM_DATA DICT_DEAL
CUSTOM_DATA BFG_2056
CUSTOM_DATA FFD_15

CUSTOMER_DETAIL BALANCE
CUSTOMER_DETAIL BFG_16
CUSTOMER_DETAIL STAT_HIST

如果您对我如何解决这个问题有任何其他想法，或者哪个库可能更适合这个问题，请随时写信。任何帮助将不胜感激！

Answer 1

好的，我想我的问题的答案真的很简单。整个代码如下所示：

data = pd.read_csv('data.txt', sep=" ", header=0)
data = data[data['child'] != data['Parent']]
G = nx.from_pandas_edgelist(data, source = 'Parent', target = 'child', create_using = nx.DiGraph())
leaves = list((v for v, d in G.in_degree() if d==0))
nodes = G.nodes()
for leaf in leaves:
    for node in nodes:
        if nx.has_path(G,leaf, node) and node not in leaves:
            print(leaf, node)

这段代码背后的想法非常简单。我只是从森林中取出每一片叶子，然后检查是否存在从叶子到每个节点的路径。当然，叶子也是节点，所以当我看到一个节点时，我会通过它。可能有点幼稚，但效果很好。

如何在 Networkx 中从叶子到根的所有路径中从每个叶子到每个节点的连接

How to get connection from every leaf to every node in all paths from leaf to root in Networkx

python

algorithm

networkx