Python：如何使用节点、父节点、兄弟节点重新组织数据

Question

我在一个数据帧中有一个数据结构，它有3列:节点、父节点、前一个兄弟节点

我想创建完整数据结构的树文件夹，父节点和节点之间的级别不同，节点和previous_sibling之间的级别相同，兄弟节点之间的顺序正确。

因此，一个新的数据框、重新排序和一个新的列“级别”

当parent为null时，节点处于根级别当previous_sibling为null时这是第一个同级

下面是一个例子：

数据帧

应给出以下数据框架

这是我现在所做的，但不包括兄弟姐妹的顺序

def getDescendants(curr, par, level):
    res = [[curr, par, level]]
    children = json_dataframe_flat.query('parent == @curr')
    for n in children.node:
        if n != par:
            deeper = getDescendants(n, curr, level + 1)
            if len(deeper) > 0:
                res.extend(deeper)
    return res
    
result = pd.DataFrame(getDescendants('node0', '', 0), columns=['node', 'parent', 'level'])
print(result)

谢谢你的帮助

Answer 1

树状数据结构可以表示为 DAG，我们可以为其使用 networkx 库。这允许在迭代数据帧的行时逐步构建图形。同级信息可以存储在单独的 DAG 中，然后使用这些 DAG 以正确的顺序检索同级。

以下是一个示例脚本：

from collections import defaultdict

import networkx as nx
from networkx.algorithms.dag import dag_longest_path, dag_longest_path_length


_ = None
data = [
    [0, _, _],
    [1, _, 2],
    [2, _, 0],
    [3, 2, _],
    [4, 1, 7],
    [5, 2, 6],
    [6, 2, 3],
    [7, 1, _],
    [8, 6, _],
]


G = nx.DiGraph()  # main graph (tree)
S = defaultdict(nx.DiGraph)  # graphs for siblings

for n, p, s in data:
    if p is None:
        G.add_node(n)
    else:
        G.add_edge(p, n)
    if s is None:
        S[p].add_node(n)
    else:
        S[p].add_edge(s, n)


class empty:  # utility for printing the resulting tree
    def __repr__(self): return ' '
empty = empty()


n_cols = 1 + dag_longest_path_length(G)
result = [[empty]*n_cols for _ in data]


def fill(node, row, col):
    """Fill the resulting table at position (row, col) and return number of rows used."""
    result[row][col] = node
    count = 1
    for child in dag_longest_path(S[node]):  # there is only one path
        count += fill(child, row+count, col+1)
    return count


row = 0
for node in sorted({n for n,d in G.in_degree() if d == 0}):
    row += fill(node, row, 0)


from pprint import pprint 

pprint(result)

这是输出：

[[0,  ,  ],
 [1,  ,  ],
 [ , 7,  ],
 [ , 4,  ],
 [2,  ,  ],
 [ , 3,  ],
 [ , 6,  ],
 [ ,  , 8],
 [ , 5,  ]]