match.c

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

#endif
{
    node *n, *memo;
    node *nodelist = G->nodelist;
    edge *e;

#if PRINT_LEVEL
    printf ("    Fix Matching %i; x = %i\n",
                (int) (oldnode - PG->nodelist), (int) (x - PG->nodelist));
    fflush (stdout); 
#endif

    if (x->blossom_next_edge == x->matched_edge) {
        n = x;
        memo = PNODE(oldnode->blossom_root);
    } else {
        n = PNODE(oldnode->blossom_root);
        memo = x;
    }

    for (; n != memo; n = PNODE(n->blossom_next)) {
        e = PEDGE(n->blossom_next_edge);
        e->x = 1 - e->x;
        if (e->x == 1) {
            nodelist[e->nod1].status = MATCHED;
	    nodelist[e->nod2].status = MATCHED;
	    nodelist[e->nod1].matched_edge = IEDGE(e);
	    nodelist[e->nod2].matched_edge = IEDGE(e);
        }
    }

    oldnode->blossom_root = INODE(x);
    x->matched_edge = oldnode->matched_edge;
    x->status = MATCHED;
}

#ifdef CC_PROTOTYPE_ANSI
extern void fix_tree (graph *G, node *oldnode, node *x, node *y)
#else
extern void fix_tree (G, oldnode, x, y)
graph *G;
node *oldnode, *x, *y;
#endif
{
    node *p, *n, *cnode;
    int c, label_help;

    p = PNODE(oldnode->parent);

#if PRINT_LEVEL
    printf ("    Fix Tree %i; x = %i; y = %i\n",
        (int) (oldnode - PG->nodelist), (int) (x - PG->nodelist),
        (int) (y - PG->nodelist));
    fflush (stdout); 
#endif

    /* Restore child-sibling list for p */

    if (p->child == INODE(oldnode)) {
	y->sibling = oldnode->sibling;
	p->child = INODE(y);
    } else {
	for (c = p->child; c != -1; c = cnode->sibling) {
            cnode = PNODE(c);
	    if (cnode->sibling == INODE(oldnode)) {
		cnode->sibling = INODE(y);
		y->sibling = oldnode->sibling;
		break;
	    }
	}
        assert (c != -1);
    }

    y->parent = INODE(p);
    y->parent_edge = oldnode->parent_edge;
    G->nodelist[oldnode->child].parent = INODE(x);
    x->child = oldnode->child;

    label_help = MINUS;
    if (y->blossom_next_edge == y->matched_edge) {
        /* From y to x */
	for (n = y; n != x; n = PNODE(n->blossom_next)) {
	    n->child = n->blossom_next;
	    G->nodelist[n->blossom_next].parent = INODE(n);
	    G->nodelist[n->blossom_next].parent_edge = n->blossom_next_edge;
	    n->label = label_help;
	    if (label_help == MINUS) {
		label_help = PLUS;
	    } else {
		label_help = MINUS;
	    }
	}
	x->label = MINUS;	/* This is not set in for-loop */
    } else {
	for (n = x; n != y; n = PNODE(n->blossom_next)) {
            /* From x to y */
	    n->parent = n->blossom_next;
	    n->parent_edge = n->blossom_next_edge;
	    G->nodelist[n->blossom_next].child = INODE(n);
	    n->label = label_help;
	    if (label_help == MINUS) {
		label_help = PLUS;
	    } else {
		label_help = MINUS;
	    }
	}
	y->label = MINUS;	/* This is not set in for-loop */
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int expand_blossom (graph *G, node *oldnode, stats *scount)
#else
extern int expand_blossom (G, oldnode, scount)
graph *G;
node *oldnode;
stats *scount;
#endif
{
    node *memo, *x, *y, *n;
    int child, parent;

    scount->expand_count++;

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

    child = oldnode->child;
    parent = oldnode->parent;

    n = memo = PNODE(oldnode->blossom_root);
    do {
	label_penultimate (G, n, INODE(n));
	n = PNODE(n->blossom_next);
    } while (n != memo);

    if (G->edgelist[oldnode->matched_edge].nod1 == INODE(oldnode))
	x = PNODE(G->edgelist[oldnode->matched_edge].orig_nod1);
    else
	x = PNODE(G->edgelist[oldnode->matched_edge].orig_nod2);

    if (G->edgelist[oldnode->parent_edge].nod1 == INODE(oldnode))
	y = PNODE(G->edgelist[oldnode->parent_edge].orig_nod1);
    else
	y = PNODE(G->edgelist[oldnode->parent_edge].orig_nod2);

    if (lower_edges (G, oldnode)) {
        fprintf (stderr, "lower_edges failed\n");
        return 1;
    }
    fix_matching (G, oldnode, PNODE(x->penultimate));

    n = memo;
    do {
	/* Clear tree structure of nodes in oldnodes blossom */
	n->blossom_parent = -1;
	n->child = -1;
	n->parent = -1;
	n->sibling = -1;
	n->parent_edge = -1;
	n->label = NIX;

	n = PNODE(n->blossom_next);
        n->hit = n->hit | oldnode->hit;
    } while (n != memo);

    fix_tree (G, oldnode, PNODE(x->penultimate), PNODE(y->penultimate));

    /* update tree roots */

    for (child = G->nodelist[child].parent; child != parent;
                                            child = G->nodelist[child].parent) {
	G->nodelist[child].tree_root = G->nodelist[parent].tree_root;
    }

    /* clear oldnode */

    oldnode->edg_list = -1;
    oldnode->pi = 0;
    oldnode->status = UNMATCHED;
    oldnode->matched_edge = -1;
    oldnode->child = -1;
    oldnode->sibling = -1;
    oldnode->parent = -1;
    oldnode->parent_edge = -1;
    oldnode->label = NIX;
    oldnode->blossom_root = -1;
    oldnode->blossom_next = -1;
    oldnode->blossom_next_edge = -1;
    oldnode->blossom_parent = -1;
    oldnode->penultimate = -1;
    oldnode->tree_root = -1;
    oldnode->hit = 0;

    /* put oldnode on unused list */

    oldnode->mark = G->unused;
    G->unused = oldnode - G->nodelist;

    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern node *common_parent (graph *G, node *p, node *q, int *size)
#else
extern node *common_parent (G, p, q, size)
graph *G;
node *p, *q;
int *size;
#endif
{
    int count;
    node *n;
    node *stop = G->nodelist - 1;

#if PRINT_LEVEL
    printf ("     Common-parent from %i and %i is ",
          (int) (p - PG->nodelist), (int) (q - PG->nodelist));
    fflush (stdout);
#endif

    for (count = 0, n = p; n != stop; n = PNODE(n->parent)) {
	count++;
	n->mark = count;
    }

    for (count = 0; q != stop; q = PNODE(q->parent)) {
	if (q->mark) {
            *size = (count + q->mark);
	    for (n = p; n != stop; n = PNODE(n->parent)) 
		n->mark = 0;
	    return q;
	}
	count++;
    }
    for (n = p; n != stop; n = PNODE(n->parent))
	n->mark = 0;		

    *size = 0;
    return (node *) NULL;
}

#ifdef CC_PROTOTYPE_ANSI
extern void flip_cycle (graph *G, node *node_i)
#else
extern void flip_cycle (G, node_i)
graph *G;
node *node_i;
#endif
{
    int count = 0, ok = 1;
    node *node_j, *node_k;
    edge *e, *memo;

#if PRINT_LEVEL
    printf ("     Flip cycle with root %i: ", (int) (node_i - PG->nodelist));
    fflush (stdout);
#endif

    /* init start (node_j, node_k, e) */

    e = PEDGE(node_i->matched_edge);
    node_j = node_i;
    node_k = OTHEREND (e, node_i, G->nodelist);

    while (ok) {
	/* test if last edge */
	if (node_k == node_i)
	    ok = 0;

	e->x = (count % 2);
	memo = PEDGE(node_k->matched_edge);

	if (count % 2) {
	    node_j->matched_edge = node_k->matched_edge = IEDGE(e);
	    node_j->status = MATCHED;
	    node_k->status = MATCHED;
	}

	e = memo;
	node_j = node_k;
        node_k = OTHEREND (e, node_j, G->nodelist);
	count++;
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern void augment_path (graph *G, node *n, int fractional)
#else
extern void augment_path (G, n, fractional)
graph *G;
node *n;
int fractional;
#endif
{
    edge *edgelist = G->edgelist;
    node *nodelist = G->nodelist;

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

    if (n->parent != -1) {
	for (; n->parent_edge != -1; n = PNODE(n->parent)) {
	    edgelist[n->parent_edge].x = 1 - edgelist[n->parent_edge].x;
	    if (edgelist[n->parent_edge].x == 1) {
		nodelist[edgelist[n->parent_edge].nod1].matched_edge =
                             n->parent_edge;
		nodelist[edgelist[n->parent_edge].nod2].matched_edge =
                             n->parent_edge;
	    }
	}
    }
    n->status = MATCHED;  /* This will be corrected in HALVES case */
    if (!fractional) 
        G->roots[n->tree_root].status = MATCHED;
    clear_tree (G, n);   /* n is the root */
}

#ifdef CC_PROTOTYPE_ANSI
extern int augment_blossom (graph *G, edge *e, int fractional, srkstuff *srk)
#else
extern int augment_blossom (G, e, fractional, srk)
graph *G;
edge *e;
int fractional;
srkstuff *srk;
#endif
{
    node *node_i = PNODE(e->nod1);
    node *node_j = PNODE(e->nod2);
    node *node_k;
    int size;
    shrink_ary_T *ary = srk->shrinks.ary;

#if PRINT_LEVEL
    printf ("    Augment blossom with ends %i & %i \n", e->nod1, e->nod2);
    fflush (stdout);
#endif

    node_k = common_parent (G, node_i, node_j, &size);
    if (node_k == (node *) NULL) {    /* more then one tree */
	e->x = 1;
	node_i->matched_edge = e -G->edgelist;
	node_j->matched_edge = e -G->edgelist;
	G->unmatched_count -= 2;
	augment_path (G, node_i, fractional);
	augment_path (G, node_j, fractional);
	return 1;
    } else {
	if (fractional) {
	    make_cycle_halves (G, node_i, node_j, node_k, e);
	    augment_path (G, node_k, fractional);
            node_k->status = HALVES;
	    G->unmatched_count--;
	    return 1;
	} else {
	    if (srk->shrinks.length < srk->shrinks_max) {
		ary[srk->shrinks.length].node_i = node_i - G->nodelist;
		ary[srk->shrinks.length].node_j = node_j - G->nodelist;
		ary[srk->shrinks.length].node_k = node_k - G->nodelist;
		ary[srk->shrinks.length].edge = e - G->edgelist;
		ary[srk->shrinks.length].size = size;
		srk->shrinks.length++;
                if (srk->shrinks.length == srk->shrinks_max) {
		    printf ("   WARNING: shrinks.length==shrinks_max=%i\n",
                               srk->shrinks_max);
		    fflush (stdout);
                }
	    }
            return 0;
	}
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int add_to_tree (graph *G, edge *e, node *node_i, node *node_j,
                        int fractional)
#else
extern int add_to_tree (G, e, node_i, node_j, fractional)
graph *G;
edge *e;
node *node_i, *node_j;
int fractional;
#endif
{
    node *node_k;
    edge *f;

#if PRINT_LEVEL
    printf ("    Add (%i,%i)=(%i,%i) to tree \n", e->nod1,
       e->nod2, (int) (node_i - PG->nodelist), (int) (node_j - PG->nodelist));
    fflush (stdout);
#endif

    if (node_j->status == UNMATCHED) {
	e->x = 1;
	node_j->status = MATCHED;
	node_i->matched_edge = e - G->edgelist;
	node_j->matched_edge = e - G->edgelist;
	G->unmatched_count -= 2;
        if (!fractional) 
            G->roots[node_j->tree_root].status = MATCHED;
	augment_path (G, node_i, fractional);
	return 1;
    } else if (node_j->status == HALVES) {
	flip_cycle (G, node_j);
	e->x = 1;
	node_i->status = MATCHED;
	node_j->status = MATCHED;
	node_i->matched_edge = e - G->edgelist;
	node_j->matched_edge = e - G->edgelist;
	augment_path (G, node_i, fractional);
	G->unmatched_count--;
	return 1;
    } else {
	/* set node_j in tree */
	node_j->sibling = node_i->child;
	node_j->parent = INODE(node_i);
	node_j->tree_root = node_i->tree_root;
	node_j->parent_edge = IEDGE(e);
	node_j->label = MINUS;

	/* set child for node_i */
	node_i->child = INODE(node_j);

	/* set child for node_j */
	f = PEDGE(node_j->matched_edge);
        node_k = OTHEREND (f, node_j, G->nodelist);
	node_j->child = INODE(node_k);

	/* set node_k in tree */
	node_k->child = -1;
	node_k->sibling = -1;
	node_k->parent = INODE(node_j);
	node_k->parent_edge = IEDGE(f);
	node_k->label = PLUS;
	node_k->tree_root = node_j->tree_root;

	return 0;
    }
}

#ifdef CC_PROTOTYPE_ANSI
extern int checkout_node (graph *G, node *n, int fractional, srkstuff *srk)
#else
extern int checkout_node (G, n, fractional, srk)
graph *G;
node *n;
int fractional;
srkstuff *srk;
#endif
{
    node *m;
    int augmented;
    edge *e;
    int ei;

#if PRINT_LEVEL
    printf ("   Checkout node %i ...\n", (int) (n - PG->nodelist));
    fflush (stdout);
#endif
 
    for (ei = n->edg_list; ei != -1; ei = e->ptrs[ei % 2]) {
        e = PEDGE(ei/2);
        if (e->slack == 0) {
            m = OTHEREND (e, n, G->nodelist);
	    if (m->label == PLUS) {
		return augment_blossom (G, e, fractional, srk);
	    }
	    if (m->label == NIX) {
		if ((augmented = add_to_tree (G, e, n, m, fractional)) != 0) {
		    return augmented;
		}
            }
	}
    }

    return 0;
}

#ifdef CC_PROTOTYPE_ANSI
extern int grow_tree_no_shrink (graph *G, node *n, int fractional,
           srkstuff *srk)
#else
extern int grow_tree_no_shrink (G, n, fractional, srk)
graph *G;
node *n;
int fractional;
srkstuff *srk;