Calculating maximum mutually independent set of nodes with iterative approach

Question

We start with an n-ary tree. Each branch represents "dependence" (i.e. parent is dependent on child). I need to find the maximal sum of mutually independent nodes.

Recursive solution is rather easy:

int calc_max()
{
    int child_max = 0;
    foreach (var n in nodes)
    {
        child_max += n.calc_max();
    }

    return Math.Max(this.value, child_max);
}

Now I am having rather hard time offering non recursive solution for this. This would require post order traversal. Iterative post order for binary tree is already answered here. But even with that solution I have problems removing recursion from this one.

Gene · Accepted Answer · 2019-11-17T21:39:20.603

I have a few SO answers that show how to translate any recursive expression of an algorithm into a non-recursive one.

Let's do it one more time.

I'll use C because it's clearer for this purpose:

int calc_max(NODE *node) {
  int child_sum = 0;
  for (int i = 0; i < node->n_children; ++i) 
    child_sum += calc_max(node->children[i]);
  return MAX(node->value, child_sum);
}

Now simulate the recursive call with an explicit stack, a variable that serves as the "return register," and goto to simulate the jump performed by a call and return instructions. Let some things in pseudocode for clarity.

int calc_max(NODE *node) {
  int rtn_val; // Simulated register for function return value.
 start:
  int child_sum = 0;
  for (int i = 0; i < node->n_children; ++i) {
    <<save params and locals on frame stack>>
    node = node->children[i];
    goto start;
   rtn:
    child_sum += rtn_val;
  }
  // Simulate using a register to return a result.
  int rtn_val = MAX(node->value, child_sum);
  if (<<frame stack isn't empty>>) {
    <<restore params and locals from frame stack>>
    goto rtn;
  }
  return rtn_val;
}

The params and locals that need to be saved are node, i, and child_sum. So we can fill in the pseudocode.

typedef struct node {
  struct node *children[8];
  int n_children, value;
} NODE;

#define MAX(A, B) ((A) > (B) ? A : B)

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
 start:
  child_sum = 0;
  for (i = 0; i < node->n_children; ++i) {
    stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
    node = node->children[i];
    goto start;
   rtn:
    child_sum += rtn_val;
  }
  rtn_val = MAX(node->value, child_sum);
  if (sp > 0) {
    --sp;
    node = stk[sp].node;
    i = stk[sp].i;
    child_sum = stk[sp].child_sum;
    goto rtn;
  }
  return rtn_val;
}

This ought to work fine. I have not tested it. The gotos aren't pretty, but with some algebra you can turn them into while or for loops if you like. Here are the steps.

Change for loop to while and move statements after rtn to execute before the goto rtn. Then rtn itself can be moved before the while:

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
 start:
  i = child_sum = 0;
 rtn:
  while (i < node->n_children) {
    stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
    node = node->children[i];
    goto start;
  }
  rtn_val = MAX(node->value, child_sum);
  if (sp > 0) {
    --sp;
    node = stk[sp].node;
    i = stk[sp].i;
    child_sum = stk[sp].child_sum;
    child_sum += rtn_val;
    ++i;
    goto rtn;
  }
  return rtn_val;
}

Now by copying i = child_sum = 0 we can move the target of goto start to rtn instead.

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
  i = child_sum = 0;
 rtn:
  while (i < node->n_children) {
    stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
    node = node->children[i];
    i = child_sum = 0;
    goto rtn;
  }
  rtn_val = MAX(node->value, child_sum);
  if (sp > 0) {
    --sp;
    node = stk[sp].node;
    i = stk[sp].i;
    child_sum = stk[sp].child_sum;
    child_sum += rtn_val;
    ++i;
    goto rtn;
  }
  return rtn_val;
}

Now note that the first goto rtn can be eliminated. The while loop does the same thing without it:

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp = 0;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];
  i = child_sum = 0;
 rtn:
  while (i < node->n_children) {
    stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
    node = node->children[i];
    i = child_sum = 0;
  }
  rtn_val = MAX(node->value, child_sum);
  if (sp > 0) {
    --sp;
    node = stk[sp].node;
    i = stk[sp].i;
    child_sum = stk[sp].child_sum;
    child_sum += rtn_val;
    ++i;
    goto rtn;
  }
  return rtn_val;
}

Finally we can replace the last goto rtn with an endless loop, where we return from the function (breaking out of the loop) except in the case where goto rtn would have looped:

int calc_max(NODE *node) {
  int i, child_sum, rtn_val, sp;
  struct stack_frame {
    NODE *node;
    int i, child_sum;
  } stk[1000];

  sp = i = child_sum = 0;
  while (1) {
    while (i < node->n_children) {
      stk[sp++] = (struct stack_frame){.node = node, .i = i, .child_sum = child_sum};
      node = node->children[i];
      i = child_sum = 0;
    }
    rtn_val = MAX(node->value, child_sum);
    if (sp <= 0) return rtn_val;
    node = stk[--sp].node;
    i = stk[sp].i + 1;
    child_sum = stk[sp].child_sum + rtn_val;
  }
}

I might easily have made a mistake along the way. I don't have a compiler at hand to do any testing. But the basic idea is sound, and the result ought to be pretty efficient. It compiles to 33 x86 instructions.

After you've done a few of these, the algebra tricks to get rid of goto fall into patterns. But there are general, automatic algorithms to do the same thing. It would be fairly simple to build a tool that would do this transformation automatically.

Now that the gotos are gone, you can translate back to your language of choice.

The nice thing about this method is you don't need to puzzle out the operational semantics of the specific algorithm. Just start with the recursive expression and simulate what the compiler does, then transform with algebra to get a form that looks nice. Except for silly errors, it must work.

Calculating maximum mutually independent set of nodes with iterative approach

1 Answers1