PGX 19.1.0

Running Graph Algorithms on PGX

PGX provides two different ways for running graph algorithms.

Built-in Algorithms

PGX provides built-in implementations for a rich set of popular graph algorithms. The user can simply make use of the built-in implementation if his/her algorithm is one of them.

The PGX built-in algorithms include:

  • Centrality - Degree Centrality, Eigenvector Centrality, PageRank, Betweenness Centrality, Closedness Centrality, HITS, ...
  • Component and Community - Strongly Connected Components (Tarjan's and Kosaraju's). Weakly Connected Components, Twitter's Who-To-Follow, Label Propagation, ...
  • Path Finding - Single source all destination (Bellman-Ford), Dijsktra's shortest path, Hop Distance (Breadth-first search), ...
  • Community Evaluation - Coefficient (Triangle Counting), Conductance, Modularity, Adamic-Adar counter ...

Custom Algorithms

A custom graph algorithm, or any one that is not part of the built-in package, can still be implemented on PGX. For this purpose, PGX adopts a Domain Specific Language (DSL) approach.

More specifically, the user can program the algorithm with Green-Marl, a DSL for graph algorithms, as a front-end language, and submit it to PGX; PGX then compiles the Green-Marl program and executes it.

Note that all the current built-in algorithms of PGX are, in fact, created from the corresponding Green-Marl programs.

DSL Benefits

The DSL approach provides the following benefits

  • Productivity: Green-Marl provides high-level graph-specific data types and operators with which the user can program their algorithms intuitively.

  • Performance: PGX compiles the given Green-Marl program into a PGX-executable binary. In doing so, the Green-Marl compiler applies several optimizations as well as parallelization. Many of these optimizations are only enabled by the high-level information available from the semantic information of Green-Marl DSL.

  • Portability: Green-Marl helps PGX to maintain forward portability. Green-Marl programs, once written, can still be executable by future versions of PGX — no matter how much of its internal implementation might have changed. Especially important is that future implementation of the distributed PGX will support Green-Marl programs.