如何从关联关系DataFrame中获取指定元素的全部输入依赖源头元素

Hey there! I see the issue with your current code—when you hit a node like D that has multiple dependencies (E and F), you're only following one branch (E→G) and never going back to process the other (F→H). That's why you're missing H as a source dependency.

This is a classic graph traversal problem, where each element is a node and the "to→from" relationship is a directed edge (from is a dependency of to). We need to traverse all possible branches to capture all source nodes (nodes that have no dependencies themselves, i.e., they never appear in the to column).

Solution 1: Breadth-First Search (BFS) #

This approach uses a queue to process each dependency level by level, ensuring we don't miss any branches.

import pandas as pd
import numpy as np

# Your original dataset
df = pd.DataFrame(np.array([['A', 'B'], ['B', 'C'], ['C', 'D'],['D', 'E'], ['D', 'F'], ['E', 'G'],['F', 'H'], ['Z', 'T'], ['T', 'M'],['V','D']]), columns=['to', 'from'])

def find_all_source_dependencies(target_obj):
    # Initialize a queue with the target object
    queue = [target_obj]
    # Set to keep track of visited nodes (avoids redundant processing/cycles)
    visited = set()
    # Set to store source dependencies (nodes with no incoming edges)
    sources = set()
    
    while queue:
        current = queue.pop(0)  # FIFO for BFS; use pop() for DFS (LIFO)
        if current in visited:
            continue
        visited.add(current)
        
        # Get all dependencies for the current node
        dependencies = df[df['to'] == current]['from'].tolist()
        
        if not dependencies:
            # No dependencies = this is a source node
            sources.add(current)
        else:
            # Add all dependencies to the queue to process their dependencies
            queue.extend(dependencies)
    
    return list(sources)

# Test with target 'A'
print(find_all_source_dependencies('A'))  # Output: ['G', 'H']
# Test with target 'D'
print(find_all_source_dependencies('D'))  # Output: ['G', 'H']
# Test with target 'Z'
print(find_all_source_dependencies('Z'))  # Output: ['M']

How This Works #

• We use a queue to handle each element and its dependencies. BFS processes elements level by level, while switching to queue.pop() (LIFO) would give you a depth-first traversal—both work, just traverse in different orders.
• The visited set ensures we don't reprocess the same node multiple times, which is crucial if your dataset ever has cycles.
• For each node, we check if it has dependencies. If not, it's a source node and we add it to our result set. If it does have dependencies, we add those to the queue to keep traversing down the chain.

Why Your Original Code Failed #

• You overwrote obj immediately after finding one dependency, so you never went back to process other dependencies of the parent node (like F for D).
• You incorrectly modified the target list by setting target = target[-1], which turned it into a string instead of maintaining a collection of dependencies.

Solution 2: Recursive Depth-First Search (DFS) #

If you prefer a recursive approach (great for smaller datasets):

def find_sources_recursive(current, visited=None, sources=None):
    # Initialize sets on first call
    if visited is None:
        visited = set()
    if sources is None:
        sources = set()
    
    if current in visited:
        return sources
    visited.add(current)
    
    dependencies = df[df['to'] == current]['from'].tolist()
    if not dependencies:
        sources.add(current)
    else:
        # Recursively process each dependency
        for dep in dependencies:
            find_sources_recursive(dep, visited, sources)
    
    return list(sources)

print(find_sources_recursive('A'))  # Output: ['G', 'H']

Both methods will correctly capture all source dependencies by traversing every branch of the dependency tree. The iterative BFS approach is safer for larger datasets to avoid hitting recursion limits.

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