Попытка распараллелить DFS (рекурсивный) обход через openMP - PullRequest
0 голосов
/ 07 мая 2020

Я впервые использую openMP .

Ниже приведен код (который я еще не смог распараллелить, даже в очень небольшой части, так как я столкнувшись лицом к лицу с ошибкой, указанной в конце).

// C++ program to print DFS traversal from  a given vertex in a  given graph 
#include <bits/stdc++.h> 
#include <iostream>
#include <fstream>
#include <vector>

#include <omp.h>



using namespace std; 




// Graph class represents a directed graph  using adjacency list representation 
 class Graph 
{ 
  int V;    // No. of vertices 

  // Pointer to an array containing adjacency lists 
  list<int> *adj; 

  // A recursive function used by DFS 
  void DFSUtil(int v, bool visited[]); 
 public: 
  Graph(int V);   // Constructor 

  // function to add an edge to graph 
  void addEdge(int v, int w); 

  // DFS traversal of the vertices  reachable from v 
  void DFS(int v); 
 }; 



  Graph::Graph(int V) 
{ 
 this->V = V; 
 adj = new list<int>[V]; 
} 

void Graph::addEdge(int v, int w) 
{ 
 adj[v].push_back(w); // Add w to v’s list. 
} 

void Graph::DFSUtil(int v, bool visited[]) 
{ 
 // Mark the current node as visited and  print it 
 visited[v] = true; 
 cout << v << " "; 


 // Recur for all the vertices adjacent  to this vertex 
 list<int>::iterator i; 
 for (i = adj[v].begin(); i != adj[v].end(); ++i) {
     if (!visited[*i]) 
         DFSUtil(*i, visited);
   } 
} 


// DFS traversal of the vertices reachable from v. It uses recursive DFSUtil(). 
void Graph::DFS(int v) 
{ 
 // Mark all the vertices as not visited 
 bool *visited = new bool[V]; 


 for (int i = 0; i < v; i++) 
    visited[i] = false; 

 // Call the recursive helper function to print DFS traversal 
 DFSUtil(v, visited); 
} 





     // ------------------Drivercode-------------------------------//
int main() 
{ 

//Create a dynamic array to hold the values
vector<int> numbers;

//Create an input file stream
ifstream in("graph_adjacency_list.txt",ios::in);

/*
 As long as we haven't reached the end of the file, keep reading entries.
*/

int number;  //Variable to hold each number as it is read

//Read number using the extraction (>>) operator
 while (in >> number) {
//Add the number to the end of the array
numbers.push_back(number);
 }

//Close the file stream
in.close();

/* 
    Now, the vector<int> object "numbers" contains both the array of numbers, 
        and its length (the number count from the file).
*/

//Display the numbers
cout << " \n  Numbers of our file (graph_adjacency_list.txt):\n";
for (int i=0; i<numbers.size(); i++) {
    cout << numbers[i] << ' ';
}
cout << "\n";   



int s = numbers.size();

auto start = chrono::steady_clock::now();

// Create a graph given in the above diagram 
Graph g(numbers[0]); //<--Takes the number of Vertices , included in the first position of the array(numbers[])

В этой части у меня проблема:

#pragma omp parallel shared(g) private(i) firstprivate(s)
{
 int i =0;
 #pragma omp for
 for ( i=0; i<s; i=i+2) {
    g.addEdge(numbers[i],numbers[i+1]);
  }

}

cout << "\n  Following is Depth First Traversal"
        " (starting from vertex 0): \n"; 

g.DFS(0); 
cout << "\n";   

auto end = chrono::steady_clock::now();





auto diff = end - start;
cout << "\n  Time taken:" << chrono::duration <double, milli> (diff).count() << " ms" << endl;  
cout << "\n";   

return 0; 
} 

Когда я компилирую файл через терминал:

ex. -> g ++ parallel_DFS. cpp -o parallel_DFS -fopenmp

Я принимаю эту ошибку:

 parallel_DFS.cpp: In function ‘int main()’:

 parallel_DFS.cpp:149:44: error: ‘i’ has not been declared

 #pragma omp parallel shared(g) private(i) firstprivate(s)
                                        ^

и более того, когда я запускаю его на VScode, я беру :

  malloc(): memory corruption

  Aborted (core dumped)

Заранее благодарим за любую помощь

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...