asequence.cpp

微软的基于HMM的人脸识别原代码, 非常经典的说

    int e_count3, e_count4;
    int gr_idx, op;
    int vtx_size = sgr[0]->vtx->elem_size - 1;
    int edge_size= sgr[0]->elem_size - 1;
    int work_vtx_size = ((vtx_size + 3) & -4) + 4;
    int work_edge_size = ((edge_size + 3) & -4) + 16;
    int max_struct_size = sgr[0]->vtx->max_count;

    v_elem = (CvGraphVtx*)icvAlloc( work_vtx_size );
    e_elem = (CvGraphEdge*)icvAlloc( work_edge_size );
    e_list = (CvGraphEdge**)icvAlloc( max_struct_size * sizeof(e_list[0]));
    
    for( i = 0; i < iters; i++ )
    {
        atsRandSetBounds( rng_state, 0, count * max_op );

        gr_idx = atsRand32s( rng_state );
        op = gr_idx % max_op;
        gr_idx /= max_op;

        if( op == 0 ) /* clear */
        {
            if( gr[gr_idx] != 0 )
            {
                int prev_vtxs = gr[gr_idx]->total;
                int prev_edges = gr[gr_idx]->edges->total;

                clear_simple_graph( sgr[gr_idx] );
                DO_CV_ACTION( cvClearGraph, ( gr[gr_idx] ));

                CHECK_CONDITION( gr[gr_idx]->total == 0 &&
                                 gr[gr_idx]->first == 0 &&
                                 gr[gr_idx]->free_elems == 0 &&
                                 (gr[gr_idx]->free_blocks != 0 || prev_vtxs == 0),
                                 "The graph is not empty after clearing" );

                CHECK_CONDITION( gr[gr_idx]->edges->total == 0 &&
                                 gr[gr_idx]->edges->first == 0 &&
                                 gr[gr_idx]->edges->free_elems == 0 &&
                                 (gr[gr_idx]->edges->free_blocks != 0 || prev_edges == 0),
                                 "The graph is not empty after clearing" );
            }
            else
            {
                CHECK_CONDITION( sgr[gr_idx]->vtx->free_count == sgr[gr_idx]->vtx->max_count,
                                 "The graph is empty while the simple_graph is not" );
            }
        }
        else
        {
            op %= max_op_ex;

            switch( op )
            {
            case 0: /* add vertex */
                if( sgr[gr_idx]->vtx->free_count == 0  ) break;

                atsbRand8s( rng_state, (char*)(v_elem + 1), vtx_size );
                idx = add_simple_graph_vertex( sgr[gr_idx], v_elem + 1 );
    
                if( gr[gr_idx] == 0 )
                {
                    gr[gr_idx] = cvCreateGraph( CV_SEQ_KIND_GRAPH | 
                        (sgr[gr_idx]->oriented ? CV_GRAPH_FLAG_ORIENTED : 0),
                        sizeof(CvGraph), work_vtx_size, work_edge_size, storage );
                    if( !gr[gr_idx] )
                    {
                        message_string = "cvCreateGraph fails";
                        code = TRS_FAIL;
                        goto test_exit;
                    }
                }
    
                idx2 = cvGraphAddVtx( gr[gr_idx], v_elem, &v_elem2 );
                CHECK_CONDITION( idx2 >= 0, "cvGraphAddVtx fails" );

                v_elem3 = cvGetGraphVtx( gr[gr_idx], idx2 );
                CHECK_CONDITION( v_elem3,
                                "cvGraphAddVtx doesn't add the element" );

                elem4 = find_simple_graph_vertex( sgr[gr_idx], idx );

                CHECK_CONDITION( CV_IS_SET_ELEM_EXISTS( v_elem2 ) &&
                                 v_elem2->first == 0 &&
                                 v_elem2 == v_elem3 && idx == idx2 &&
                                 !memcmp( v_elem2 + 1, elem4, vtx_size),
                                 "The vertex is added to graph incorrectly" );
                break;
            case 1: /* remove vertex */
                
                idx = atsRandPlain32s( rng_state ) % MAX( sgr[gr_idx]->vtx->max_count, 1);
                elem4 = find_simple_graph_vertex( sgr[gr_idx], idx );

                if( elem4 != 0 )
                {
                    assert( gr[gr_idx] != 0 );

                    v_elem2 = cvGetGraphVtx( gr[gr_idx], idx );
                    CHECK_CONDITION( v_elem2 != 0, "Existing element is not found" );
                    assert( CV_IS_SET_ELEM_EXISTS(v_elem2) );

                    e_count = calc_simple_graph_vertex_degree( sgr[gr_idx], idx );
                    if( atsRandPlain32s( rng_state ) % 2 )
                    {
                        e_count2 = cvGraphVtxDegree( gr[gr_idx], idx );
                    }
                    else
                    {
                        CvGraphVertex* vtx = cvGetGraphVtx( gr[gr_idx], idx );
                        CHECK_CONDITION( vtx != 0, "Existing element is not found" );
                        e_count2 = cvGraphVtxDegreeByPtr( gr[gr_idx], vtx );
                    }
            
                    CHECK_CONDITION( !memcmp( v_elem2 + 1, elem4, vtx_size ) &&
                                     e_count == e_count2,
                                     "Found element is incorrect");

                    e_elem2 = v_elem2->first;
                    e_count = 0;

                    /* iteration through the edge list */
                    while( e_elem2 )
                    {
                        e_list[e_count++] = e_elem2;
                        idx2 = e_elem2->vtx[1] == v_elem2;

                        CHECK_CONDITION( idx2 == 1 || e_elem2->vtx[0] == v_elem2,
                                        "Graph edge is invalid");
                        e_elem2 = e_elem2->next[idx2];
                    }

                    remove_simple_graph_vertex( sgr[gr_idx], idx );
                    if( atsRandPlain32s( rng_state ) % 2 )
                    {
                        DO_CV_ACTION( cvGraphRemoveVtx, ( gr[gr_idx], idx ));
                    }
                    else
                    {
                        CvGraphVertex* vtx = cvGetGraphVtx( gr[gr_idx], idx );
                        CHECK_CONDITION( vtx != 0, "Existing vertex is not found" );
                        DO_CV_ACTION( cvGraphRemoveVtxByPtr, ( gr[gr_idx], vtx ));
                        
                        //////////// !!!!! HACK: write index to make the test pass !!!! ////////////
                        ((CvMemBlock*)(vtx))->next = (CvMemBlock*)(idx);
                    }

                    v_elem3 = cvGetGraphVtx( gr[gr_idx], idx );

                    CHECK_CONDITION( !v_elem3 && !CV_IS_SET_ELEM_EXISTS( v_elem2 ),
                             "Remove operation doesn't clear vertex existence flag");

                    for( j = 0; j < e_count; j++ )
                    {
                        CHECK_CONDITION( !CV_IS_SET_ELEM_EXISTS( e_list[j] ),
                             "Remove operation doesn't clear edge existence flag");
                    }
                }
                break;

            case 2: /* add edge */

                idx = atsRandPlain32s( rng_state ) % MAX( sgr[gr_idx]->vtx->max_count, 1);
                elem4 = find_simple_graph_vertex( sgr[gr_idx], idx );

                if( elem4 == 0 ) break;

                for( j = 0; j <= max_struct_size/4; j++ )
                {
                    idx2 = atsRandPlain32s( rng_state ) %
                           MAX( sgr[gr_idx]->vtx->max_count, 1);
                    elem5 = find_simple_graph_vertex( sgr[gr_idx], idx2 );
                    if( idx != idx2 && elem5 )
                    {
                        char* edge = find_simple_graph_edge( sgr[gr_idx], idx, idx2 );
                        int e_count3, e_count4;

                        if( edge ) continue;

                        v_elem2 = cvGetGraphVtx( gr[gr_idx], idx );
                        v_elem3 = cvGetGraphVtx( gr[gr_idx], idx2 );

                        CHECK_CONDITION( v_elem2 && v_elem3 &&
                                       !memcmp( v_elem2 + 1, elem4, vtx_size ) &&
                                       !memcmp( v_elem3 + 1, elem5, vtx_size ),
                                       "Existing vertex is not found" );

                        e_count3 = calc_simple_graph_vertex_degree( sgr[gr_idx], idx );
                        e_count4 = calc_simple_graph_vertex_degree( sgr[gr_idx], idx2);

                        e_count = cvGraphVtxDegree( gr[gr_idx], idx );
                        e_count2= cvGraphVtxDegree( gr[gr_idx], idx2);

                        CHECK_CONDITION( e_count == e_count3 && e_count2 == e_count4, 
                                         "Different number of edges for vertices" );
                        
                        atsbRand8s( rng_state, (char*)(e_elem + 1), edge_size );
                        
                        add_simple_graph_edge( sgr[gr_idx], idx, idx2, e_elem + 1);

                        DO_CV_ACTION( cvGraphAddEdge,
                            ( gr[gr_idx], idx, idx2, e_elem, &e_elem2 ));
                                                    
                        e_elem3 = cvFindGraphEdge( gr[gr_idx], idx, idx2 );
                        elem4 = find_simple_graph_edge( sgr[gr_idx], idx, idx2 );
                        
                        CHECK_CONDITION( e_elem3 != 0 && e_elem3 == e_elem2 &&
                                         !memcmp( e_elem2 + 1, elem4, edge_size),
                                         "Added edge is incorrect");
                        
                        assert( CV_IS_SET_ELEM_EXISTS(e_elem2) );

                        e_count3 = cvGraphVtxDegree( gr[gr_idx], idx );
                        e_count4 = cvGraphVtxDegree( gr[gr_idx], idx2);

                        CHECK_CONDITION( e_count+1 == e_count3 &&
                                         e_count2+1 == e_count4, 
                                        "Incorrect number of edges for vertex" );
                        break;
                    }
                } /* end of search loop for pair */
                break;

            case 3: /* remove edge */

                if( gr[gr_idx] == 0 ) break;

                idx = atsRandPlain32s( rng_state ) % MAX( gr[gr_idx]->total, 1);
                e_elem2 = (CvGraphEdge*)cvGetSetElem(
                                  (CvSet*)(gr[gr_idx]->edges), idx );

                if( !e_elem2 ) break;
                assert( CV_IS_SET_ELEM_EXISTS( e_elem2 ));

                v_elem2 = e_elem2->vtx[0];
                v_elem3 = e_elem2->vtx[1];

                CHECK_CONDITION( v_elem2 && v_elem3,
                                 "Existing graph edge is invalid" );

                idx = cvSeqElemIdx( (CvSeq*)gr[gr_idx], v_elem2, 0 );
                idx2= cvSeqElemIdx( (CvSeq*)gr[gr_idx], v_elem3, 0 );

                CHECK_CONDITION( idx >= 0 && idx2 >= 0,
                                 "Edge vertices are not found" );

                e_count3 = calc_simple_graph_vertex_degree( sgr[gr_idx], idx );
                e_count4 = calc_simple_graph_vertex_degree( sgr[gr_idx], idx2);

                e_count = cvGraphVtxDegree( gr[gr_idx], idx );
                e_count2= cvGraphVtxDegree( gr[gr_idx], idx2);

                CHECK_CONDITION( e_count == e_count3 && e_count2 == e_count4 &&
                                 e_count > 0 && e_count2 > 0, 
                                 "Wrong number of edges for vertices" );

                elem4 = find_simple_graph_edge( sgr[gr_idx], idx, idx2 );
                e_elem3 = cvFindGraphEdge( gr[gr_idx], idx, idx2 );

                CHECK_CONDITION( e_elem3 == e_elem2 &&
                                 !memcmp( elem4, e_elem2 + 1, edge_size ),
                                 "Found graph edge is wrong" );

                remove_simple_graph_edge( sgr[gr_idx], idx, idx2 );
                DO_CV_ACTION( cvGraphRemoveEdge, ( gr[gr_idx], idx, idx2 ));

                e_count3 = cvGraphVtxDegree( gr[gr_idx], idx );
                e_count4 = cvGraphVtxDegree( gr[gr_idx], idx2);

                e_elem3 = cvFindGraphEdge( gr[gr_idx], idx, idx2 );

                CHECK_CONDITION( e_count3 == e_count - 1 && e_count4 == e_count2 - 1 &&
                                 !e_elem3 && !CV_IS_SET_ELEM_EXISTS( e_elem2 ),
                                 "Edge is removed incorrectly" );

                break;
            default:
                assert(0);
                message_string = "Unknown error";
                code = TRS_FAIL;
                goto test_exit;
            }
        }

        if( gr[gr_idx] )
        {
            /* check edges */
            code = check_seq_block_consistence( (CvSeq*)(gr[gr_idx]->edges),
                                                gr[gr_idx]->edges->total, &message_string );
            if( code != TRS_OK ) goto test_exit;

            /* check vertices */
            code = check_seq_block_consistence( (CvSeq*)gr[gr_idx],
                                                sgr[gr_idx]->vtx->count, &message_string );
            if( code != TRS_OK ) goto test_exit;
        }
        else
        {
            CHECK_CONDITION( sgr[gr_idx]->vtx->free_count == sgr[gr_idx]->vtx->max_count,
                         "CvGraph is empty while the simple_graph is not");
        }
    }

test_exit:

    icvFree( &v_elem );
    icvFree( &e_elem );
    icvFree( &e_list );

    *msg = message_string;
    *_result = result;
    return code;
}



static int  test_graph( void )
{
    const char*  message_string = ok_message;
    int i = 0, j, k = 0, code = TRS_OK;
    CvStatus   result = CV_NO_ERR;
    simple_graph** sgr = 0;
    CvGraph** gr = 0;
    CvMemStorage* storage = 0;

    int seed = atsGetSeed();
    AtsRandState rng_state;

    read_data_struct_params();
    if( !ATS_RANGE( GRAPH_TEST, adt_l, adt_h+1 )) return TRS_UNDEF;

    atsRandInit( &rng_state, 0, 1, seed );

    sgr = (simple_graph**)icvAlloc( struct_count * sizeof(sgr[0]));
    gr = (CvGraph**)icvAlloc( struct_count * sizeof(CvGraph*));

    for( j = 0; j < struct_count; j++ )
    {
        sgr[j] = create_simple_graph( max_struct_size/20, elem_size, elem_size + 2, j & 1 );
        gr[j] = 0;
    }

    storage = cvCreateMemStorage( storage_block_size );

    for( i = 0; i < iters; i++ )
    {
        atsRandSetBounds( &rng_state, 0, max_struct_size - 10 );
        
        code = test_graph_ops( struct_count, gr, sgr, &rng_state,
                               max_struct_size*2, storage, &message_string, &result );
        if( code != TRS_OK || result < 0 ) goto test_exit;

        trsWrite( ATS_LST|ATS_CON,
            "iter = %d, storage blocks = %d\n", i, calc_storage_blocks(storage) );
    }

test_exit:

    if( result < 0 ) code = TRS_FAIL;

    if( code == TRS_OK && result >= 0 )
    {
        DO_CV_ACTION( cvReleaseMemStorage, ( &storage ));
    }
    else
    {
        cvReleaseMemStorage( &storage );
        trsWrite( ATS_LST, "seed = %08x, iter = %d, index = %d", seed, i, k );
        if( result < 0 ) trsWrite( ATS_LST, "error code: %d", result );
    }

    for( j = 0; j < struct_count; j++ )
    {
        release_simple_graph( sgr + j );
    }

    icvFree( &sgr );
    icvFree( &gr );

    return trsResult( code, message_string );
}


#if 0
int test_sort_seq(void)
{
    int code = TRS_OK;
    
    CvMemStorage* storage = cvCreateMemStorage( 100 );
    CvSeq* seq = cvCreateSeq( 0, sizeof(*seq), sizeof(T), storage );
    CvSeqReader reader;
    int iters = 100;
    int i, j;
    int seed = atsGetSeed();
    AtsRandState state;

    atsRandInit( &state, 0, 1000, seed );

    for( i = 0; i < iters; i++ )
    {
        int count = rand()%10000 + 1;

        for( j = 0; j < count; j++ )
        {
            T a;
            atsbRand32s( &state, (int*)&a, sizeof(a)/sizeof(int));
            cvSeqPush( seq, &a );
        }

        icvSeqSort( seq, 0 );
        
        cvStartReadSeq( seq, &reader );

        T a;
        CV_READ_SEQ_ELEM( a, reader );

        for( j = 1; j < count; j++ )
        {
            T b;
            CV_READ_SEQ_ELEM( b, reader );
            if( !_CMP_EDGES( a, b ))
            {
                code = TRS_FAIL;
                goto test_exit;
            }
        }

        putchar('.');

        cvClearSeq( seq );
    }

test_exit:

    trsWrite( ATS_LST, "seed = %08x\n", seed );
    return trsResult( code, "" );
}
#endif

void InitASequence(void)
{
    /* Registering test functions */
    trsReg( struct_names[0], test_desc, atsAlgoClass, test_sequence );
    trsReg( struct_names[1], test_desc, atsAlgoClass, test_set );
    trsReg( struct_names[2], test_desc, atsAlgoClass, test_graph );
    //trsReg( struct_names[3], test_desc, atsAlgoClass, test_sort_seq );

} /* InitASequence */

/* End of file. */