- /* all contains all nodes not removed in this qn */
- all_size = 0;
- for (i=0; i<ou->node_count; ++i)
- if (!qnode_are_conflicting(qn, ou->nodes[i], ou->nodes[i]))
- all[all_size++] = ou->nodes[i];
-
- /* which[i] says which element to take out of all[] and put into curr[i] */
- which = alloca(all_size*sizeof(*which));
- for (curr_size=0; curr_size<all_size; ++curr_size)
- which[curr_size] = curr_size;
-
- /* stores the currently examined set */
- curr = alloca(all_size*sizeof(*curr));
-
- while (1) { /* this loop will terminate because at least a single node'll be a max indep. set */
- /* build current set */
- for (i=0; i<curr_size; ++i)
- curr[i] = all[which[all_size-curr_size+i]];
-
- /* check current set */
- for (i=0; i<curr_size; ++i)
- for (o=i+1; o<curr_size; ++o)
- if (qnode_are_conflicting(qn, curr[i], curr[o]))
- goto conflict_found;
-
- /* We had no conflict. This is the max indep. set */
- qn->mis_size = curr_size;
- for (i=0; i<curr_size; ++i)
- qn->mis[i] = curr[i];
- return;