52     add_node(int v, CCtsp_qsparsegroup *qs, CCtsp_lpgraph *g, int *pnzlist),
53     sub_node(int v, CCtsp_qsparsegroup *qs, CCtsp_lpgraph *g, int *pnzlist),
54     update_queues (int v, CCtsp_qsparsegroup *qs, CCtsp_lpgraph *g);
86     CCtsp_qsparsegroup *qs;  local
92     qs = *pqs;
93     qs->add_queue = (CCdheap *) NULL;
94     qs->sub_queue = (CCdheap *) NULL;
95     qs->count_m1 = (int *) NULL;
96     qs->count_non0 = (int *) NULL;
97     qs->count_1 = (int *) NULL;
98     qs->on_add_queue = (int *) NULL;
99     qs->on_sub_queue = (int *) NULL;
100     qs->mults = (int *) NULL;
102     qs->add_queue = CC_SAFE_MALLOC (1, CCdheap);
103     qs->sub_queue = CC_SAFE_MALLOC (1, CCdheap);
104     if (!qs->add_queue || !qs->sub_queue) {
108     if (CCutil_dheap_init (qs->add_queue, ncount)) {
112     if (CCutil_dheap_init (qs->sub_queue, ncount)) {
117     qs->count_m1 = CC_SAFE_MALLOC (ncount, int);
118     qs->count_non0 = CC_SAFE_MALLOC (ncount, int);
119     qs->count_1 = CC_SAFE_MALLOC (ncount, int);
120     qs->on_add_queue = CC_SAFE_MALLOC (ncount, int);
121     qs->on_sub_queue = CC_SAFE_MALLOC (ncount, int);
122     qs->mults = CC_SAFE_MALLOC (ncount, int);
123     if (!qs->count_m1 || !qs->count_non0 || !qs->count_1 ||
124         !qs->on_add_queue || !qs->on_sub_queue || !qs->mults) {
130         qs->count_m1[i] = 0;
131         qs->count_non0[i] = 0;
132         qs->count_1[i] = 0;
133         qs->on_add_queue[i] = 0;
134         qs->on_sub_queue[i] = 0;
135         qs->mults[i] = 0;
182     CCtsp_qsparsegroup *qs;  local
198     qs = *pqs;
199     count_non0 = qs->count_non0;
200     count_1 = qs->count_1;
201     count_m1 = qs->count_m1;
221                 update_queues(edges[e].ends[0], qs, g);
225                 update_queues(edges[e].ends[1], qs, g);
233         v = queue_max (qs->add_queue);
234         w = queue_max (qs->sub_queue);
240             queue_delete (qs->add_queue, v);
241             qs->on_add_queue[v] = 0;
242             (qs->mults[v])++;
243             add_node (v, qs, g, pnzlist);
246             queue_delete (qs->sub_queue, w);
247             qs->on_sub_queue[w] = 0;
248             (qs->mults[w])--;
249             sub_node (w, qs, g, pnzlist);
256         if (qs->mults[edges[e].ends[0]] &&
261         if (qs->mults[edges[e].ends[1]] &&
277             if (qs->mults[edges[e].ends[0]]) {
279                 t = qs->mults[edges[e].ends[0]];
284                 qs->mults[edges[e].ends[0]] = 0;
286             if (qs->mults[edges[e].ends[1]]) {
288                 t = qs->mults[edges[e].ends[1]];
293                 qs->mults[edges[e].ends[1]] = 0;
300         qs->count_m1[edges[e].ends[0]] = 0;
301         qs->count_non0[edges[e].ends[0]] = 0;
302         qs->count_1[edges[e].ends[0]] = 0;
303         qs->count_m1[edges[e].ends[1]] = 0;
304         qs->count_non0[edges[e].ends[1]] = 0;
305         qs->count_1[edges[e].ends[1]] = 0;
369 static void add_node (int v, CCtsp_qsparsegroup *qs, CCtsp_lpgraph *g,  in add_node()  argument
372 static void add_node (v, qs, g, pnzlist)  in add_node()
374 CCtsp_qsparsegroup *qs;
391             qs->count_non0[v]++;
392             qs->count_1[v]++;
393             qs->count_non0[w]++;
394             qs->count_1[w]++;
395             update_queues (w, qs, g);
397             qs->count_1[v]--;
398             qs->count_1[w]--;
399             update_queues (w, qs, g);
401             qs->count_m1[v]--;
402             qs->count_non0[v]--;
403             qs->count_m1[w]--;
404             qs->count_non0[w]--;
405             update_queues (w, qs, g);
407             qs->count_m1[v]++;
408             qs->count_m1[w]++;
409             update_queues (w, qs, g);
413     update_queues (v, qs, g);
417 static void sub_node (int v, CCtsp_qsparsegroup *qs, CCtsp_lpgraph *g,  in sub_node()  argument
420 static void sub_node (v, qs, g, pnzlist)  in sub_node()
422 CCtsp_qsparsegroup *qs;
439             qs->count_non0[v]++;
440             qs->count_m1[v]++;
441             qs->count_non0[w]++;
442             qs->count_m1[w]++;
443             update_queues (w, qs, g);
445             qs->count_m1[v]--;
446             qs->count_m1[w]--;
447             update_queues (w, qs, g);
449             qs->count_1[v]--;
450             qs->count_non0[v]--;
451             qs->count_1[w]--;
452             qs->count_non0[w]--;
453             update_queues (w, qs, g);
455             qs->count_1[v]++;
456             qs->count_1[w]++;
457             update_queues (w, qs, g);
461     update_queues (v, qs, g);
468 static void update_queues (int v, CCtsp_qsparsegroup *qs, CCtsp_lpgraph *g)  in update_queues()  argument
470 static void update_queues (v, qs, g)  in update_queues()
472 CCtsp_qsparsegroup *qs;
476     if (qs->count_m1[v] - (g->nodes[v].deg - qs->count_non0[v]) > 0) {
477         if (qs->on_add_queue[v]) {
478             queue_keychange (qs->add_queue, v,
479                   qs->count_m1[v] - (g->nodes[v].deg - qs->count_non0[v]));
481             queue_add (qs->add_queue, v,
482                   qs->count_m1[v] - (g->nodes[v].deg - qs->count_non0[v]));
483             qs->on_add_queue[v] = 1;
486         if (qs->on_add_queue[v]) {
487             queue_delete (qs->add_queue, v);
488             qs->on_add_queue[v] = 0;
492     if (qs->count_1[v] - (g->nodes[v].deg - qs->count_non0[v]) > 0) {
493         if (qs->on_sub_queue[v]) {
494             queue_keychange (qs->sub_queue, v,
495                   qs->count_1[v] - (g->nodes[v].deg - qs->count_non0[v]));
497             queue_add (qs->sub_queue, v,
498                   qs->count_1[v] - (g->nodes[v].deg - qs->count_non0[v]));
499             qs->on_sub_queue[v] = 1;
502         if (qs->on_sub_queue[v]) {
503             queue_delete (qs->sub_queue, v);
504             qs->on_sub_queue[v] = 0;