使用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

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()    

Answer 2

你的输入是一个图，有很多Python库可以帮助你分析这个图。NetworkX就是其中一个。

你想要找的是图中的连通分量，而在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]]