MaxCut

#include <stdio.h>
#include <mpi.h>
#include <stdlib.h>
#include <math.h>

#define max_nodes 30
#define max_edges 500
#define send_data_tag 2001
#define return_data_tag 2002


int edge_u[max_edges];
int edge_v[max_edges];
int edge_c[max_edges];


int edge2_u[max_edges];
int edge2_v[max_edges];
int edge2_c[max_edges];


inline long long cut(long long mask, int num_edges, int *edge_u, int *edge_v, int *edge_c) {
    int result = 0;
    for (int i = 0; i < num_edges; i++) {
        if ((mask & (1LL << edge_u[i])) != (mask & (1LL << edge_v[i]))) {
            result += edge_c[i];
        }
    }
    return result;
}

int main(int argc, char *argv[]) {
    long long best, partial_best;
    MPI_Status status;
    int my_id, root_process, ierr, i, num_nodes, num_edges, num_procs,
        an_id, start_mask, end_mask, num_masks;

    // Razdeli na vec procesov
    ierr = MPI_Init(&argc, &argv);

    root_process = 0;

    // Najdi id mojega procesa in koliko procesov je bilo zacetih

    ierr = MPI_Comm_rank(MPI_COMM_WORLD, &my_id);
    ierr = MPI_Comm_size(MPI_COMM_WORLD, &num_procs);

    if(my_id == root_process) {

        // Sem zacetni/glavni procesor (MASTER)

        printf("Vpisi stevilo zaporednih stevilk da jih sestejem: ");
        scanf("%i", &num_nodes);
        scanf("%i", &num_edges);

        if(num_nodes > max_nodes || num_edges > max_edges) {
            printf("Graf je prevelik! \n");
            exit(1);
        }

        num_masks = (1LL << num_nodes);

        for(i = 0; i < num_edges; i++) {
            scanf("%i", &edge_u);
            scanf("%i", &edge_v);
            scanf("%i", &edge_c);
        }



        // Povprecno stevilo podmnozic, ki jih en proces obdeluje
        long long avg_masks_per_process = num_masks / num_procs;


        for(an_id = 1; an_id < num_procs; an_id++) {
            //Mnozica, ki jo proces obdela se zacne pri tem ideksu
            start_mask = an_id * avg_masks_per_process;
            //in se konca pri tem indeksu
            end_mask   = (an_id + 1) * avg_masks_per_process - 1;


            if((num_masks - end_mask) < avg_masks_per_process)
            end_mask = num_masks - 1;


            ierr = MPI_Send( &start_mask, 1 , MPI_LONG,
                an_id, send_data_tag, MPI_COMM_WORLD);
            ierr = MPI_Send( &end_mask, 1 , MPI_LONG,
                an_id, send_data_tag, MPI_COMM_WORLD);


            ierr = MPI_Send( &num_edges, 1 , MPI_INT,
                an_id, send_data_tag, MPI_COMM_WORLD);
            ierr = MPI_Send( edge_u, num_edges, MPI_INT,
                an_id, send_data_tag, MPI_COMM_WORLD);
            ierr = MPI_Send( edge_v, num_edges, MPI_INT,
                an_id, send_data_tag, MPI_COMM_WORLD);
            ierr = MPI_Send( edge_c, num_edges, MPI_INT,
                an_id, send_data_tag, MPI_COMM_WORLD);
        }

        // Izracunamo se del za MASTERA

        best = 0;
        for (long long mask = 0; mask < avg_masks_per_process + 1; mask++) {
            best = std::max(best, cut(mask, num_edges, edge_u, edge_v, edge_c));
        }

        // Prejmi max-cut iz vsakega procesa

        for(an_id = 1; an_id < num_procs; an_id++) {

            ierr = MPI_Recv( &partial_best, 1, MPI_LONG, MPI_ANY_SOURCE,
                return_data_tag, MPI_COMM_WORLD, &status);

            best = std::max(best, partial_best);
        }

        printf("Vse skupaj je: %ld\n", best);
    }

    else {

        // Nisem glavni proces (SLAVE)

        ierr = MPI_Recv( &start_mask, 1 , MPI_LONG,
            root_process, send_data_tag, MPI_COMM_WORLD, &status);
        ierr = MPI_Recv( &end_mask, 1 , MPI_LONG,
            root_process, send_data_tag, MPI_COMM_WORLD, &status);


        ierr = MPI_Recv( &num_edges, 1 , MPI_INT,
            root_process, send_data_tag, MPI_COMM_WORLD, &status);
        ierr = MPI_Recv( edge2_u, num_edges, MPI_INT,
            root_process, send_data_tag, MPI_COMM_WORLD, &status);
        ierr = MPI_Recv( edge2_v, num_edges, MPI_INT,
            root_process, send_data_tag, MPI_COMM_WORLD, &status);
        ierr = MPI_Recv( edge2_c, num_edges, MPI_INT,
            root_process, send_data_tag, MPI_COMM_WORLD, &status);

        // Izracunaj max-cut za vsak proces
        partial_best = 0;
        for (long long mask = start_mask; mask <= end_mask; mask++) {
            partial_best = std::max(partial_best, cut(mask, num_edges, edge2_u, edge2_v, edge2_c));
        }

        // Poslji max-cut nazaj k glavnemu procesu
        ierr = MPI_Send( &partial_best, 1, MPI_LONG, root_process,
            return_data_tag, MPI_COMM_WORLD);
    }
    ierr = MPI_Finalize();
}