python - 在 Python 中查找点的所有后代

Question

我需要获取所有用 side_a - side_b 表示的链接的后代点(在一个数据帧中)，直到到达每个 side_a 它们的 end_point(在其他数据帧中)。所以:

df1:
side_a   side_b
  a        b
  b        c
  c        d
  k        l
  l        m
  l        n
  p        q
  q        r
  r        s

df2:
side_a    end_point
  a          c
  b          c
  c          c
  k          m
  k          n
  l          m
  l          n
  p          s
  q          s
  r          s

重点是获取每个 side_a 值的所有点，直到从 df2 到达该值的 end_point。如果它有两个 end_point 值(就像“k”一样)，它应该是两个列表。

我有一些代码，但它不是用这种方法编写的，如果 df1['side_a'] == df2['end_points'] 它会删除 df1 中的所有行，这会导致某些问题。但是，如果有人要我发布代码，我当然会。

期望的输出应该是这样的:

side_a    end_point
  a          [b, c]
  b          [c]
  c          [c]
  k          [l, m]
  k          [l, n]
  l          [m]
  l          [n]
  p          [q, r, s]
  q          [r, s]
  r          [s]

还有一件事，如果两边相同，那一点根本不需要列出，我可以稍后附加它，无论它更容易。

import pandas as pd
import numpy as np
import itertools

def get_child_list(df, parent_id):
    list_of_children = []
    list_of_children.append(df[df['side_a'] == parent_id]['side_b'].values)
    for c_, r_ in df[df['side_a'] == parent_id].iterrows():
        if r_['side_b'] != parent_id:
            list_of_children.append(get_child_list(df, r_['side_b']))

    # to flatten the list 
    list_of_children =  [item for sublist in list_of_children for item in sublist]
    return list_of_children

new_df = pd.DataFrame(columns=['side_a', 'list_of_children'])
for index, row in df1.iterrows():
    temp_df = pd.DataFrame(columns=['side_a', 'list_of_children'])
    temp_df['list_of_children'] = pd.Series(get_child_list(df1, row['side_a']))
    temp_df['side_a'] = row['side_a']

    new_df = new_df.append(temp_df)

因此，此代码的问题在于，如果我从 df2 中删除 side_a 等于 end_point 的行，它会起作用。我不知道如何实现条件，即如果在 side_b 列中捕获 df2，则停止，不要再继续。

真的，欢迎任何帮助或提示。提前致谢。

Answer 1

您可以使用 networkx 库和图形:

import networkx as nx
G = nx.from_pandas_edgelist(df, source='side_a',target='side_b')
df2.apply(lambda x: [nx.shortest_path(G, x.side_a,x.end_point)[0],
                     nx.shortest_path(G, x.side_a,x.end_point)[1:]], axis=1)

输出:

  side_a  end_point
0      a     [b, c]
1      b        [c]
2      c         []
3      k     [l, m]
4      k     [l, n]
5      l        [m]
6      l        [n]
7      p  [q, r, s]
8      q     [r, s]
9      r        [s]