OpenMPで並列化するBoruvka

Question

私はBoruvkaのアルゴリズムをC++で順番に実装していますが、アルゴリズムの利点の1つは容易に並列化できるということです。私はopenMPを使ってこれをやろうとしていますが、動作させる方法を理解できません。私はgraph.txtから隣接リストを読み、mt.txtに最小スパニングツリーの出力を表示します。ここでboruvkaのための私のシーケンシャルコードである：私のgraph.txtの

#include <iostream> 
#include <fstream> 
#include <sstream> 


using namespace std; 

// initialize data structure for edges (given in adjacency list) 
struct Edge { 
    int v1, v2, weight; // 2 connecting verticies and a weight 
}; 

// initialize structure for the graph 
struct Graph { 
    int vertex, edge; 
    Edge* e; // undirected graph so edge from v1 to v2 is same as v2 to v1 
}; 

// Creates a graph for #verticies and #edges using arrays 
struct Graph* formGraph(int vertex, int edge) 
{ 
    Graph* graph = new Graph; 
    graph->vertex = vertex; 
    graph->edge = edge; 
    graph->e = new Edge[edge]; // again, v1-v2 = v2-v1 
    return graph; 
} 

// initialize structure for subsets within the graph 
struct Subset { 
    int parent, rank; // rank will act as counter 
}; 

// will help to find lightest edge of sets recursively 
int find(struct Subset subset[], int i) 
{ 
    if (subset[i].parent != i) { 
     subset[i].parent = find(subset, subset[i].parent); 
    } 
// once it is =1 
return subset[i].parent; 
} 

// A function that does union of two sets 
void Union(struct Subset subs[], int set1, int set2) 
{ 
    int root1 = find(subs, set1); 
    int root2 = find(subs, set2); 

    //union by ranking 
    if (subs[root1].rank < subs[root2].rank) { // if rank2 is higher thats parent 
     subs[root1].parent = root2; 
    } 

    else if (subs[root1].rank > subs[root2].rank) { // if rank1 is higher thats parent 
     subs[root2].parent = root1; 
    } 

    else // ranks are the equal so increment rank by 1 
    { 
     subs[root2].parent = root1; 
     subs[root1].rank++; 
    } 
} 

// the boruvka algorithm implementation 
void boruvka(struct Graph* graph) { 
// set data of initial graph 
int vertex = graph->vertex; 
int edge = graph->edge; 
Edge* e = graph->e; 

//initially there will always be as many subsets as there are vertices 
struct Subset *subs = new Subset[vertex]; 

int *lightest = new int[vertex]; // array storing least weight edge 

// subset for each vertex 
for (int v = 0; v < vertex; v++) 
{ 
    subs[v].parent = v; // initial parent (none) 
    subs[v].rank = 0; // initial rank (no parent so always 0) 
    lightest[v] = -1; // start from -1 
} 

int components = vertex; // iniitial trees = number of verticies 
int minWeight = 0; 

// must keep going until there is only one tree 
while (components > 1) 
{ 
    // lightest weight for all edges 
    for (int i=0; i<edge; i++) 
    { 
     // gets subsets for edges that could connect 
     int set1 = find(subs, e[i].v1); 
     int set2 = find(subs, e[i].v2); 

     // waste of time if they're already in same set so don't check 
     if (set1 == set2) 
      continue; 

     // if different then check which one is lightest 
     else 
     { 
      if (lightest[set1] == -1 || e[lightest[set1]].weight > e[i].weight) { 
       lightest[set1] = i; 
      } 

      if (lightest[set2] == -1 || e[lightest[set2]].weight > e[i].weight) { 
       lightest[set2] = i; 
      } 
     } 
    } 

    // making sure the wieghts are added 
    for (int i=0; i<vertex; i++) 
    { 
     // make sure all lightest edges are included 
     if (lightest[i] != -1) 
     { 
      int s1 = find(subs, e[lightest[i]].v1); 
      int s2 = find(subs, e[lightest[i]].v2); 

      if (s1 == s2) 
       continue; 

      minWeight += e[lightest[i]].weight; 

      // Need to sort output lexicographically!?!?!?!?!! 
      printf("Edge %d-%d included in MST with weight %d\n", // prints verices and weight of edge 
        e[lightest[i]].v1, e[lightest[i]].v2, 
        e[lightest[i]].weight); 

      // union subsets together, decrease component number 
      Union(subs, s1, s2); 
      components--; 
     } 
     lightest[i] = -1; // in case after first iteration lightest edges fall in same subset 
    } 

} 

printf("Weight of MST is %d\n", minWeight); 
return; 
} 

// main function for calling boruvka 
int main() { 
    ifstream infile; 
    char inputFileName[] = "graph.txt"; // input filename here 
    infile.open(inputFileName, ios::in); 

    string line; 

    getline(infile, line); 
    int V = atoi(line.c_str()); // set num of vertices to first line of txt 

    getline(infile, line); 
    int E = atoi(line.c_str()); // set num of edges to second line of txt 

    // create graph for boruvka 
    struct Graph* graph = formGraph(V, E); 

    if (infile.is_open()) { 
     string data[3]; // initialize data array 
     int count = 0; // initialize counter 

     while (infile.good()) { // same as while not end of file 
      getline(infile, line); 
      stringstream ssin(line); 
      int i = 0; 

     while (ssin.good() && i < 3) { 
      ssin >> data[i]; 
      i++; 
     } 

      graph->e[count].v1 = atoi(data[0].c_str()); 
      graph->e[count].v2 = atoi(data[1].c_str()); 
      graph->e[count].weight = atoi(data[2].c_str()); 

     count++; 
    } 
} 

freopen("mst.txt","w",stdout); // writes output into mst.txt 

// call boruvka function 
boruvka(graph); 

infile.close(); // close the input file 
return 0; 
} 

例はこれです：

9 
14 
0 1 4 
7 8 7 
1 2 8 
1 7 11 
2 3 7 
2 5 4 
2 8 2 
3 4 9 
3 5 14 
4 5 10 
5 6 2 
6 7 1 
6 8 6 
0 7 8 

私mst.txtに配置される正しいこの例の出力は、このされ：

Edge 0-1 included in MST with weight 4 
Edge 2-8 included in MST with weight 2 
Edge 2-3 included in MST with weight 7 
Edge 3-4 included in MST with weight 9 
Edge 5-6 included in MST with weight 2 
Edge 6-7 included in MST with weight 1 
Edge 1-2 included in MST with weight 8 
Edge 2-5 included in MST with weight 4 
Weight of MST is 37 

Answer 1

アルゴリズムによれば、まで加え縁CON、各反復において、フォレスト内の各ツリーは、一つを有し、唯一のエッジが独立に（異なる木のエッジが同じであってもよい）フォレストに追加しました森林全体を単一の木にする。

各ツリーの唯一のエッジが並行して実行できることがわかります。複数のツリーを持つ限り、複数のスレッドを使用して検索を高速化できます。