DFS and BFS traversal using OpenMP

Question

This words fine. Or seems to. It runs and gives the right output.

#include <conio.h>
#include <stdlib.h>
//#include "omp.h"
#include "iostream"

#define infinity 9999
#define MAX 20

using namespace std;
//int v,e;
//double etime;

class Q 
{
    int data[30];
    int R,F;
    public:
    Q() {
    R=F=-1;
    }

    void init() {
    R=F=-1;
    }

    int empty() {
    if(R==-1)
    return 1;
    return 0;
    }
    void insert(int x) {
    if(empty())
        R=F=0;
    else
        R=R+1;
    data[R]=x;
    }

    int Delete() {
    int x=data[F];
    if(R==F)
        R=F=-1;
    else
        F=F+1;
    return(x);
    }
};  //end of Q implementation


struct node
{
node *next;
int vertex;
};  //end of note structure declarion

class graph {
    int visited[MAX];
    node *G[20];        
    int n;              
    void insert (int vi,int vj);   
    void DFS1 (int);
    public:
    graph () {
    n=0;
    }
    void readgraph ();
    void BFS (int);
    void DFS (int);
};

void graph::DFS  (int start) {
    for (int i=0;i<n;i++)
        visited[i]=0;
    DFS1  (start);
    }

void graph::BFS  (int v) {
    int i,w;
    Q q;
    node *p;
    for (i=0;i<n;i++)
    visited[i]=0;
    q.insert (v);
    cout<<"\n Visit  "<<v;
    visited[v]=1;
    while (!q.empty ()) {
    //omp_set_num_threads (4);
    //#pragma omp parallel shared  (visited,node,data,vertex,v,q,G) num_threads (4)  //OpenMP shared memory
    v=q.Delete ();
    //double wtime1=omp_get_wtime ();
    //int nthrds= omp_get_num_threads ();
        //#pragma omp parallel shared(visited, G) private(w) num_threads(4)
        for (p=G[v] ; p != NULL ; p=p->next) {
            w=p->vertex;
            //#pragma omp critical
            {
            if (visited[w]== 0) {
                q.insert (w);
                visited[w]=1;
                cout<<"\nvisit "<<w;
            }
            }
        }
    }
    //double wtime2= omp_get_wtime ();
    //etime +=  wtime2-wtime1;
}

void graph::DFS1  (int i) {
    node *p;
    cout<<"\nvisit"<<i;
    p=G[i];
    visited[i]=1;
    //#pragma omp parallel shared(visited, G) private(i) num_threads(4)
    while (p != NULL)   {
        i=p->vertex;
        //#pragma omp critical
        if (!visited[i])
            DFS1 (i);
        p=p->next;
    }
}


void graph::readgraph () {
    int i,vi,vj,no_of_edges;
    cout<<"\nEnter no. of vertices :";
    cin>>n;
        for (i=0;i<n;i++)
            G[i]=NULL;
            cout<<"\nEnter no of edges :";
            cin>>no_of_edges;
            
        for (i=0;i<no_of_edges;i++) {
            cout<<"\nEnter an edge  (u,v)  :";
            cin>>vi>>vj;
            insert (vi,vj);
            insert (vj,vi);
        }
}
void graph::insert (int vi,int vj) {
    node *p,*q;
    q=new node ;
    q->vertex=vj;
    q->next=NULL;
    
    if (G[vi]== NULL)
        G[vi]=q;
    
    else {
        p= G[vi];
        while (p->next != NULL)
        p=p->next;
        p->next=q;
    }
}


int main  () {
int op,start,n;
graph g1;
//Clear
    do {
    cout<<"\n\n1)Create a graph \n2)BFS\n3)DFS\n4)Quit";
    cout<<"\nEnter Your Choice : ";
    cin >> op;
        switch (op) {

        case 1: 
            g1.readgraph ();
            break;

        case 2: 
            cout<<"\nEnter starting node : ";
            cin>>start;
            g1.BFS (start);
            break;

        case 3: 
            cout<<"\nEnter starting node : ";
            cin>>start;
            g1.DFS (start);
            break;
        }

    } while (op !=  4);
return 0;
}

But as soon as I un-comment the OpenMP directive. I get

 error: invalid increment expression
   52 |         for (node* p = G[v]; p != NULL; p = p->next) {

error: invalid increment expression
   73 |     for (node* p = G[i]; p != NULL; p = p->next) {

I know this is probably something really silly. Or stupid. That I am missing.

I am compiling using the usual g++ foo.cpp -fopenmp -o foo
Note: I know the openmp parts are probably in the wrong places too. Becuase I changed the for's to while to make it run and it gets start after 1-3 vertices are traversed

Answer 1

Since you're writing C++ I'll phrase it in C++ terms: the loop needs to have a random-access iterator. Meaning: OpenMP wants to be able to count how many iterations there are, and then divide them up before the loop starts. Clearly that's not possible with going down a linked list as you are doing.

The solution is to use tasks:

#pragma omp parallel
#pragma omp single
for ( /* go down the list */ ) 
    #pragma omp task
    //process the current list node.