使用Python创建递归拓扑树：双DataFrame链路截断实现问询

Hey there! Let's work through building those recursive topology trees for your link data. I'll break this down into easy, actionable steps so you can follow along.

First, we need a way to quickly look up which nodes connect to which—an adjacency list is perfect for this. It turns your df1 into a dictionary where each key is a starting node, and the value is a list of nodes it points to.

import pandas as pd

# Example df1 (replace with your actual data)
df1 = pd.DataFrame({
    'point_1': ['A', 'B', 'C', 'D', 'D', 'M', 'N'],
    'point_2': ['B', 'C', 'D', 'E', 'F', 'N', 'O']
})

# Build the adjacency list
adjacency_list = df1.groupby('point_1')['point_2'].apply(list).to_dict()

# Add nodes that only appear as destinations (no outgoing links) to avoid KeyErrors later
for node in set(df1['point_2']) - set(adjacency_list.keys()):
    adjacency_list[node] = []

This gives you a clean map: {'A': ['B'], 'B': ['C'], 'C': ['D'], 'D': ['E', 'F'], 'M': ['N'], 'N': ['O'], 'E': [], 'F': [], 'O': []}

Next, we'll create a recursive function that starts at your point_A, traverses the adjacency list, and stops when it hits the end_point. It returns a nested dictionary that represents the topology tree.

def build_topology(start_node, end_node, adjacency_list, current_path=None):
    # Initialize the current path if it's the first call
    if current_path is None:
        current_path = []
    current_path.append(start_node)
    
    # Stop recursion if we've reached the end node
    if start_node == end_node:
        return {start_node: []}
    
    # If the node has no outgoing links, return it as a leaf
    if not adjacency_list.get(start_node, []):
        return {start_node: []}
    
    # Recursively build child trees for each connected node
    children = []
    for next_node in adjacency_list[start_node]:
        if next_node == end_node:
            # Directly add the end node as a leaf
            children.append({next_node: []})
        else:
            # Recurse to build the sub-tree, using a copy of the path to avoid reference issues
            child_tree = build_topology(next_node, end_node, adjacency_list, current_path.copy())
            children.append(child_tree)
    
    return {start_node: children}

For example, calling build_topology('A', 'E', adjacency_list) will return:

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

Now we'll run this function on each pair of point_A and end_point in df2, and store the results directly in the dataframe.

# Example df2 (replace with your actual data)
df2 = pd.DataFrame({
    'point_A': ['A', 'A', 'M'],
    'end_point': ['E', 'F', 'O']
})

# Add a new column with the topology tree for each row
df2['topology_tree'] = df2.apply(
    lambda row: build_topology(row['point_A'], row['end_point'], adjacency_list),
    axis=1
)

# Print the results to verify
print(df2[['point_A', 'end_point', 'topology_tree']])

Optional: Get a simple path list instead of a nested tree #

If you don't need the nested dictionary format and just want a flat list of nodes from start to end, you can use this modified recursive function:

def build_path(start_node, end_node, adjacency_list, current_path=None):
    if current_path is None:
        current_path = [start_node]
    
    if start_node == end_node:
        return current_path
    
    # Recursively check each connected node
    for next_node in adjacency_list[start_node]:
        path = build_path(next_node, end_node, adjacency_list, current_path.copy())
        if path:
            return path
    # Return None if no path exists (adds a safety net)
    return None

Then add it to df2 like this:

df2['path'] = df2.apply(
    lambda row: build_path(row['point_A'], row['end_point'], adjacency_list),
    axis=1
)

This will give you values like ['A', 'B', 'C', 'D', 'E'] for the first row.

If you need to adjust the output format (like nested lists instead of dictionaries, or flattening the tree further), just tweak the recursive function to match your needs!

内容的提问来源于stack exchange，提问作者jovicbg