match.c

A salient-boundary extraction software package based on the paper: S. Wang, T. Kubota, J. M. Siskind

#endif
{
    int augmented;
    expand_T *expands = &(srk->expands);
    int expands_max = srk->expands_max;
    node *c=n;
    node *stop = G->nodelist - 1;

#if PRINT_LEVEL
    printf ("   growtree no shrink %i\n", (int) (c - PG->nodelist));
    fflush (stdout);
#endif

    while (1) {
	if (c->label == PLUS) {
	    if ((augmented = checkout_node (G, c, fractional, srk)) > 0) {
		return augmented;
	    }
	} else {			/* MINUS node */
	    if (c->blossom_root != -1 && c->pi == 0) {
		if (expands->length < expands_max) {
		    expands->node[expands->length] = c - G->nodelist;
		    expands->length++;
		    if (expands->length == expands_max) {
			printf ("   WARNING: expands = expands_max = %i\n",
				expands_max);
			fflush (stdout);
		    }
		}
	    }
	}
	/* go to next c */
	if (c->child!=-1) {
	    c=PNODE(c->child);
	} else {
	    while (PNODE(c->sibling) == stop) {
		if (c == n) return 0; /* this if is for childless n */
		c = PNODE(c->parent);
		if (c == n) return 0;
	    }
	    c = PNODE(c->sibling);
	}
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int grow_tree (graph *G, node *n, int fractional, stats *scount,
                      srkstuff *srk, int *found_aug)
#else
extern int grow_tree (G, n, fractional, scount, srk, found_aug)
graph *G;
node *n;
int fractional;
stats *scount;
srkstuff *srk;
int *found_aug;
#endif
{
    int i, size;
    node *node_i, *node_j, *node_k, *newnode;
    edge *e;
    shrink_ary_T *ary = srk->shrinks.ary;
    expand_T *expands = &(srk->expands);
    int *shrinks_ = srk->shrinks_;
    shrink_T *shrinks = &(srk->shrinks);
    int old_shrinks_len;

    *found_aug = 0;

    do {
        FIND_SURFACE (n);
	shrinks->length = 0;
	expands->length = 0;

	if (grow_tree_no_shrink (G, n, fractional, srk)) {
            *found_aug = 1;
	    return 0;         
        }

        /* found no new match edge, so do shrinks */

        while (shrinks->length) {
            old_shrinks_len = shrinks->length;
            if (shrinks->length > 4) {   
                /* build buckets for all different sizes */
                for (i = 0; i < SHRINKS_SIZE; i++)
                    shrinks_[i] = -1;
                for (i = 0; i < shrinks->length; i++) {
                    size = ary[i].size;
                    if (size >= SHRINKS_SIZE)
                        size = SHRINKS_SIZE - 1;
                    if (shrinks_[size] == -1) {
                        shrinks_[size] = i;
                        ary[i].next = -1;
                    } else {
                        ary[i].next = shrinks_[size];
                        shrinks_[size] = i;
                    }
                }
                for (size = SHRINKS_SIZE - 1; size >= 3; size -= 2) {
                    for (i = shrinks_[size]; i != -1; i = ary[i].next) {
                        node_i = PNODE(ary[i].node_i);
                        node_j = PNODE(ary[i].node_j);
                        node_k = PNODE(ary[i].node_k);
                        e = PEDGE(ary[i].edge);
                        FIND_SURFACE (node_i);
                        FIND_SURFACE (node_j);
                        FIND_SURFACE (node_k);
                        if (node_i != node_j) {
                            newnode = shrink_blossom (G, node_i, node_j,
                                                      node_k, e, scount);
                            if ((checkout_node(G,newnode,fractional,srk)) >0) {
                                *found_aug = 1;
                                return 0;
                            }
                        }
                    }
                }
            } else {      /* just do all of the stupid shrinks */
                for (i = 0; i < shrinks->length; i++) {
                    node_i = PNODE(ary[i].node_i);
                    node_j = PNODE(ary[i].node_j);
                    node_k = PNODE(ary[i].node_k);
                    e = PEDGE(ary[i].edge);
                    FIND_SURFACE (node_i);
                    FIND_SURFACE (node_j);
                    FIND_SURFACE (node_k);
                    if (node_i != node_j) {
                        newnode = shrink_blossom (G, node_i, node_j,
                                                  node_k, e, scount);
                        if ((checkout_node (G, newnode, fractional, srk)) > 0) {
                            *found_aug = 1;
                            return 0;
                        }
                    }
                }
            }
            if (shrinks->length > old_shrinks_len) {
                size = shrinks->length - old_shrinks_len;
                for (i = 0; i < size; i++) {
                    ary[i].node_i = ary[i + old_shrinks_len].node_i;
                    ary[i].node_j = ary[i + old_shrinks_len].node_j;
                    ary[i].node_k = ary[i + old_shrinks_len].node_k;
                    ary[i].edge = ary[i + old_shrinks_len].edge;
                    ary[i].size = ary[i + old_shrinks_len].size;
                }
                shrinks->length = size;
            } else {
                shrinks->length = 0; 
            }
        }
	for (i = 0; i < expands->length; i++) {
	    /* blossom_root != -1 is necessary because expand
	     * of this node might have happened here before */
	    /* blossom_parent == -1 is necessary because
	     * this node might be shrunk already */
	    if (G->nodelist[expands->node[i]].blossom_root != -1 &&
                G->nodelist[expands->node[i]].blossom_parent == -1) {
		if (expand_blossom (G, G->nodelist+expands->node[i], scount)) {
                    fprintf (stderr, "expand_blossom failed\n");
                    return 1;
                }
	    }
	}
    } while (expands->length > 0);
    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern int apply_dual_change (graph *G, node *n, int delta)
#else
extern int apply_dual_change (G, n, delta)
graph *G;
node *n;
int delta;
#endif
{
    int ei;
    edge *e;
    node *c=n;
    node *stop = G->nodelist - 1;

    if (delta == INTEGER_MAX) {
	fprintf (stderr, "\ndelta=Infinity, node=%i\n", (int) (n-G->nodelist));
	fprintf (stderr, "There seems to be no perfect matching\n");
    }

    while (1) {
	if (c->label == PLUS) {
            c->hit = 1;
	    c->pi += delta;
	    for (ei = c->edg_list; ei != -1; ei = e->ptrs[ei % 2]) {
		e = PEDGE(ei/2);
		e->slack -= delta;
	    }
	} else if (c->label == MINUS) {
	    c->pi -= delta;
	    for (ei = c->edg_list; ei != -1; ei = e->ptrs[ei % 2]) {
		e = PEDGE(ei/2);
		e->slack += delta;
	    }
	}

	/* go to next c */

	if (c->child != -1) {
	    c = PNODE(c->child);
	} else {
	    while (PNODE(c->sibling) == stop) {
		if (c == n) return 0; /* this if is for childless n */
		c = PNODE(c->parent);
		if (c == n) return 0;
	    }
	    c = PNODE(c->sibling);
	}
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int find_single_dual_change (graph *G, node *n)
#else
extern int find_single_dual_change (G, n)
graph *G;
node *n;
#endif
{
    edge *e;
    int ei;
    int lab;
    int delta;
    node *c = n;
    node *stop = G->nodelist - 1;

#if PRINT_LEVEL
    printf (" %i", (int) (n - PG->nodelist));
    fflush (stdout);
#endif

    delta = INTEGER_MAX;

    while (1) {
	if (c->label == PLUS) {
	    for (ei = c->edg_list; ei != -1; ei = e->ptrs[ei % 2]) {
		e = PEDGE(ei/2);
		if (e->slack < 2 * delta) {
		    lab = OTHEREND (e, c, G->nodelist)->label;
		    if (lab == PLUS) {
			delta = e->slack / 2;
		    } else if (lab == NIX) {
			if (e->slack < delta) {
			    delta = e->slack;
			}
		    }
		}
	    }
	} else if (c->label == MINUS) {
	    if (c->blossom_root != -1 && c->pi < delta) {
		delta = c->pi;
	    }
	}

	/* go to next c */

	if (c->child != -1) {
	    c = PNODE(c->child);
	} else {
	    while (PNODE(c->sibling) == stop) {
		if (c == n) return delta ; /* this if is for childless n */
		c = PNODE(c->parent);
		if (c == n) return delta;
	    }
	    c = PNODE(c->sibling);
	}
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int find_dual_change_forest (graph *G, node *n)
#else
extern int find_dual_change_forest (G, n)
graph *G;
node *n;
#endif
{
    edge *e;
    int ei;
    int delta;
    nodeptr *roots = G->roots;
    node *c = n, *o;
    node *stop = G->nodelist - 1;

#if PRINT_LEVEL
    printf (" %i", (int) (c - PG->nodelist));
    fflush (stdout);
#endif

    delta = INTEGER_MAX;

    while (1) {
	if (c->label == PLUS) {
	    for (ei = c->edg_list; ei != -1; ei = e->ptrs[ei % 2]) {
		e = PEDGE(ei/2);
		o = OTHEREND (e, c, G->nodelist);
		switch (o->label) {
#ifdef GREEDY_DUAL_CHANGE
                case PLUS:
                    if (roots[c->tree_root].dad != roots[o->tree_root].dad ) {
                        /* two trees, not connected with vereinigung */
                        if (roots[o->tree_root].tree_processed) {
                            if (delta > e->slack -
                                        roots[roots[o->tree_root].dad].delta) {
                                delta = e->slack -
                                        roots[roots[o->tree_root].dad].delta;
                            }
                        } else {
                            if (e->slack < delta) {
                                delta = e->slack;
                            }
                        }
                    } else {
                        if (e->slack < 2 * delta) {
                            delta = e->slack / 2;
                        }
                    }
                    break;
                case NIX:
                    if (e->slack < delta) {
                        delta = e->slack;
                    }
                    break;
                case MINUS:
                    if (roots[c->tree_root].dad != roots[o->tree_root].dad) {
                        /* two trees, not connected with vereinigung */
                        if (roots[o->tree_root].tree_processed) { 
                            if (delta > e->slack +
                                        roots[roots[o->tree_root].dad].delta) {
                                delta = e->slack +
                                        roots[roots[o->tree_root].dad].delta;
                            }
                        } else {
                            if (e->slack < delta ) {
                                delta = e->slack;
                            }
                        }
                    }
                }
#else /* GREEDY_DUAL_CHANGE */
		case PLUS:
		    if (e->slack < 2 * delta) {
		        delta = e->slack / 2;
		    }
		    break;
		case NIX:
		    if (e->slack < delta) {
			delta = e->slack;
		    }
		    break;
		case MINUS:
		    if (roots[c->tree_root].dad != roots[o->tree_root].dad) { 
		        if (e->slack < delta ) {
			    delta = e->slack;
			}
		    }
		}
#endif /* GREEDY_DUAL_CHANGE */
	    }
	} else if (c->label == MINUS) {
	    if (c->blossom_root != -1 && c->pi <= delta) {
		delta = c->pi;
	    }
	}
	
	/* go to next c */

	if (c->child != -1) {
	    c = PNODE(c->child);
	} else {
	    while (PNODE(c->sibling) == stop) {
		if (c == n) return delta ; /* this is for childless n */
		c = PNODE(c->parent);
		if (c == n) return delta;
	    }
	    c = PNODE(c->sibling);
	}
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern void vereinigung (graph *G, int x, int y)
#else
extern void vereinigung (G, x, y)
graph *G;
int x, y;
#endif
{
    int xroot, yroot, dad;
    nodeptr *roots = G->roots;

#if PRINT_LEVEL
    printf (" vereinigung (%i,%i)", x, y); fflush (stdout);
#endif

    xroot = x;
    while (roots[xroot].dad >= 0)
	xroot = roots[xroot].dad;
    while (roots[x].dad >= 0) {
        dad = roots[x].dad;
        roots[x].dad = xroot;
        x = dad;
    }

    yroot = y;
    while (roots[yroot].dad >= 0)
	yroot = roots[yroot].dad;
    while (roots[y].dad >= 0) {
        dad = roots[y].dad;
        roots[y].dad = yroot;
        y = dad;
    }

    if (xroot != yroot) {
	if (roots[yroot].dad < roots[xroot].dad) {
            roots[yroot].dad += roots[xroot].dad; 
            roots[xroot].dad = yroot;
	} else {
	    roots[xroot].dad += roots[yroot].dad; 
	    roots[yroot].dad = xroot;
	}
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern void set_vereinigung (graph *G, node *n)
#else
extern void set_vereinigung (G, n)
graph *G;
node *n;
#endif
{
    edge *e;
    int ei;
    node *nod = G->nodelist;
    node *c = n;
    node *stop = G->nodelist - 1;

#if PRINT_LEVEL
    printf (" set_vereinigung (%i)", (int) (n - PG->nodelist));
    fflush (stdout);
#endif

    /* this is called only for PLUS nodes */

    while (1) {
	for (ei = c->edg_list; ei != -1; ei = e->ptrs[ei % 2]) {
	    e = PEDGE(ei/2);
	    if (nod[e->nod1].tree_root != nod[e->nod2].tree_root) {  
		if (e->slack == 0) {	
		    if (OTHEREND (e, c, nod)->label == MINUS) {
			vereinigung (G, nod[e->nod1].tree_root,
				        nod[e->nod2].tree_root);
		    }
		}
	    }
	}
	
	/* now check the chilren of c's children (these are PLUS nodes) */

	if (c->child != -1) {
	    c = PNODE(PNODE(c->child)->child);
	} else {
	    if (c == n) return; /* this if is for childless n */
	    c = PNODE(c->parent);
	    while (PNODE(c->sibling) == stop) {
		c = PNODE(c->parent);
		if (c == n) return;
		c = PNODE(c->parent);
	    }
	    c = PNODE(PNODE(c->sibling)->child);
	}
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int find_parity_sum (graph *G, int n)
#else
extern int find_parity_sum (G, n)
graph *G;
int n;
#endif
{
    node *v;
    int sum, ei;
    edge *e;