python - 构建组织结构图

Question

我在编写可以读取员工/经理的 CSV 并输出包含员工/经理关系的有向图的算法时遇到问题。

我的 foobar 示例:给定以下 CSV 文件

john,
jill, john
tom, john
tim, jill
felisa, tom
ray, tom
bob, tim
jim, tim
pam, felisa
ben, ray
james, ray
mike, pam
rashad, ben
henry, james

我怎样才能构建一个有向图来显示以下组织结构:

         john
        /    \
     jill    tom
     /       /  \
   tim   felisa  ray
 /  \      /     /  \
bob jim   pam  ben  james
          /     /       \
        mike   rashad    henry

显然这是一个图形问题，但我无法决定使用哪种结构(例如，最好使用 dict 还是构建自定义 OrganizationalGraph 对象等)。感谢您的帮助。

选择的语言并不是很重要(虽然我们可以简单地说 Python [相应地更新标签])，我更重要的是试图理解这类问题的基本原理(即递归与递归)。迭代，使用 set() 存储经理的直接下属与使用仅抽象数据结构)。 最后，不，使用标准库之外的任何包都是行不通的。

Answer 1

为了构建图表，我们获得了以下信息:

1. 根(在本例中为 John)
2. 表单中的边列表(子、父)
3. 每个节点最多有两个子节点(从您的示例中暗示，但是下面的代码适用于具有任意数量子节点的任何节点)

请注意，在您问题的示例 csv 数据中，您似乎将 felisa 拼错为 felia。因此，这些输出不是针对您提供的实际数据，而是针对更正后的版本。首先我们解析 csv 文件，提取根和边列表:

import csv

with open('data.csv') as f:
    f = list(csv.reader(f, skipinitialspace=True))
    root, *edges = f
    root = root[0]

print(root)
print(edges)

输出:

john 
[['jill', 'john'], ['tom', 'john'], ['tim', 'jill'], ['felisa', 'tom'], ['ray', 'tom'], ['bob', 'tim'], ['jim', 'tim'], ['pam', 'felisa'], ['ben', 'ray'], ['james', 'ray'], ['mike', 'pam'], ['rashad', 'ben'], ['henry', 'james']]

我们使用collections(标准库)中的defaultdict 来表示图形。我们用字典中的key代表父/经理，用value代表 child /员工列表:

from collections import defaultdict

graph = defaultdict(list)
for child, parent in edges:
    graph[parent].append(child)

print(graph)

输出:

defaultdict(<class 'list'>, {'john': ['jill', 'tom'], 'jill': ['tim'], 'tom': ['felisa', 'ray'], 'tim': ['bob', 'jim'], 'felisa': ['pam'], 'ray': ['ben', 'james'], 'pam': ['mike'], 'ben': ['rashad'], 'james': ['henry']})

这个结构让我们可以通过 graph[node] 获得一个节点的子节点列表。我们知道树的根是不存在于任何列表中的任何值中的节点。我们之前也保存了 root。

我从字面上理解了“我如何构建一个有向图以便可以显示以下组织结构”。这是我们如何遍历此图结构以构建字符串表示的示例:

res = ''
stack = [(root, 0)]
needed_lines = defaultdict(int)

while stack:
    node, level = stack.pop()
    prev_level = level-4
    res += '\n' + ''.join('|' if i in needed_lines else
                          ' ' if i <= level-4 else
                          '-' for i in range(level)) + node
    for child in graph[node]:
        stack.append((child, level+4))

    needed_lines[level] += len(graph[node])
    needed_lines[prev_level] -=1
    if needed_lines[prev_level] == 0: del needed_lines[prev_level]

print(res)

输出:

john
|---tom
|   |---ray
|   |   |---james
|   |   |   |---henry
|   |   |---ben
|   |       |---rashad
|   |---felisa
|       |---pam
|           |---mike
|---jill
    |---tim
        |---jim
        |---bob