I have json data of supervisor to supervisee. I need to get it into a nested form to use lib_ggOrgChart. The issue is.... it is very difficult! Struggling to see a straightforward way to do this. Maybe recursion or something... Anyone have any ideas?
I know I can write some brute force code... but I'm hoping for a more elegant solution. Any help appretiated!
{
{"Supervisor_ID": 1, "Supervisee_ID": 2},
{"Supervisor_ID": 1, "Supervisee_ID": 3},
{"Supervisor_ID": 1, "Supervisee_ID": 4},
{"Supervisor_ID": 2, "Supervisee_ID": 5},
{"Supervisor_ID": 3, "Supervisee_ID": 6},
{"Supervisor_ID": 4, "Supervisee_ID": 7},
{"Supervisor_ID": 4, "Supervisee_ID": 8},
{"Supervisor_ID": 4, "Supervisee_ID": 9}
}
I need to get it into this form:
{
'root':{
'id': 1,
'children': {
{
'id': 2,
'children': {
{
'id': 5
}
}
},
{
'id': 3,
'children': {
{
'id': 6
}
}
},
{
'id': 4,
'children': {
{
'id': 7
},
{
'id': 8
},
{
'id': 9
}
}
}
}
}
This will do the trick.
/**
* @typedef TInput
* @property {number} Supervisor_ID Employee-ID of supervisor
* @property {number} Supervisee_ID Employee-ID of supervisee
*/
const input = [
{ Supervisor_ID: 1, Supervisee_ID: 2 },
{ Supervisor_ID: 1, Supervisee_ID: 3 },
{ Supervisor_ID: 1, Supervisee_ID: 4 },
{ Supervisor_ID: 2, Supervisee_ID: 5 },
{ Supervisor_ID: 3, Supervisee_ID: 6 },
{ Supervisor_ID: 4, Supervisee_ID: 7 },
{ Supervisor_ID: 4, Supervisee_ID: 8 },
{ Supervisor_ID: 4, Supervisee_ID: 9 },
];
/**
* Create organization tree from given input.
* @param {TInput[]} input input
* @returns {Map<number, Set<number>>} OrgTree
*/
function createOrgTree(input) {
const rootNodes = new Map();
input.forEach((relation) => {
if (rootNodes.has(relation.Supervisor_ID)) {
rootNodes.get(relation.Supervisor_ID).add(relation.Supervisee_ID);
} else {
// I am using a set here to make sure there are no duplicate entries
// but probably not necessary to use it as there should be no duplicates -> use array instead
const children = new Set();
children.add(relation.Supervisee_ID);
rootNodes.set(relation.Supervisor_ID, children);
}
});
return rootNodes;
}
/**
* Creates OrgChart for all employees.
* @param {TInput[]} input input
* @returns {Object} OrgChart
*/
function createOrgChartAllEmployees(input) {
const orgTree = createOrgTree(input);
// loop over all entries here
const endResult = [...orgTree.entries()].map(([parent, children]) => {
return buildEmployee(parent, children, orgTree);
});
return endResult;
}
/**
* Creates OrgChart for a given Employee ID.
* @param {TInput[]} input input
* @param {number} empId Employee ID
* @returns {Object} OrgChart
*/
function createOrgChartForEmployee(input, empId) {
const orgTree = createOrgTree(input);
if (!orgTree.has(empId)) {
console.error(`Employee-ID ${empId} does not exist`);
return null;
}
return buildEmployee(empId, orgTree.get(empId), orgTree);
}
/**
* Recursive function to build an Employee with all their children.
* @param {number} parent Supervisor ID
* @param {Set<number>} children Supervisee IDs
* @param {Map<number, Set<number>>} orgTree Lookup table for parents and children
*/
function buildEmployee(parent, children, orgTree) {
// Base case: recursion ends here
if (children === undefined) {
return {
id: parent,
};
}
// recursive call
// children will be the new parent and lookup the children of that child node in rootChodes
const childArray = [...children.entries()].map(([child, child2]) =>
buildEmployee(child, orgTree.get(child), orgTree)
);
return {
id: parent,
children: childArray,
};
}
/**
* Pretty-print organization chart.
* @param {Object} orgChart OrgChart
* @param {string} title title for OrgChart
*/
function printOrgChart(orgChart, title) {
console.log(`
-------------------------
OrgChart: ${title}
-------------------------
`);
console.log(JSON.stringify(orgChart, null, 4));
}
// this is I believe what you want
// OrgChart for Employee with ID 1 (CEO?)
const ceoOrgChart = createOrgChartForEmployee(input, 1);
printOrgChart(ceoOrgChart, "CEO");
const allEmployeeChart = createOrgChartAllEmployees(input);
printOrgChart(allEmployeeChart, "All Employees");First using your input I am creating an OrgTree which is actually a Map<number, Set<number>> and maps each employee ID to the set of employee IDs, which the person the employee ID belongs to supervises.
This is the foundation for the next step.
Given n relations (Supervisor => Supervisee) and constant lookup time for Set and Map this takes O(n).
Consider the function createOrgChartForEmployee() which creates the OrgChart for a given Employee.
Here we first build the OrgTree, as described above, then start at the given employee i. e. lookup his/ her children and then call buildEmployee().
That's the start of the recursion. In buildEmployee() we need to check if children are undefined, this does happen for employees who themselves do not supervise any employees. In that case we just return the ID of the Employee. This is our base case and ends the recursion.
Now, all other employees will have employees to supervise, so recursively call buildEmployee() on all children and map the result of every buildEmployee() call into an array that contains all children and return that array.
There are some special inputs to consider:
Note:
x -> ymeansx supervises y
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> ... -> n
This will result in a maximum tree depth of n - 1 = O(n).
Input: 1 -> 2 -> 3 -> 1
An input like this will result in an infinite loop and sooner or later in an error Maximum call stack size exceeded. But for OrgCharts this input should not be a concern.