构建组织结构图

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

如何构建DiGraph,以便显示以下组织结构:

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

显然这是一个图形问题,但我在确定使用哪个结构时遇到问题(例如,最好是使用dict或构建自定义OrganizationalGraph对象等).任何帮助表示赞赏.

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

Answer 1

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

1. 根（在这种情况下是约翰）
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']]

我们使用defaultdictfrom collections（标准库）来表示图。我们使用key字典中的 来表示父/经理，使用value来表示孩子/员工的列表：

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]。我们知道树的根节点是不存在于任何列表中的任何值中的节点。我们之前也保存了根。

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

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