如何将C++图结构转换为Python/Numpy图结构？

Question

免责声明：这篇文章的作者对C++和Python的了解有限，但对Java和Ruby有足够的知识。

在《OpenCL编程指南》这本书中，有一个例子使用了一个特别为Dijkstra算法设计的图数据结构，这个结构可以在OpenCL设备上运行：

void generateRandomGraph(GraphData *graph, int numVertices, int neighborsPerVertex)
{
    graph->vertexCount = numVertices;
    graph->vertexArray = (int*) malloc(graph->vertexCount * sizeof(int));
    graph->edgeCount = numVertices * neighborsPerVertex;
    graph->edgeArray = (int*)malloc(graph->edgeCount * sizeof(int));
    graph->weightArray = (float*)malloc(graph->edgeCount * sizeof(float));

    for(int i = 0; i < graph->vertexCount; i++)
    {
        graph->vertexArray[i] = i * neighborsPerVertex;
    }

    for(int i = 0; i < graph->edgeCount; i++)
    {
        graph->edgeArray[i] = (rand() % graph->vertexCount);
        graph->weightArray[i] = (float)(rand() % 1000) / 1000.0f;
    }
}

这个数据结构的设计灵感来源于Pawan Harish和P. J. Narayanan的论文《使用CUDA加速大型图算法》。

简单来说，这个数据结构包含三个数组：第一个是顶点数组 V，每个顶点指向它在边数组 E 中的邻居顶点（比如，顶点 i+1 的邻居紧接着在数组 E 中跟着顶点 i 的邻居）。第三个数组是用来存储边的权重（另外还有两个与OpenCL相关的特定数组）。

我该如何在Python/Numpy中表示这个数据结构呢？ 我想在PyOpenCL中使用它。

Answer 1

我对这个话题不是专家，但这是一种邻接矩阵（可以参考这个链接：http://en.wikipedia.org/wiki/Adjacency_matrix）。Numpy的核心数据类型是n维数组，所以这应该是比较简单的。

Answer 2

• 你想了解关于图和Python的所有知识，可以查看这个链接：http://wiki.python.org/moin/PythonGraphApi
• 一些已经不再维护的图形包的作者推荐这个包：http://networkx.lanl.gov/index.html。它可以把图转换成Numpy矩阵、Scipy稀疏矩阵等格式。