基于GPU的搜索图上两个节点之间的所有可能路径 [英] GPU-based search for all possible paths between two nodes on a graph

问题描述

我的工作广泛使用了Migliore，Martorana和Sciortino的算法来查找所有可能的简单路径，即在图中不曾遇到一次以上节点的简单路径，如下所述:

My work makes extensive use of the algorithm by Migliore, Martorana and Sciortino for finding all possible simple paths, i.e. ones in which no node is encountered more than once, in a graph as described in: An Algorithm to find All Paths between Two Nodes in a Graph. (Although this algorithm is essentially a depth-first search and intuitively recursive in nature, the authors also present a non-recursive, stack-based implementation.) I'd like to know if such an algorithm can be implemented on the GPU. At the moment I'm struggling to see any real parallelism in this problem. For example, the cost of monitoring and dispatching threads might make the a cooperative graph search (by hardware threads) prohibitive. Alternatively, a divide and conquer strategy could work if the graph is partitioned and assigned to individual hardware threads for searching. However, one would have to figure out how to (1) partition the graph (2) formulate the subtasks and (3) combine the results of the searches on the partitions.

推荐答案

对此有点生锈.Dijkstra怎么样?

Bit rusty on this. How about Dijkstra?

Boolean[] visited;              // [node] = true;
Boolean[][] connected;          // [node][i] = node
Vector<Vector<Integer>>[] path; // this should suck
Integer startNode;
Integer endNode;
Queue queue0; //for thread 0
Queue queue1; //for thread 1

while (queue0.hasNext()) {
   Integer node = queue.getNext();
   if visited[node] { 
      continue;
   } else {
      visited[node] = true;
   }

   for (nextNode: connected[node]) {
      for (i) {
         path[nextNode].append(path[node][i].clone().append(node));
      }
      if (nextNode%2 == 0) { queue0.add(nextNode); }
      if (nextNode%2 == 1) { queue1.add(nextNode); }
   }
}

path [endNode] [i]//从startNode到endNode的ith路径

path[endNode][i] // ith path to endNode from startNode

分区:来自节点％2
子任务:找到从节点去的地方
结合:你有共享的记忆，对不对?

partitioning: came from node % 2
subtasks: find place to go from node
combining: you have shared memory, right?

这篇关于基于GPU的搜索图上两个节点之间的所有可能路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！