Tricky transformation of JSON data-CodePudding

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
                    }
                }
             }
        }
}

CodePudding user response：

I don't know if I properly understood what you're trying to achieve as I found the example I need to get it into this form kinda confusing (seems like first supervisor is wrapping all for some reason?). Anyways, take a shot at this:

// Supposing this is your array
const supervisorToSupervisee = [
    {"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}
];

// Backup variable to store the new object
const yourResult = { root: []};
// For of all the Supervisor_ID unique values
for (const id of [...new Set(supervisorToSupervisee.map((x) => x.Supervisor_ID))]) {
    // Pushing to the new object the id of the supervisor and a children 
    // with objects { id: Supervisee_ID }, filtering from the original array 
    // and mapping to the correct format
    yourResult.root.push({
        id,
        children: supervisorToSupervisee
            .filter((x) => x.Supervisor_ID == id)
            .map((x) => ({ id: x.Supervisee_ID }))
    });
}

// Smile
console.log(yourResult);

CodePudding user response：

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");

Key steps

Create OrgTree

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

Creating desired object structure

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 -> y means x supervises y

Degeneration to list:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> ... -> n

This will result in a maximum tree depth of n - 1 = O(n).

Infinite Loop

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.