cpupar.cpp
// Dinic's algorithm to find max s-t flow
Dinic's algorithm to find max s-t flow
Dinic ' s algorithm to find max s - t flow
Flow *dinicCPU(Graph *g, int s, int t) {
    int flow = 0;
    int maxInt = std::numeric_limits<int>::max();
    int *curNeighbor = (int *)malloc(g->n * sizeof(int));
    int *levels = (int *)malloc(g->n * sizeof(int));
    int *flowMatrix = (int *)calloc((g->n * 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);
    }
    while (true) {
        #pragma omp parallel for schedule(static)
        for (int i=0; i < g->n; i++) {
            curNeighbor[i] = 0;
        }
        bool existsPath = bfsTopDownDinicLayered(g, frontier, threadFrontiers, 
                                                 flowMatrix, levels, s, t);
        if (!existsPath) {
            break;
        }
        while (true) {
            int tempFlow = dinicSearch(g, flowMatrix, levels, curNeighbor, s, t, maxInt);
            if (tempFlow == 0) {
                break;
            }
            flow += tempFlow;
        }
    }
    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(curNeighbor);
    free(levels);
    return result;
}
Flow * dinicCPU ( Graph * g , int s , int t ) { int flow = 0 ; int maxInt = std :: numeric_limits < int > :: max ( ) ; int * curNeighbor = ( int * ) malloc ( g -> n * sizeof ( int ) ) ; int * levels = ( int * ) malloc ( g -> n * sizeof ( int ) ) ; int * flowMatrix = ( int * ) calloc ( ( g -> n * 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 ) ; } while ( true ) { #pragma  omp parallel for schedule(static) for ( int i = 0 ; i < g -> n ; i ++ ) { curNeighbor [ i ] = 0 ; } bool existsPath = bfsTopDownDinicLayered ( g , frontier , threadFrontiers , flowMatrix , levels , s , t ) ; if ( ! existsPath ) { break ; } while ( true ) { int tempFlow = dinicSearch ( g , flowMatrix , levels , curNeighbor , s , t , maxInt ) ; if ( tempFlow == 0 ) { break ; } flow += tempFlow ; } } 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 ( curNeighbor ) ; free ( levels ) ; return result ; }
Dinic's algorithm to find max s-t flow
Dinic ' s algorithm to find max s - t flow
// initialize all thread frontiers