Algorithm to traverse graph with certain dependency/constraint-CodePudding

So I am building a operations pipeline that allows user to apply certain Data operations on dataframes. The operations are such that they may have "one-input-->two-outputs" or "one-input-->one-output" or "two-inputs-->one-output".

I need to traverse the graph from the starting points labelled as [S1, S2, S3, S4] and reach the end points The important thing to note is that in order to execute operation2, we need to have operation1 and operation5 already executed. similarly to execute operation7, operations 3 and 6 need to be already executed.

Note that this is simpler than a directed acyclic graph as we have clear start and end points and the flow is unidirectional [left-->right in the image]

It is known which operations are the starting points marked as S1,s2,s3,s4. I need to execute all operations and reach the terminal points. I just the need the pseudocode.

CodePudding user response：

This looks to be some kind of task scheduling problem, It is impossible to say exactly what kind or offer any concrete suggestion because the question is missing many important details, and the OP refuses to answer detailed questions.

However, there is a vast literature on task scheduling problems. A reasonable starting point would be https://en.wikipedia.org/wiki/Scheduling_(computing)

CodePudding user response：

// The index numbers are just for illustration
const operationsGraph = {
  0: [null, [1]],
  1: [[0], [2]],
  2: [[1, 5], [3]],
  3: [[2], [4, 7]],
  4: [[3], null],
  5: [null, [2]],
  6: [null, [7]],
  7: [[3, 6], [8]],
  8: [[7], null],
  9: [null, [10]],
  10: [[9], null],
};

// Convert the graph to an array
const operation = Object.values(operationsGraph);

// Create an array to keep track of the completed operations
const completed = Array(operation.length).fill(false);

/**
 * The algorithm works as follows:
 *
 *  1. move along path until (2 inputs needed)
 *  2. backtrack until base case
 *  3. continue in lowest completed order
 *
 *   [complete] <--- [current] ----> [complete]
 */

function traverse(pointer) {
  // if this step has been completed return
  if (completed[pointer]) return true;
  // extract the prev and next operations
  const prev = operation[pointer][0];
  const next = operation[pointer][1];
  // backtrack each previous operation
  prev?.forEach((op) => traverse(op));
  // if the previous step is complete and this operation
  // has been completed then mark as completed and print
  if (isComplete(prev) && completed[pointer] === false) {
    // update the completed flag
    completed[pointer] = true;
    // run the operation here
    console.log('running: ', pointer);
  }
  // iterate the next steps in the sequence
  next?.forEach((op) => traverse(op));
}

// helper function to check if a step is complete
function isComplete(step) {
  if (step === null) return true;
  return step.every((i) => completed[i]);
}

// run each of the sequences
function main() {
  const s1 = traverse(0);
  const s2 = traverse(5);
  const s3 = traverse(6);
  const s4 = traverse(9);
}

main()