###### 我对这部分不理解，这个值的意思是什么
VexNode* src = &(ParallelGraph->adjlist[0]);
VexNode* tag = &(ParallelGraph->adjlist[331);
###### e = 45 的做用是什么
###### 可以对这段代码做一个解释吗
###### 还有要如何写一个graphsize的显示代码现实当前设置的size
######
#include <stdio.h>
#include <memory.h>
#include <malloc.h>
#include <windows.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <omp.h>
#include <tchar.h>
#define MAX_DISTANCE 99999
#define GRAPH_ERROR 0
#define MAX_VEX_NUM 500
#define MIN_ITERATOR_NUM 100
// Get the number of cores in your CPU.
const int g_ncore = omp_get_num_procs();
// Node of edge
typedef struct LinkNode
{
int adjvex;
int weight;
struct LinkNode* next;
}EdgeNode;
typedef struct VexNode {
int vertex;
int nMagic;
struct VexNode* pMagic;
EdgeNode* first;
};
// Graph Struct
typedef struct ALGraph {
int nNodeCount, e;
VexNode adjlist[MAX_VEX_NUM];
ALGraph operator=(ALGraph& graph)
{
nNodeCount = graph.nNodeCount;
e = graph.e;
memcpy(adjlist, graph.adjlist, MAX_VEX_NUM * sizeof(VexNode));
return *this;
};
};
// Get the thread num
int dtn(int n, int min_n)
{
int max_tn = n / min_n;
int tn = max_tn > g_ncore ? g_ncore : max_tn;
if (tn < 1) {
tn = 1;
}
return tn;
}
void SearchNextVertex(ALGraph* pGraph, VexNode** ppTNode, int nCount, VexNode** ppNode, int* pnDis, bool parallel)
{
int thread_num = 1;
if (parallel)
thread_num = dtn(pGraph->nNodeCount, MIN_ITERATOR_NUM);
#pragma omp parallel for num_threads(thread_num)
for (int i = 0; i < nCount; i++)
{
LinkNode* pNode;
int MinDis = MAX_DISTANCE;
int idd;
pNode = ppTNode[i]->first;
idd = pNode->adjvex;
int num;
num = pNode->adjvex;
if (pGraph->adjlist[num].nMagic != -1)
{
pNode = pNode->next;
}
while (pNode != NULL && pNode != 0x00000000)
{
int nu;
nu = pNode->adjvex;
if (pGraph->adjlist[nu].nMagic != -1)
{
pNode = pNode->next;
continue;
}
if (MinDis > ppTNode[i]->nMagic + pNode->weight)
{
MinDis = ppTNode[i]->nMagic + pNode->weight;
idd = pNode->adjvex;
}
else
{
pNode = pNode->next;
continue;
}
pNode = pNode->next;
}//while
pnDis[i] = MinDis;
VexNode* shortnode;
shortnode = &pGraph->adjlist[idd];
ppNode[i * 2] = shortnode;
ppNode[i * 2 + 1] = ppTNode[i];
}//for(i=0;i<nCounte...)
return;
}
int GetShortDistance(ALGraph* pGraph, VexNode* pSrcNode, VexNode* pTagNode, bool parallel)
{
int* pnDis;
int nTagDis = -1;
VexNode** ppTNode;
VexNode** ppNode;
pnDis = (int*)malloc(pGraph->nNodeCount * sizeof(int));
if (NULL == pnDis) { return GRAPH_ERROR; }
ppTNode = (VexNode**)malloc(pGraph->nNodeCount * sizeof(VexNode*));
if (ppTNode == NULL) {
free(pnDis);
return GRAPH_ERROR;
}
memset(ppTNode, 0, pGraph->nNodeCount * sizeof(VexNode*));
ppNode = (VexNode**)malloc(pGraph->nNodeCount * 2 * sizeof(VexNode*));
if (ppNode == NULL) {
free(pnDis);
free(ppTNode);
return GRAPH_ERROR;
}
int thread_num = 1;
if (parallel)
thread_num = dtn(pGraph->nNodeCount, MIN_ITERATOR_NUM);
#pragma omp parallel for num_threads(thread_num)
for (int i = 0; i < pGraph->nNodeCount; i++) {
pGraph->adjlist[i].nMagic = -1;
pGraph->adjlist[i].pMagic = NULL;
}
ppTNode[0] = pSrcNode;
ppTNode[0]->nMagic = 0;
ppTNode[0]->pMagic = NULL;
for (int k = 1; k < pGraph->nNodeCount; k++) {
int nTotalDis;
VexNode* pTNode;
pTNode = NULL;
nTotalDis = MAX_DISTANCE;
SearchNextVertex(pGraph, ppTNode, k, ppNode, pnDis, parallel);
int index = -1;
for (int i = 0; i < k; i++)
{
if (nTotalDis > pnDis[i])
{
nTotalDis = pnDis[i];
index = i;
}
}//for(i=0..)
if (index != -1)
{
pTNode = ppNode[index * 2];
pTNode->nMagic = nTotalDis;
pTNode->pMagic = ppNode[index * 2 + 1];
if (pTNode == pTagNode)
{
nTagDis = nTotalDis;
break;
}
}
else
{
//如果找不到最短路径
break;
}
ppTNode[k] = pTNode;
}
free(ppNode);
free(ppTNode);
free(pnDis);
return nTagDis;
}
int _tmain(int argc, _TCHAR* argv[])
{
int count = 10;
_int64 counter_begin;
_int64 counter_end;
_int64 run_time_parallel;
_int64 run_time_serial;
for (int iter = 0; iter < count; iter++)
{
ALGraph* ParallelGraph;
ALGraph* SerialGraph;
ParallelGraph = (ALGraph*)malloc(sizeof(ALGraph));
SerialGraph = (ALGraph*)malloc(sizeof(ALGraph));
if (ParallelGraph == NULL || SerialGraph == NULL) { return 0; }
ParallelGraph->nNodeCount = MAX_VEX_NUM;
ParallelGraph->e = 45;
// Create the data of graph.
srand(time(0));
for (int i = 0; i < MAX_VEX_NUM; i++)
{
ParallelGraph->adjlist[i].vertex = i;
ParallelGraph->adjlist[i].first = NULL;
for (int j = MAX_VEX_NUM - 1; j >= 0; j--)
{
if (i == j) {
continue;
}
LinkNode* p;
p = (LinkNode*)malloc(sizeof(LinkNode));
if (p == NULL) {
printf("No memory!\n");
return 0;
}
p->adjvex = j;
p->weight = rand() % 100 + 30;
p->next = ParallelGraph->adjlist[i].first;
ParallelGraph->adjlist[i].first = p;
}
}
SerialGraph = ParallelGraph;
VexNode* src = &(ParallelGraph->adjlist[0]);
VexNode* tag = &(ParallelGraph->adjlist[331);
// Get current performance start time.
QueryPerformanceCounter((LARGE_INTEGER*)&counter_begin);
int distance_parallel = GetShortDistance(ParallelGraph, src, tag, true);
// Get current performance end time.
QueryPerformanceCounter((LARGE_INTEGER*)&counter_end);
run_time_parallel = counter_end - counter_begin;
// Get current performance start time.
QueryPerformanceCounter((LARGE_INTEGER*)&counter_begin);
int distance_serial = GetShortDistance(SerialGraph, src, tag, false);
QueryPerformanceCounter((LARGE_INTEGER*)&counter_end);
run_time_serial = counter_end - counter_begin;
printf("Test %d:\nThe shortest path is %d\n--- Parallel take time %I64d\n--- Serial take time %I64d\n----Efficiency: %.2f%%\n--------------------------------\n", iter + 1, distance_parallel, run_time_parallel, run_time_serial, (run_time_serial * 1.0 / run_time_parallel) * 100.0);
}
}
e=45的意思没有解答，如果我想现实graphsize要怎么做
把ParallelGraph->adjlist第一个元素的地址赋值给指针变量src;
VexNode* src = &(ParallelGraph->adjlist[0]);
把ParallelGraph->adjlist第332个元素的地址赋值给指针变量tag;
VexNode* tag = &(ParallelGraph->adjlist[331);