Как преобразовать структуру графа C ++ в структуру графа Python / Numpy? - PullRequest
Новая
       9

Как преобразовать структуру графа C ++ в структуру графа Python / Numpy?

1 голос
/ 17 октября 2011

Отказ от ответственности: автор этого поста имеет ограниченные знания C ++ и Python и обладает достаточными знаниями Java и Ruby.

Пример из книги "Руководство по программированию OpenCL"использует следующую настроенную OpenCL графическую структуру данных для алгоритма Дейкстры для запуска на устройстве 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;
    }
}

Эта структура данных основана на примере из статьи «Ускорение алгоритмов больших графов на GPU с использованием CUDA»Pawan Harish и PJ Narayanan.

По сути, у него есть три массива: массив вершин V, каждая вершина которого указывает на свои соседние вершины в массиве ребер E (соседи вершины i+1 следуйте за соседями вершины i непосредственно в массиве E).Третий массив предназначен для весов ребер (есть еще два конкретных связанных с OpenCL массива).

Как я могу представить эту структуру данных в Python / Numpy? Я хотел бы использовать ее в PyOpenCL.

Ответы [ 2 ]

1 голос
/ 17 октября 2011
  • Все, что вы хотели знать о графиках и Python: http://wiki.python.org/moin/PythonGraphApi
  • Несколько авторов устаревших пакетов графиков рекомендуют этот пакет: http://networkx.lanl.gov/index.html. Он может преобразовывать граф в матрицу Numpy и обратно, в редкую матрицу Scipy и т. Д.
0 голосов
/ 17 октября 2011

Не эксперт по теме, но это какая-то матрица смежности (http://en.wikipedia.org/wiki/Adjacency_matrix). Тип данных Numpy core - это массив n-измерений, так что это должно быть довольно просто.

...