\ * icvFindBasicVariables * \****************************************************************************************/
| 563 | * icvFindBasicVariables * |
| 564 | \****************************************************************************************/ |
| 565 | static int icvFindBasicVariables( float **cost, char **is_x, |
| 566 | CvNode1D * u, CvNode1D * v, int ssize, int dsize ) |
| 567 | { |
| 568 | int i, j, found; |
| 569 | int u_cfound, v_cfound; |
| 570 | CvNode1D u0_head, u1_head, *cur_u, *prev_u; |
| 571 | CvNode1D v0_head, v1_head, *cur_v, *prev_v; |
| 572 | |
| 573 | /* initialize the rows list (u) and the columns list (v) */ |
| 574 | u0_head.next = u; |
| 575 | for( i = 0; i < ssize; i++ ) |
| 576 | { |
| 577 | u[i].next = u + i + 1; |
| 578 | } |
| 579 | u[ssize - 1].next = 0; |
| 580 | u1_head.next = 0; |
| 581 | |
| 582 | v0_head.next = ssize > 1 ? v + 1 : 0; |
| 583 | for( i = 1; i < dsize; i++ ) |
| 584 | { |
| 585 | v[i].next = v + i + 1; |
| 586 | } |
| 587 | v[dsize - 1].next = 0; |
| 588 | v1_head.next = 0; |
| 589 | |
| 590 | /* there are ssize+dsize variables but only ssize+dsize-1 independent equations, |
| 591 | so set v[0]=0 */ |
| 592 | v[0].val = 0; |
| 593 | v1_head.next = v; |
| 594 | v1_head.next->next = 0; |
| 595 | |
| 596 | /* loop until all variables are found */ |
| 597 | u_cfound = v_cfound = 0; |
| 598 | while( u_cfound < ssize || v_cfound < dsize ) |
| 599 | { |
| 600 | found = 0; |
| 601 | if( v_cfound < dsize ) |
| 602 | { |
| 603 | /* loop over all marked columns */ |
| 604 | prev_v = &v1_head; |
| 605 | |
| 606 | for( found |= (cur_v = v1_head.next) != 0; cur_v != 0; cur_v = cur_v->next ) |
| 607 | { |
| 608 | float cur_v_val = cur_v->val; |
| 609 | |
| 610 | j = (int)(cur_v - v); |
| 611 | /* find the variables in column j */ |
| 612 | prev_u = &u0_head; |
| 613 | for( cur_u = u0_head.next; cur_u != 0; ) |
| 614 | { |
| 615 | i = (int)(cur_u - u); |
| 616 | if( is_x[i][j] ) |
| 617 | { |
| 618 | /* compute u[i] */ |
| 619 | cur_u->val = cost[i][j] - cur_v_val; |
| 620 | /* ...and add it to the marked list */ |
| 621 | prev_u->next = cur_u->next; |
| 622 | cur_u->next = u1_head.next; |