从图中检索节点值

Question

我有一个由字典定义的图：

{'A':['B', 'C'], 'B': ['D', 'E'], 'C': [], 'D': [], 'E': []}

这些节点中的每一个都对应于熊猫数据帧中的一列，比如

DEE1

A	B	C
A1	B1	C1	D1
A2	B2	C2	D2	E2

这个问题有点不明确，因为图可能非常复杂。对于您的示例，这可能有效：

G = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': [], 'D': [], 'E': []}
paths = []
stack = [[next(iter(G))]]
while stack:
path = stack.pop()
extension = [
path + [node] for node in G[path[-1]] if node not in path
]
if extension:
stack.extend(reversed(extension))
else:
paths.append(path)

结果：

[['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'C']]

从数据帧df:获取数据

data =  [
list(lists)
for lists in zip(*(df[path].apply(list, axis=1) for path in paths))
]

[[['A1', 'B1', 'D1'], ['A1', 'B1', 'E1'], ['A1', 'C1']],
[['A2', 'B2', 'D2'], ['A2', 'B2', 'E2'], ['A2', 'C2']]]

这应该适用于具有根'A'的树(实际上，在这种情况下不需要if node not in path——只是向前看，尽量避免无限循环(。但是像这样的图呢：

G = {
'A': ['B', 'C'], 'B': ['D', 'E'], 'C': [], 'D': [], 'E': [],
'F': ['G'], 'G': ['A'],
'H': ['I'], 'I': ['J', 'K'], 'J': [], 'K': []
}

• 'F'导致'G'，'G'返回'F'，即G有一个循环：应该发生什么
• 并且您无法从'A'到达'H'(G未连接(：它是否应该在输出中

这是一个自适应

paths = []
used = set()
for node in G:
if node in used:
continue
stack = [[node]]
used.add(node)
while stack:
path = stack.pop()
nodes = G[path[-1]]
if nodes:
for node in reversed(nodes):
if node not in used:
stack.append(path + [node])
used.add(node)
else:
if len(path) > 1:
paths.append(path)

它包括每个组件的路径，从组件中的第一个节点开始，这些路径导致死胡同。输出：

[['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'C'],
['H', 'I', 'J'], ['H', 'I', 'K']]