Getting wrong values on Brandes Algorithm

General OpenMP discussion

Getting wrong values on Brandes Algorithm

Postby brazilian_student » Thu Dec 07, 2017 8:24 am

I am getting an error when I run this code:

Code: Select all
#include <stdio.h>
#include <vector>
#include <iostream>
#include <string>
#include <omp.h>
#include <deque>
using namespace std;

int main(int argc, char *argv[]) {

   int count = 1;
   while (count != argc) {


      FILE *arq, *saida;

      if ((arq = fopen(argv[count], "r")) == NULL)
      {
         cout << "Unable to open File";
         return 0;
      }

      int V, E, i, j;

      for (i = 0; i<2; i++) {
         if (i == 0) {
            fscanf(arq, "%d", &V);

         }
         if (i == 1) {
            fscanf(arq, "%d", &E);
         }
      }


      int **grafo = new int*[E];
      for (int i = 0; i < E; i++)
         grafo[i] = new int[2];

      for (i = 0; i<E + 2; i++) {

         if (i == 0 || i == 1) {
            continue;
         }

         else for (j = 0; j<2; j++) {
            fscanf(arq, "%d ", &grafo[i - 2][j]);
         }
      }

      vector<int> *A;
      A = new vector<int>[V];
      int conteudo;
      for (i = 0; i<E; i++) {
         conteudo = grafo[i][0];

         A[conteudo].push_back(grafo[i][1]);
         A[grafo[i][1]].push_back(conteudo);
      }



      float *Cb = new float[V];
      for (i = 0; i < V; i++) {
         Cb[i] = 0;
      }

      float *Cb_private;

      #pragma omp parallel
      {

         const int nthreads = omp_get_num_threads();
         const int ithread = omp_get_thread_num();

         #pragma omp single
         {
            Cb_private = new float[V * nthreads];
            for (i = 0; i<(V * nthreads); i++) Cb_private[i] = 0;
         }

         float *sigma = new float[V];
         int *d = new int[V];
         int v, w;

         #pragma omp for
         for (int s = 0; s < V; s++) {

            for (i = 0; i < V; i++) {
               sigma[i] = 0;
               d[i] = -1;
            }

            vector<int> *P;
            vector<int> S;
            deque<int> Q;
            P = new vector<int>[V];

            sigma[s] = 1;
            d[s] = 0;

            Q.push_back(s);

            while (!Q.empty()) {

               v = Q[0];
               Q.pop_front();
               S.push_back(v);

               for (j = 0; j < A[v].size(); j++) {

                  w = A[v][j];
                  if (d[w] < 0) {
                     Q.push_back(w);
                     d[w] = d[v] + 1;
                  }

                  if (d[w] == (d[v] + 1)) {
                     sigma[w] = sigma[w] + sigma[v];
                     P[w].push_back(v);
                  }

               }
            }

            float *delta = new float[V];

            for (i = 0; i < V; i++) {
               delta[i] = 0;
            }

            while (!S.empty()) {
               w = S[S.size() - 1];
               S.pop_back();

               for (i = 0; i < P[w].size(); i++) {
                  v = P[w][i];
                  delta[v] = delta[v] + (sigma[v] / sigma[w])*(1 + delta[w]);
               }

               if (w != s) {
                  Cb_private[ithread * V + w] = (Cb_private[ithread * V + w] + delta[w]);
               }
            }
         }

         #pragma omp for
         for (int i = 0; i<V; i++) {
            for (int t = 0; t<nthreads; t++) {
               Cb[i] += Cb_private[V * t + i];
            }
         }
      }




      string str = argv[count];
      string str2 = "btw";
      str.erase(str.end() - 3, str.end());
      str.append(str2);
      saida = fopen(str.c_str(), "w");

      for (i = 0; i<V; i++) {
         Cb[i] = Cb[i] / 2;
         fprintf(saida, "%.6f\n", Cb[i]);
      }
      fclose(saida);


      fclose(arq);


      count++;
   }

   return 0;

}





Here, the code reads a file that has E+2 lines; the first line indicates the number of vertices of a graph, and the second, the number of edges; the following lines indicates the conections of the vertices. After this, it should calculate de Betweenness Centrality for each of the V vertices (Brandes' algorithm) and generate the file "saida.btw". However, every time I run it, it returns different wrong values; the sequential version of the code is working.

What am I doing wrong??
brazilian_student
 
Posts: 1
Joined: Wed Dec 06, 2017 9:01 pm

Re: Getting wrong values on Brandes Algorithm

Postby MarkB » Thu Dec 07, 2017 12:44 pm

The most obvious problem I can see is that the loop indices i and j are shared by default inside the parallel region.
MarkB
 
Posts: 768
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 4 guests

cron