查找 Python 中点的所有后代
Find all descendants for points in Python
我需要获取所有用 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 中的所有行，这会导致某些问题。但是，如果有人要我 post 我当然会的代码。
期望的输出是这样的：
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，则停止，不要继续。
欢迎任何帮助或提示，真的。
提前致谢。
您的规则不一致且定义不明确，因此您可能需要在各处添加一些限制条件，因为不清楚您的确切要求。通过组织数据结构来解决问题和构建更强大的遍历函数（如下所示），add/edit 根据需要约束 - 并彻底解决问题。
将 df 转换为 dict 以更好地表示树结构
如果将数据结构转换为更直观的问题，而不是尝试在当前结构的上下文中解决问题，这个问题就会简单很多。
## Example dataframe
df = pd.DataFrame({'side_a':['a','b','c','k','l','l','p','q','r'],'side_b':['b','c','d','l','m','n','q','r','s']})
## Instantiate blank tree with every item
all_items = set(list(df['side_a']) + list(df['side_b']))
tree = {ii : set() for ii in all_items}
## Populate the tree with each row
for idx, row in df.iterrows():
tree[row['side_a']] = set(list(tree[row['side_a']]) + list(row['side_b']))
遍历树
既然数据结构很直观，这就简单多了。任何标准 Depth-First-Search algorithm w/ path saving 都可以。我修改了 link 中的那个来处理这个例子。
编辑：再次阅读它看起来你在 endpoint 中有一个搜索终止条件（你需要在你的问题中更清楚什么是输入和什么是输出）。您可以调整 dfs_path(tree,**target**, root) 并将终止条件更改为 return 只有正确的路径。
## Standard DFS pathfinder
def dfs_paths(tree, root):
stack = [(root, [root])]
while stack:
(node, path) = stack.pop()
for nextNode in tree[node] - set(path):
# Termination condition.
### I set it to terminate search at the end of each path.
### You can edit the termination condition to fit the
### constraints of your goal
if not tree[nextNode]:
yield set(list(path) + list(nextNode)) - set(root)
else:
stack.append((nextNode, path + [nextNode]))
从我们产生的生成器构建数据框
如果您对生成器不是很满意，您可以构建 DFS 遍历，以便它以列表形式输出。而不是发电机
set_a = []
end_points = []
gen_dict = [{ii:dfs_paths(tree,ii)} for ii in all_items]
for gen in gen_dict:
for row in list(gen.values()).pop():
set_a.append(list(gen.keys()).pop())
end_points.append(row)
## To dataframe
df_2 = pd.DataFrame({'set_a':set_a,'end_points':end_points}).sort_values('set_a')
输出
df_2[['set_a','end_points']]
set_a end_points
a {b, c, d}
b {c, d}
c {d}
k {n, l}
k {m, l}
l {n}
l {m}
p {s, r, q}
q {s, r}
r {s}
如果您接受额外的导入，这可以作为图形上的路径问题，并使用 NetworkX:
在几行中解决
import networkx
g = networkx.DiGraph(zip(df1.side_a, df1.side_b))
outdf = df2.apply(lambda row: [row.side_a,
set().union(*networkx.all_simple_paths(g, row.side_a, row.end_point)) - {row.side_a}],
axis=1)
outdf 看起来像这样。请注意，这包含集合而不是所需输出中的列表 - 这允许以简单的方式组合所有路径。
side_a end_point
0 a {c, b}
1 b {c}
2 c {}
3 k {l, m}
4 k {l, n}
5 l {m}
6 l {n}
7 p {r, q, s}
8 q {r, s}
9 r {s}
您可以使用 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]
我需要获取所有用 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 中的所有行，这会导致某些问题。但是，如果有人要我 post 我当然会的代码。
期望的输出是这样的：
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，则停止，不要继续。
欢迎任何帮助或提示，真的。 提前致谢。
您的规则不一致且定义不明确，因此您可能需要在各处添加一些限制条件，因为不清楚您的确切要求。通过组织数据结构来解决问题和构建更强大的遍历函数（如下所示），add/edit 根据需要约束 - 并彻底解决问题。
将 df 转换为 dict 以更好地表示树结构
如果将数据结构转换为更直观的问题，而不是尝试在当前结构的上下文中解决问题，这个问题就会简单很多。
## Example dataframe
df = pd.DataFrame({'side_a':['a','b','c','k','l','l','p','q','r'],'side_b':['b','c','d','l','m','n','q','r','s']})
## Instantiate blank tree with every item
all_items = set(list(df['side_a']) + list(df['side_b']))
tree = {ii : set() for ii in all_items}
## Populate the tree with each row
for idx, row in df.iterrows():
tree[row['side_a']] = set(list(tree[row['side_a']]) + list(row['side_b']))
遍历树
既然数据结构很直观，这就简单多了。任何标准 Depth-First-Search algorithm w/ path saving 都可以。我修改了 link 中的那个来处理这个例子。
编辑：再次阅读它看起来你在 endpoint 中有一个搜索终止条件（你需要在你的问题中更清楚什么是输入和什么是输出）。您可以调整 dfs_path(tree,**target**, root) 并将终止条件更改为 return 只有正确的路径。
## Standard DFS pathfinder
def dfs_paths(tree, root):
stack = [(root, [root])]
while stack:
(node, path) = stack.pop()
for nextNode in tree[node] - set(path):
# Termination condition.
### I set it to terminate search at the end of each path.
### You can edit the termination condition to fit the
### constraints of your goal
if not tree[nextNode]:
yield set(list(path) + list(nextNode)) - set(root)
else:
stack.append((nextNode, path + [nextNode]))
从我们产生的生成器构建数据框
如果您对生成器不是很满意，您可以构建 DFS 遍历，以便它以列表形式输出。而不是发电机
set_a = []
end_points = []
gen_dict = [{ii:dfs_paths(tree,ii)} for ii in all_items]
for gen in gen_dict:
for row in list(gen.values()).pop():
set_a.append(list(gen.keys()).pop())
end_points.append(row)
## To dataframe
df_2 = pd.DataFrame({'set_a':set_a,'end_points':end_points}).sort_values('set_a')
输出
df_2[['set_a','end_points']]
set_a end_points
a {b, c, d}
b {c, d}
c {d}
k {n, l}
k {m, l}
l {n}
l {m}
p {s, r, q}
q {s, r}
r {s}
如果您接受额外的导入，这可以作为图形上的路径问题，并使用 NetworkX:
在几行中解决import networkx
g = networkx.DiGraph(zip(df1.side_a, df1.side_b))
outdf = df2.apply(lambda row: [row.side_a,
set().union(*networkx.all_simple_paths(g, row.side_a, row.end_point)) - {row.side_a}],
axis=1)
outdf 看起来像这样。请注意，这包含集合而不是所需输出中的列表 - 这允许以简单的方式组合所有路径。
side_a end_point
0 a {c, b}
1 b {c}
2 c {}
3 k {l, m}
4 k {l, n}
5 l {m}
6 l {n}
7 p {r, q, s}
8 q {r, s}
9 r {s}
您可以使用 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]