match.c

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

    do {
	if (init (G, &srk)) {
            fprintf (stderr, "init failed\n");
            goto CLEANUP;
        }

        scount.expand_count = 0;
        scount.shrink_count = 0;
        scount.dualchange_count = 0;
        scount.dualzero_count = 0;
	if (match_main_frac (G, &scount, &srk)) {
            fprintf (stderr, "match_main_frac failed\n");
            goto CLEANUP;
        }

	if (make_match (G)) {
            fprintf (stderr, "make_match failed\n");
            fflush (stdout);
        }
        scount.expand_count = 0;
        scount.shrink_count = 0;
        scount.dualchange_count = 0;
        scount.dualzero_count = 0;
	if (match_main (G, &scount, &srk, use_all_trees)) {
            fprintf (stderr, "match_main failed\n");
            goto CLEANUP;
        }

        dual_match_len (G, 0, &val);

    } while (!finished);

    adjust_match (G);

CLEANUP:

    CC_IFFREE (srk.expands.node, int);
    CC_IFFREE (srk.shrinks.ary, shrink_ary_T); 

    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern int init (graph *G, srkstuff *srk)
#else
extern int init (G, srk)
graph *G;
srkstuff *srk;
#endif
{
    int i, count;
    node *n;
    edge *e;
    int ei;
    int delta;
    node *nodelist = G->nodelist;
    int   ncount = G->nnodes;
    int   ecount = G->nedges;

    /* set all the pi s */
    for (i = 0; i < ncount; i++)
	nodelist[i].pi = INTEGER_MAX;
    for (i = ncount; i <= 3 * ncount / 2; i++)
	nodelist[i].pi = 0;

    for (i = 0, e = G->edgelist; i < ecount; i++, e++) {
	if (nodelist[e->nod1].pi > e->slack) {
	    nodelist[e->nod1].pi = e->slack;
	}
	if (nodelist[e->nod2].pi > e->slack) {
	    nodelist[e->nod2].pi = e->slack;
	}
    }

    for (i = 0; i < ncount; i++)
	nodelist[i].pi /= 2;

    /* calculate the slacks with the pi's and set rest to zero/nothing */

    for (i = 0, e = G->edgelist; i < ecount; i++, e++) {
	e->slack = e->slack - nodelist[e->nod1].pi - nodelist[e->nod2].pi;
	e->x = 0;
    }

    for (i = 0, n = nodelist; i <= 3 * ncount / 2; i++, n++) {
	n->child = -1;
	n->sibling = -1;
	n->parent = -1;
	n->label = NIX;
	n->parent_edge = -1;
	n->matched_edge = -1;
	n->status = UNMATCHED;
	n->blossom_root = -1;
	n->blossom_next = -1;
	n->blossom_next_edge = -1;
	n->blossom_parent = -1;
	n->tree_root = -1;
        n->hit = 0;
    }
#if 0
    /* Take all 0-slack edges directly, old version */
    count = 0;
    for (i = 0, e = G->edgelist; i < ecount; i++, e++) {
	if (e->slack == 0) {
	    if ((nodelist[e->nod1].status == UNMATCHED) &&
                (nodelist[e->nod2].status == UNMATCHED)) {
		e->x = 1;
		nodelist[e->nod1].matched_edge = i;
		nodelist[e->nod2].matched_edge = i;
		nodelist[e->nod1].status = MATCHED;
		nodelist[e->nod2].status = MATCHED;
		count += 2;
	    }
	}
    }
#else
    /* Take all 0-slack edges directly & make better pi, new version */
    count = 0;
    for (i = 0, n = nodelist; i < ncount; i++, n++) {
	delta = INTEGER_MAX;
	if (n->status == UNMATCHED) {
            for (ei = n->edg_list; ei != -1; ei = e->ptrs[ei % 2]) {
                e = PEDGE(ei/2); 
		if (e->slack <= delta) {
		    if (e->slack == 0) {
			if ((nodelist[e->nod1].status == UNMATCHED) && 
                            (nodelist[e->nod2].status == UNMATCHED)) {
			    e->x = 1;
			    nodelist[e->nod1].matched_edge = IEDGE(e);
			    nodelist[e->nod2].matched_edge = IEDGE(e);
			    nodelist[e->nod1].status = MATCHED;
			    nodelist[e->nod2].status = MATCHED;
			    count += 2;
			}
		    }
		    delta = e->slack;
		}
	    }
	    if (delta != 0) {
		n->pi += delta;
                for (ei = n->edg_list; ei != -1; ei = e->ptrs[ei % 2]) {
                    e = PEDGE(ei/2);
                    e->slack -= delta;
		}
	    }
	}
    }
#endif

    G->unmatched_count = ncount - count;

    srk->shrinks_max = ncount / 10 + 10;  /* was just ncount */
    srk->shrinks.ary = CC_SAFE_MALLOC (srk->shrinks_max, shrink_ary_T);
    srk->expands_max = ncount / 10 + 10;
    srk->expands.node = CC_SAFE_MALLOC (srk->expands_max, int);

    if (!srk->shrinks.ary || !srk->expands.node) {
        fprintf (stderr, "out of memory in init\n");
        CC_IFFREE (srk->shrinks.ary, shrink_ary_T);
        CC_IFFREE (srk->expands.node, int);
        return 1;
    }
    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern void init_tree (graph *G, node *n)
#else
extern void init_tree (G, n)
graph *G;
node *n;
#endif
{
#if PRINT_LEVEL
    printf ("  init_tree %i\n", (int) (n - PG->nodelist)); fflush (stdout); 
#endif
    n->child = -1;
    n->sibling = -1;
    n->parent = -1;
    n->parent_edge = -1;
    n->label = PLUS;
}

#ifdef CC_PROTOTYPE_ANSI
extern void clear_tree (graph *G, node *n)
#else
extern void clear_tree (G, n)
graph *G;
node *n;
#endif
{
    node *c = n;
    node *stop = G->nodelist -1;

    while (1) {
	c->mark = 0;
	c->label = NIX;
	c->tree_root = -1;	/* ??? */

	/* go to next c */
	if (c->child!=-1) {
	    c=PNODE(c->child);
	}
	else {
	    while (PNODE(c->sibling)==stop) {
		if (c==n) return ; /* this if is for an n without childs */
		c=PNODE(c->parent);
		if (c==n) return ;
	    }
	    c=PNODE(c->sibling);
	}
    }
}

/* make_cycle_halves - edge from i to j, k is the "root" */
#ifdef CC_PROTOTYPE_ANSI
extern void make_cycle_halves (graph *G, node *node_i, node *node_j,
                               node *node_k, edge *e)
#else
extern void make_cycle_halves (G, node_i, node_j, node_k, e)
graph *G;
node *node_i, *node_j, *node_k;
edge *e;
#endif
{
    edge *edgelist = G->edgelist;
    node *parent;

#if PRINT_LEVEL
    printf ("    Make cycle halves: root %i ends %i and %i:",
	  (int) (node_k - PG->nodelist), (int) (node_i - PG->nodelist),
          (int) (node_j - PG->nodelist));
    fflush (stdout); 
#endif

    /* set matched_edge for node_j */
    node_j->status = HALVES;
    node_j->matched_edge = e - edgelist;
    e->x = HALF;

    /* path from i to k : matched_edges are the parent_edges */
    for (; node_i != node_k; node_i = PNODE(node_i->parent)) {
        edgelist[node_i->parent_edge].x = HALF;
	node_i->matched_edge = node_i->parent_edge;
	node_i->status = HALVES;
    }

    /* path from j to k : matched_edges are the "child_edges" */
    for (; node_j != node_k; node_j = parent) {
        parent = PNODE(node_j->parent);
	edgelist[node_j->parent_edge].x = HALF;
	parent->matched_edge = node_j->parent_edge;
	parent->status = HALVES;
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int lift_edges (graph *G, node *newnode)
#else
extern int lift_edges (G, newnode)
graph *G;
node *newnode;
#endif
{
    node *n, *node_k;
    node *nodelist = G->nodelist;
    int nn = INODE(newnode);
    edge *e;
    int ei, einext;

#if PRINT_LEVEL
    printf ("Lift edges %i\n", nn); fflush (stdout); 
#endif

    n = node_k = PNODE(newnode->blossom_root);
    do {
        ei = n->edg_list;
        n->edg_list = -1;
        for (; ei != -1; ei = einext) {
            e = PEDGE(ei/2);
            einext = e->ptrs[ei % 2];
	    if ((nodelist[e->nod1].blossom_parent == nn) &&
                (nodelist[e->nod2].blossom_parent == nn)) {
                e->ptrs[ei % 2] = n->edg_list;
                n->edg_list = ei;
            } else {
		if (e->nod1 == INODE(n)) {    /* nod1 is in new blossom */
		    e->nod1 = nn;
		} else {                      /* nod2 is in new blossom */
		    e->nod2 = nn;
                }
                e->ptrs[ei % 2] = newnode->edg_list;
                newnode->edg_list = ei;
	    } 
	}
	n = PNODE(n->blossom_next);
    } while (n != node_k);
    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern void shrink_tree (graph *G, node *newnode)
#else
extern void shrink_tree (G, newnode)
graph *G;
node *newnode;
#endif
{
    node *n, *node_k, *cnode;
    int c, csibling, p;

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

    n = node_k = PNODE(newnode->blossom_root);
    do {
	for (c = n->child; c != -1; c = csibling) {
            cnode = PNODE(c);
	    csibling = cnode->sibling;
	    if (cnode->blossom_parent != INODE(newnode)) {
		cnode->parent = INODE(newnode);
		cnode->sibling = newnode->child;
		newnode->child = c;
	    }
	}
	n = PNODE(n->blossom_next);
    } while (n != node_k);

    /* set other items for newnode */
    p = node_k->parent;

    newnode->sibling = -1;    /* Plus node, has no siblings */
    newnode->parent = p;
    newnode->parent_edge = node_k->parent_edge;
    newnode->matched_edge = node_k->matched_edge;
    newnode->label = PLUS;

    if (p != -1)		/* _p has just one child, so this is ok */
	G->nodelist[p].child = INODE(newnode);
}

/* shrink blossom - edge from i to j, k is the "root" */

#ifdef CC_PROTOTYPE_ANSI
extern node *shrink_blossom (graph *G, node *node_i, node *node_j,
                             node *node_k, edge *e, stats *scount)
#else
extern node *shrink_blossom (G, node_i, node_j, node_k, e, scount)
graph *G;
node *node_i, *node_j, *node_k;
edge *e;
stats *scount;
#endif
{
    node *newnode;
    node *parent;

#if PRINT_LEVEL
    printf ("    Shrink blossom: root %i ends %i and %i:\n",
       (int) (node_k - PG->nodelist), (int) (node_i - PG->nodelist),
       (int) (node_j - PG->nodelist));
    fflush (stdout); 
#endif

    scount->shrink_count++;

    newnode = PNODE(G->unused);
    G->unused = newnode->mark;
    newnode->mark = 0;
    newnode->edg_list = -1;

    if (node_k->status == UNMATCHED) {
        G->roots[node_k->tree_root].surf = INODE(newnode);
    }

    /* set blossom_next,next_edge,parent for node_j */
    /* blossom_root has to stay the same */

    node_j->blossom_next = INODE(node_i);
    node_j->blossom_next_edge = IEDGE(e);
    node_j->blossom_parent = INODE(newnode);

    /* path from i to k : blossom_next_edges are the parent_edges */

    for (; node_i != node_k; node_i = PNODE(node_i->parent)) {
	node_i->blossom_next_edge = node_i->parent_edge;
	node_i->blossom_next = node_i->parent;
	node_i->blossom_parent = INODE(newnode);
    }

    /* path from j to k : blossom_next_edges are the "child_edges" */

    for (; node_j != node_k; node_j = parent) {
        parent = PNODE(node_j->parent);
	parent->blossom_next_edge = node_j->parent_edge;
	parent->blossom_next = INODE(node_j);
	parent->blossom_parent = INODE(newnode);
    }

    newnode->blossom_root = INODE(node_k);
    newnode->blossom_next = -1;
    newnode->blossom_next_edge = -1;
    newnode->blossom_parent = -1;

    newnode->mark = 0;
    newnode->pi = 0;
    newnode->status = node_k->status;
    newnode->tree_root = node_k->tree_root;

    shrink_tree (G, newnode);
    if (lift_edges (G, newnode)) {   
        fprintf (stderr, "lift_edges failed\n");
        return (node *) NULL;
    } 

    return newnode;
}

#ifdef CC_PROTOTYPE_ANSI
extern void label_penultimate (graph *G, node *n, int label)
#else
extern void label_penultimate (G, n, label)
graph *G;
node *n;
int label;
#endif
{
    /* all the leafs of the blossom_tree under n get the penultimate label */
    node *n2;

    if (n->blossom_root == -1) {
	n->penultimate = label;
	return;
    }

    n2 = n;
    while (1) {
	if (n2->blossom_root != -1) { 
	    n2 = PNODE(n2->blossom_root);
	} else {
	    n2->penultimate = label;
	    while (n2->blossom_next == 
                   PNODE(n2->blossom_parent)->blossom_root) {
		n2 = PNODE(n2->blossom_parent);
		if (n2 == n) return;
	    }
	    n2 = PNODE(n2->blossom_next);
	}
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int lower_edges (graph *G, node *old)
#else
extern int lower_edges (G, old)
graph *G;
node *old;
#endif
{
    edge *e;
    int ei, einext;
    node *x;

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

    for (ei = old->edg_list; ei != -1; ei = einext) {
        e = PEDGE(ei/2);
        einext = e->ptrs[ei % 2];
	if (e->nod1 == INODE(old)) {
	    x = PNODE(e->orig_nod1);
	    e->nod1 = x->penultimate;
	} else {
	    x = PNODE(e->orig_nod2);
	    e->nod2 = x->penultimate;
	}
        e->ptrs[ei % 2] = PNODE(x->penultimate)->edg_list;
        PNODE(x->penultimate)->edg_list = ei;
    }
    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern void fix_matching (graph *G, node *oldnode, node *x)
#else
extern void fix_matching (G, oldnode, x)
graph *G;
node *oldnode, *x;