cpupar.cpp
// Implements top-down BFS. Modified from assignment 3.
Implements top-down BFS. Modified from assignment 3.
Implements top - down BFS . Modified from assignment 3 .
int bfsTopDown(Graph *g, vertexSet *frontier, vertexSet *threadFrontiers,
               int *flowMatrix, int *parents, int *pathCapacities, int s, int t) {
    int maxThreads = omp_get_max_threads();
    vertexSetClear(frontier);
    #pragma omp parallel for schedule(static)
    for (int i=0; i < maxThreads; i++) {
        vertexSetClear(&threadFrontiers[i]);
    }
    #pragma omp parallel for schedule(static)
    for (int i=0; i < g->n; i++) {
        parents[i] = NOT_VISITED_MARKER;
        pathCapacities[i] = 0;
    }
    frontier->vertices[frontier->count++] = s;
    parents[s] = s;
    pathCapacities[s] = std::numeric_limits<int>::max();
    while (frontier->count != 0) {
        bool foundT = topDownStep(g, frontier, threadFrontiers, flowMatrix, 
                             parents, pathCapacities, t);
        if (foundT) {
            return pathCapacities[t];
        }
    }
    return 0;
}
int bfsTopDown ( Graph * g , vertexSet * frontier , vertexSet * threadFrontiers , int * flowMatrix , int * parents , int * pathCapacities , int s , int t ) { int maxThreads = omp_get_max_threads ( ) ; vertexSetClear ( frontier ) ; #pragma  omp parallel for schedule(static) for ( int i = 0 ; i < maxThreads ; i ++ ) { vertexSetClear ( & threadFrontiers [ i ] ) ; } #pragma  omp parallel for schedule(static) for ( int i = 0 ; i < g -> n ; i ++ ) { parents [ i ] = NOT_VISITED_MARKER ; pathCapacities [ i ] = 0 ; } frontier -> vertices [ frontier -> count ++ ] = s ; parents [ s ] = s ; pathCapacities [ s ] = std :: numeric_limits < int > :: max ( ) ; while ( frontier -> count != 0 ) { bool foundT = topDownStep ( g , frontier , threadFrontiers , flowMatrix , parents , pathCapacities , t ) ; if ( foundT ) { return pathCapacities [ t ] ; } } return 0 ; }
Implements top-down BFS.
Implements top - down BFS .