deploy/DeepStream/src/Lapjv.cpp
/** Single iteration of modified Dijkstra shortest path algorithm as explained in the JV paper.
 *
 * This is a dense matrix version.
 *
 * \return The closest free column index.
 */
Single iteration of modified Dijkstra shortest path algorithm as explained in the JV paper.
This is a dense matrix version.

\return The closest free column index.
Single iteration of modified Dijkstra shortest path algorithm as explained in the JV paper . This is a dense matrix version . \ return The closest free column index .
int_t find_path_dense(
        const uint_t n, cost_t *cost[],
        const int_t start_i,
        int_t *y, cost_t *v,
        int_t *pred) {
    uint_t lo      = 0, hi = 0;
    int_t  final_j = -1;
    uint_t n_ready = 0;
    int_t  *cols;
    cost_t *d;
    NEW(cols, int_t, n);
    NEW(d, cost_t, n);
    for (uint_t i = 0; i < n; i++) {
        cols[i] = i;
        pred[i] = start_i;
        d[i]    = cost[start_i][i] - v[i];
    }
    PRINT_COST_ARRAY(d, n);
    while (final_j == -1) {
        if (lo == hi) {
            PRINTF("%d..%d -> find\n", lo, hi);
            n_ready = lo;
            hi      = _find_dense(n, lo, d, cols, y);
            PRINTF("check %d..%d\n", lo, hi);
            PRINT_INDEX_ARRAY(cols, n);
            for (uint_t k = lo; k < hi; k++) {
                const int_t j = cols[k];
                if (y[j] < 0) {
                    final_j = j;
                }
            }
        }
        if (final_j == -1) {
            PRINTF("%d..%d -> scan\n", lo, hi);
            final_j = _scan_dense(
                    n, cost, &lo, &hi, d, cols, pred, y, v);
            PRINT_COST_ARRAY(d, n);
            PRINT_INDEX_ARRAY(cols, n);
            PRINT_INDEX_ARRAY(pred, n);
        }
    }
    PRINTF("found final_j=%d\n", final_j);
    PRINT_INDEX_ARRAY(cols, n);
    {
        const cost_t mind = d[cols[lo]];
        for (uint_t  k    = 0; k < n_ready; k++) {
            const int_t j = cols[k];
            v[j] += d[j] - mind;
        }
    }
    FREE(cols);
    FREE(d);
    return final_j;
}
int_t find_path_dense ( const uint_t n , cost_t * cost [ ] , const int_t start_i , int_t * y , cost_t * v , int_t * pred ) { uint_t lo = 0 , hi = 0 ; int_t final_j = -1 ; uint_t n_ready = 0 ; int_t * cols ; cost_t * d ; NEW ( cols , int_t , n ) ; NEW ( d , cost_t , n ) ; for ( uint_t i = 0 ; i < n ; i ++ ) { cols [ i ] = i ; pred [ i ] = start_i ; d [ i ] = cost [ start_i ] [ i ] - v [ i ] ; } PRINT_COST_ARRAY ( d , n ) ; while ( final_j == -1 ) { if ( lo == hi ) { PRINTF ( " \n " , lo , hi ) ; n_ready = lo ; hi = _find_dense ( n , lo , d , cols , y ) ; PRINTF ( " \n " , lo , hi ) ; PRINT_INDEX_ARRAY ( cols , n ) ; for ( uint_t k = lo ; k < hi ; k ++ ) { const int_t j = cols [ k ] ; if ( y [ j ] < 0 ) { final_j = j ; } } } if ( final_j == -1 ) { PRINTF ( " \n " , lo , hi ) ; final_j = _scan_dense ( n , cost , & lo , & hi , d , cols , pred , y , v ) ; PRINT_COST_ARRAY ( d , n ) ; PRINT_INDEX_ARRAY ( cols , n ) ; PRINT_INDEX_ARRAY ( pred , n ) ; } } PRINTF ( " \n " , final_j ) ; PRINT_INDEX_ARRAY ( cols , n ) ; { const cost_t mind = d [ cols [ lo ] ] ; for ( uint_t k = 0 ; k < n_ready ; k ++ ) { const int_t j = cols [ k ] ; v [ j ] += d [ j ] - mind ; } } FREE ( cols ) ; FREE ( d ) ; return final_j ; }
Single iteration of modified Dijkstra shortest path algorithm as explained in the JV paper.
Single iteration of modified Dijkstra shortest path algorithm as explained in the JV paper .
// No columns left on the SCAN list.