Build graph of organizational structure
To build the graph we are given the following information:
- The root (in this case John)
- A list of edges in the form (child, parent)
- Each node has a maximum of two children (implied from your example, however the code below works for any node having an arbitrary amount of children)
Note that in your question's example csv
data you seem to have mispelled felisa
as felia
. As a result these outputs aren't for the actual data you put up but rather the corrected version.
First we parse the csv
file, extracting the root and a list of edges:
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)
Output:
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']]
We use a defaultdict
from collections
(standard library) to represent a graph. We use the key
in the dictionary to represent the parent / manager, and the value
to represent a list of children / employees:
from collections import defaultdict
graph = defaultdict(list)
for child, parent in edges:
graph[parent].append(child)
print(graph)
Output:
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']})
This structure lets us get a list of children of a node with graph[node]
. We know that the root of the tree is the node that isn't present in any of the values in any of the lists. We also saved the root earlier.
I took "how can I build a DiGraph such that the following organizational structure can be shown" quite literally. Here's an example of how we can traverse this graph structure to build a string representation:
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)
Output:
john
|---tom
| |---ray
| | |---james
| | | |---henry
| | |---ben
| | |---rashad
| |---felisa
| |---pam
| |---mike
|---jill
|---tim
|---jim
|---bob