使用Python遍歷父子數據集

Question

我有一個csv文件中的兩列數據集。這個數據集的目的是在兩個不同的id之間提供一個鏈接，如果它們屬於同一個人。例如（2,3,5-屬於1） 例如

1. COLA COLB 1 2 ; 1 3 ; 1 5 ; 2 6 ; 3 7 ; 9 10 

在上面的例子1被鏈接到2,3,5和2被鏈接到6和3被鏈接到7 我我試圖實現的是識別直接（2,3,5）或間接（6,7）鏈接到1的所有記錄，並且能夠說B列中的這些ID屬於列A中的同一個人，然後重複數據刪除或者新的列添加到這將有1填充用於鏈接到預期輸出的1個

實施例中的所有行的輸出文件

- colA colB GroupField 1 2 1; 1 3 1; 1 5 1 ; 
2 6 1 ;3 7 1; 9 10 9; 10 11 9 

如何解決這個問題？

到目前爲止，我已經能夠讀取文件並創建一個字典。我研究過使用Python集操作，但無法將它們與字典一起使用。

我研究過將字典轉換爲集合然後使用集合運算符來解集集合之間的關係，但無法在網上找到任何東西，也不確定這是否是解決此問題的正確方法。

Answer 1

您的輸入是graph，有many Python libraries可幫助您分析一個。 NetworkX就是其中之一。

您正在查看connected components的圖表，還有a number of functions in NetworkX找到它們。

一些代碼行，讓你開始：

import networkx as nx 

file_contents = "1 2 ; 1 3 ; 1 5 ; 2 6 ; 3 7 ; 9 10" 
lines = [item.strip() for item in file.split(";")] 
G = nx.parse_edgelist(lines, nodetype = int) 
components = nx.connected_components(G) 
# components now holds: 
# [[1, 2, 3, 5, 6, 7], [9, 10]] 

Answer 2

Logc謝謝你指着我在正確的方向。我能夠使用一點點的networkx解決這個問題，並且在強連通的組件上使用Tarjan的算法。以下是我的代碼： -

import networkx as nx 
def strongly_connected_components(graph): 
""" Find the strongly connected components in a graph using 
    Tarjan's algorithm. 

    graph should be a dictionary mapping node names to 
    lists of successor nodes. 
    """ 

    result = [ ] 
    stack = [ ] 
    low = { } 

def visit(node): 
    if node in low: return 

num = len(low) 
    low[node] = num 
    stack_pos = len(stack) 
    stack.append(node) 

    for successor in graph[node]: 
     visit(successor) 
     low[node] = min(low[node], low[successor]) 

    if num == low[node]: 
    component = tuple(stack[stack_pos:]) 
     del stack[stack_pos:] 
     result.append(component) 
    for item in component: 
     low[item] = len(graph) 

for node in graph: 
    visit(node) 

    return result 


def topological_sort(graph): 
    count = { } 
    for node in graph: 
     count[node] = 0 
    for node in graph: 
     for successor in graph[node]: 
       count[successor] += 1 

    ready = [ node for node in graph if count[node] == 0 ] 

    result = [ ] 
    while ready: 
     node = ready.pop(-1) 
     result.append(node) 

     for successor in graph[node]: 
      count[successor] -= 1 
      if count[successor] == 0: 
       ready.append(successor) 

return result 

def robust_topological_sort(graph): 
""" First identify strongly connected components, 
    then perform a topological sort on these components. """ 

components = strongly_connected_components(graph) 

node_component = { } 
for component in components: 
    for node in component: 
     node_component[node] = component 

component_graph = { } 
for component in components: 
    component_graph[component] = [ ] 

for node in graph: 
    node_c = node_component[node] 
    for successor in graph[node]: 
     successor_c = node_component[successor] 
     if node_c != successor_c: 
      component_graph[node_c].append(successor_c) 

return topological_sort(component_graph) 


if __name__ == '__main__': 
    print robust_topological_sort({ 
    0 : [1], 
    1 : [2], 
    2 : [1,3], 
    3 : [3], 
}) 

graph = nx.read_edgelist('input_filename', 
create_using=None,delimiter=',',nodetype=None,edgetype=None) 
results = strongly_connected_components(graph) 
f=open('output_filename','w') 
for item in results: 
    f.write(','.join(map(str,item))) 
    f.write('\n') 
f.close()