cpupar.cpp
// Edmonds-Karp algorithm to find max s-t flow
Edmonds-Karp algorithm to find max s-t flow
Edmonds - Karp algorithm to find max s - t flow
Flow *edKarpCPU(Graph *g, int s, int t) {
    int flow = 0;
    int *flowMatrix = (int *)malloc((g->n * g->n) * sizeof(int));
    int *parents = (int *)malloc(g->n * sizeof(int));
    int *pathCapacities = (int *)malloc(g->n * sizeof(int));
    int maxThreads = omp_get_max_threads();
    vertexSet list1;
    vertexSetInit(&list1, g->n);
    vertexSet *frontier = &list1;
    vertexSet *threadFrontiers = (vertexSet *)malloc(maxThreads *
                                    sizeof(vertexSet));
    #pragma omp parallel for schedule(static)
    for (int i=0; i < maxThreads; i++) {
        vertexSetInit(&threadFrontiers[i], g->n);
    }
    #pragma omp parallel for schedule(static)
    for (int i=0; i < (g->n * g->n); i++) {
        flowMatrix[i] = 0;
    }
    while (true) {
        int tempCapacity = bfsTopDown(g, frontier, threadFrontiers, flowMatrix, 
                                      parents, pathCapacities, s, t);
        if (tempCapacity == 0) {
            break;
        }
        flow += tempCapacity;
        int v = t;
        while (v != s) {
            int u = parents[v];
            flowMatrix[IDX(u, v, g->n)] += tempCapacity;
            flowMatrix[IDX(v, u, g->n)] -= tempCapacity;
            v = u;
        }
    }
    Flow *result = (Flow *)malloc(sizeof(Flow));
    result->maxFlow = flow;
    result->finalEdgeFlows = flowMatrix;
    #pragma omp parallel for schedule(static)
    for (int i=0; i < maxThreads; i++) {
        free(threadFrontiers[i].vertices);
    }
    free(frontier->vertices);
    free(threadFrontiers);
    free(parents);
    free(pathCapacities);
    return result;
}
Flow * edKarpCPU ( Graph * g , int s , int t ) { int flow = 0 ; int * flowMatrix = ( int * ) malloc ( ( g -> n * g -> n ) * sizeof ( int ) ) ; int * parents = ( int * ) malloc ( g -> n * sizeof ( int ) ) ; int * pathCapacities = ( int * ) malloc ( g -> n * sizeof ( int ) ) ; int maxThreads = omp_get_max_threads ( ) ; vertexSet list1 ; vertexSetInit ( & list1 , g -> n ) ; vertexSet * frontier = & list1 ; vertexSet * threadFrontiers = ( vertexSet * ) malloc ( maxThreads * sizeof ( vertexSet ) ) ; #pragma  omp parallel for schedule(static) for ( int i = 0 ; i < maxThreads ; i ++ ) { vertexSetInit ( & threadFrontiers [ i ] , g -> n ) ; } #pragma  omp parallel for schedule(static) for ( int i = 0 ; i < ( g -> n * g -> n ) ; i ++ ) { flowMatrix [ i ] = 0 ; } while ( true ) { int tempCapacity = bfsTopDown ( g , frontier , threadFrontiers , flowMatrix , parents , pathCapacities , s , t ) ; if ( tempCapacity == 0 ) { break ; } flow += tempCapacity ; int v = t ; while ( v != s ) { int u = parents [ v ] ; flowMatrix [ IDX ( u , v , g -> n ) ] += tempCapacity ; flowMatrix [ IDX ( v , u , g -> n ) ] -= tempCapacity ; v = u ; } } Flow * result = ( Flow * ) malloc ( sizeof ( Flow ) ) ; result -> maxFlow = flow ; result -> finalEdgeFlows = flowMatrix ; #pragma  omp parallel for schedule(static) for ( int i = 0 ; i < maxThreads ; i ++ ) { free ( threadFrontiers [ i ] . vertices ) ; } free ( frontier -> vertices ) ; free ( threadFrontiers ) ; free ( parents ) ; free ( pathCapacities ) ; return result ; }
Edmonds-Karp algorithm to find max s-t flow
Edmonds - Karp algorithm to find max s - t flow
// initialize all thread frontiers // backtrack