CODEWITHSUNDEEP
arrayssortingnestedsequence
Pat Binge
Pat Binge

Reputation: 13

Sorting interdependant objects (in-line process) with javascript / node

I've been breaking my head over this for quite some time and hope to get some support here. I have an array containing multiple objects.

Every object represents a production process comprised of subprocesses made up of inputs and outputs. These processes run in line. Meaning, that the output of one process will become the input for another process. However, I have no idea in which order.

I am trying to figure out the sequence the main processes need to be run in. Our system can't tell me and now I have 5000interdependant processes that need sorting.

Here an example of how the array is formatted. As you can see Inputs have an origin flag. At least we know whether an input is taken from a warehouse or is produced somewhere upstream. If I were to sort this manually the order would be Process3, then Process 2, then Process 1. Process 1 requires the material with the id="ID3" as input, which is produced in process 2 (under subprocess 2). While Process 2 requires the material "ID5" which is produced in process 3. Anybody have an idea how to solve this nightmare?

Thank you sooo much!!!

[
  {
    processID: "1",
    subprocesses: [
      {
        subprocessID: "1",
        outputs: [
          {
            id: "ID1",
            name: "alpha",
            ratio: "1",
          },
        ],
        inputs: [
          {
            type: "rawMaterial",
            id: "ID2",
            ratio: "0.7623",
          },
          {
            type: "processOutput",
            id: "ID3",
            ratio: "0.6552",
          },
        ],
      },
    ],
  },
  {
    processID: "2",
    subprocesses: [
      {
        subprocessID: "1",
        outputs: [
          {
            id: "ID22",
            name: "beta)",
            ratio: "1",
          },
        ],
        inputs: [
          {
            type: "processOutput",
            id: "ID5",
            ratio: "0.0034",
          },
        ],
      },
      {
        subprocessID: "2",
        outputs: [
          {
            id: "ID3",
            name: "gamma",
            ratio: "1",
          },
        ],
        inputs: [
          {
            type: "rawMaterial",
            id: "ID10",
            ratio: "0.0034",
          },
        ],
      },
    ],
  },
  {
    processID: "3",
    subprocesses: [
      {
        subprocessID: "1",
        outputs: [
          {
            id: "ID5",
            name: "omega",
            ratio: "1",
          },
        ],
        inputs: [
          {
            type: "rawMaterial",
            id: "ID111",
            ratio: "0.3018",
          },
        ],
      },
    ],
  },
]

Upvotes: 1

Views: 104

Answers (1)

AKX
AKX

Reputation: 169338

As I said in the comments, what you seem to have is a graph theory problem :-)

  • The entire thingamabob is a directed acyclic graph – or in this case, basically a dependency tree.
  • Each subprocess as a node in the graph.
  • Edges point from processes outputting resources to processes requiring those resources.
  • The topological ordering of the graph is the order in which the processes need to be complete.

This solution requires the toposort package for the heavy graph lifting.

const processes = require("./processes"); // Data from original post
const toposort = require("toposort");

const processInputs = {}; // Inputs required per subprocess
const outputIdToProcessIds = {}; // Map output IDs to processes that create them
const predecessorMap = {}; // Map process IDs to the node(s) that need to run immediately before

// Step 1: massaging the input data.

// Loop over top-level processes...
processes.forEach((proc) => {
  // and each subprocess within.
  proc.subprocesses.forEach((subproc) => {
    // Compute an unique ID for the process-subprocess.
    const procId = `${proc.processID}/${subproc.subprocessID}`;
    // Add it to our map of predecessors; this way each process, whether it's needed or not,
    // is in the predecessor map.
    // This also adds a "virtual" "start" predecessor for each node; it's not strictly necessary.
    predecessorMap[procId] = ["start"];

    // Gather the required inputs for each process.
    subproc.inputs.forEach((input) => {
      (processInputs[procId] = processInputs[procId] || []).push(input);
    });

    // Gather an inverse mapping of output ids to processes that create them.
    subproc.outputs.forEach((output) => {
      (outputIdToProcessIds[output.id] = outputIdToProcessIds[output.id] || []).push(procId);
    });
  });
});

// Step 2: massaging the processed data.

// Loop over the processes that actually do need inputs.
Object.entries(processInputs).forEach(([pid, inputs]) => {
  // For each input...
  inputs.forEach((input) => {
    // ... find the process IDs that can create these outputs.
    const pidsForInput = outputIdToProcessIds[input.id] ?? [];
    if (!pidsForInput.length) {
      console.warn(`There is no process that would output ${input.id} required by ${pid}`);
    } else {
      // Push the first one of them into the predecessors list for this process.
      // This might need special handling if it's possible for a resource to be output
      // by multiple processes.
      predecessorMap[pid].push(pidsForInput[0]);
    }
  });
});

// Step 3: creating graph data.
const allEdges = []; // All edges in from-to order
// Walk over the predecessor map...
Object.entries(predecessorMap).forEach(([to, froms]) => {
  // and each predecessor of each node, and push them into the full list of edges
  froms.forEach((from) => allEdges.push([from, to]));
});

console.log(allEdges);

// Step 4: sort!
// Run the toposort and print the order!
toposort(allEdges).forEach((node) => {
  console.log(node);
});

Since the data in the original post is incomplete, the program warns you about just that, but doesn't outright fail.

The solution will be incomplete, too, of course.

The output is:

There is no process that would output ID2 required by 1/1
There is no process that would output ID10 required by 2/2
There is no process that would output ID111 required by 3/1

followed by the graph's edges

[
  [ 'start', '1/1' ],
  [ '2/2', '1/1' ],
  [ 'start', '2/1' ],
  [ '3/1', '2/1' ],
  [ 'start', '2/2' ],
  [ 'start', '3/1' ]
]

and finally the "execution order" required (with the virtual "start" node):

start
2/2
1/1
3/1
2/1

So, the order is:

  • process 2 subprocess 2 done
  • process 1 subprocess 1 done
  • process 3 subprocess 1 done
  • process 2 subprocess 1 done

Upvotes: 1

Related Questions