/GeoGraph

Primary LanguagePythonMIT LicenseMIT

GeoGraph

GeoGraph is a framework for shared-memory multicore machines, that supports routines for parallel geometric graph construction and parallel graph processing. GeoGraph contains high performance parallel primitives and algorithms implemented in C++, and includes a Python interface.

Geometric graph generators

  • Delaunay Graph
  • K-NN Graph
  • Gabriel Graph
  • Beta Skeleton

Graph algorithms

  • Hierarchical Agglomerative Clustering
  • Single Source Shortest Path
  • Minimum Spanning Tree
  • Connected Components
  • Breadth-First Search
  • Page Rank
  • K-Core

Compilation

Requirements:

  • g++ >= 7.4.0 with pthread support
  • Python 3 (tested on Python 3.8.5)

GeoGraph requires two build systems:

First, build GeoGraph by sh compile.sh from the project root directory, after which shared libraries and files will appear in the pybindings directory. Then install Python 3 dependencies by pip3 install -r pybindings/requirements.txt.

Example

Navigate to the pybindings directory and start a Python 3 session. We present a short example of generating the 1-NN graph of data.csv, and running the minimum-spanning tree algorithm:

import geograph

points = geograph.loadPoints("data.csv")

edges = geograph.KnnGraph(points, k = 1, weighted = True)

G = geograph.loadFromEdgeList(edges, symmetric = True, weighted = True)

F = G.MinimumSpanningForest()

Please refer to example.py for more examples.